Mostrando entradas con la etiqueta backtraking. Mostrar todas las entradas
Mostrando entradas con la etiqueta backtraking. Mostrar todas las entradas

miércoles, 17 de julio de 2019

backtracking busca solucion caballo en javascript



        //8x8
        var tablero = [
            [0,0,0,0,0,0,0,0],
            [0,0,0,0,0,0,0,0],
            [0,0,0,0,0,0,0,0],
            [0,0,0,0,0,0,0,0],
            [0,0,0,0,0,0,0,0],
            [0,0,0,0,0,0,0,0],
            [0,0,0,0,0,0,0,0],
            [0,0,0,0,0,0,0,0]
        ];

        var pasos_limite_caballo = 10;
        var jugadasPosibles = [[1,2],[1,-2],[2,1],[2,-1],[-1,2],[-1,-2],[-2,-1],[-2,1]] //total 8
        // jugadasPosibles.push()

function moverCaballoA(i,j, saltosCaballo){
  
    if(saltosCaballo > pasos_limite_caballo) return true; //fin
  
    //para todas las jugadas posibles
    for (var k = 0; k < jugadasPosibles.length; k++) {
        var jug = jugadasPosibles[k];
        if(esJugadaValida(i,j,jug) && tablero[i+jug[0]][j+jug[1]] == 0){
            console.log('jugada valida', i,j, jug, saltosCaballo)
            saltosCaballo++
            tablero[i][j] = saltosCaballo;
            res = moverCaballoA(i + jug[0], j + jug[1], saltosCaballo)
            if(res){
                return true;
            }else{
                //camino no valido
                console.log('camino no valido', i,j, jug, saltosCaballo)
                return false
            }
        }else{
            console.log('jugada no valida', i,j, jug, saltosCaballo)
            // return;

        }
    }

    return false;
}

function buscar_solucion(){

    for (var i = 0; i < 8; i++) {
        for (var j = 0; j < 8; j++) {      
            resetTablero()      
            res = moverCaballoA(i, j, 0)
            if(res){
                console.log("se encontro 1 solucion")
                Sistema.dibujarTableroVisible(tablero)
                $("#mensaje").text("se encontro 1 solucion")
                return true;
            }else{
                console.log("NO se encontro solucion empezando en:", i,j)
               $("#mensaje").text("NO se encontro solucion ")
                // console.log(tablero.slice(0))
            }
        }
    }
}