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))
            }
        }
    }
}