Sair do ponto [7][7] e chegar no [7][0] no tabuleiro

Programação Java
#1

Galera, não sei se postei no forum certo, aqui não tem nenhuma área para dúvidas de algoritmos, mas como implementei em java, to postando…

vamos a questão:

Eu tenho um tabuleiro 8x8, nesse tabuleiro eu tenho que sair do ponto [7][0] e chegar no ponto [7][7], segue abaixo o modelo do tabuleiro:

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

99 0 0 0 0 0 0 1

eu tenho que sair de 1 e chegar em 99, utilizando o movimento do cavalo, só que minha lógica não tá funfado, meu algoritmo tá sempre entrando em loop infinito, estou estudando sobre BackTracking e, ainda tá meio confuso a recursão nesse método. Segue o algoritmo abaixo

public class TentativaErro {
    private static final int T_TABULEIRO = 8; // tamanho do tabuleiro
    private int x[], y[], tabuleiro[][];
    
    /** Creates a new instance of TentativaErro */
    public TentativaErro() {
        
        this.tabuleiro = new int[T_TABULEIRO][T_TABULEIRO];
        this.x = new int[T_TABULEIRO]; this.y = new int[T_TABULEIRO];
        
        // movimentos possíveis do cavalo no tabuleiro
        x[0] = 2; x[1] = 1; x[2] = -1; x[3] = -2;
        y[0] = 1; y[1] = 2; y[2] =  2; y[3] =  1;

        x[4] = -2; x[5] = -1; x[6] =  1; x[7] =  2;
        y[4] = -1; y[5] = -2; y[6] = -2; y[7] = -1;
        
        this.tabuleiro[7][7] = 1;  // posicao inicial = saída
        this.tabuleiro[7][0] = 99; // local onde o algoritmo tem que chegar = final
    }
    
    public boolean tenta(int i, int x, int y) {
        
        int dx, dy;
        int k = -1;
        boolean q = false;
                
        do {
        
            // tente mover-se para uma posição válida
            k = k+1;
            dx = x + this.x[k]; // deslocamento de x = posicão atual mais o valor de x[0..7] (que é os movimentos possiveis do cavalo)
            dy = x + this.y[k];
            
           
            // verifica se a posição é valida e se ainda nao foi visitada
            if ((dx >= 0) && (dx <= 7) && (dy >= 0) && (dy <= 7) && this.tabuleiro[dx][dy] == 0) {
                this.tabuleiro[dx][dy] = i;
                
                if ( this.tabuleiro[7][0] == 99 ) { // se ainda nao chegou no final
                     q = tenta (i+1, dx, dy); // tenta novo movimento
                     if ( q == false ) tabuleiro[dx][dy] = 0;
                } else {    
                    q = true;
                }
            }
            
                
        } while ( !q && (k!=7) );
        
      return q;
    }
    
    public void imprimeTabuleiro() {
        
        for(int linha = 0; linha < T_TABULEIRO; linha++) {
            for(int coluna = 0; coluna < T_TABULEIRO; coluna++) {
                System.out.printf("%5d", tabuleiro[linha][coluna]);
            }
            System.out.println();
        }

    }
}

chamo o algoritmo assim:

        TentativaErro obj = new TentativaErro();
        boolean b = obj.tenta(2, 7, 7);
        obj.imprimeTabuleiro();

tipo…eu to entrando em loop infinito, não consigo chegar a solução final…esse algoritmo tem que ser automático, pois, se eu mudar a posição de chegado o algoritmo ir automático…

palavras chaves: backtracking, busca exaustiva…(pensei nessa técnica para implementar)

Abraços…

#2

Consegui!

esse pequeno erro na variável estava me travando…

            // tente mover-se para uma posição válida
            k = k+1;
            dx = x + this.x[k]; // deslocamento de x = posicão atual mais o valor de x[0..7] 
            dy = x****** + this.y[k]; // errado
            dy = y+ this.y[k]; // certo

tinha que chamar y e não x…

com essa lógica eu vou aplicar agora em um labirinto…

P.S; notei também que o algoritmo não vai pelo menor caminho…isso é algo pra se estudar tmb…rsr…

abraços[/code]

#3