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…