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

[tocho 0]

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 (fiz a implementação em java)

 

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] 			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();		}	}}

chamada do código

 

public class Main {		/** Creates a new instance of Main */	public Main() {	}		/**	 * @param args the command line arguments	 */	public static void main(String[] args) {		TentativaErro obj = new TentativaErro();		boolean b = obj.tenta(2, 7, 7);		obj.imprimeTabuleiro();			   	}	}

Alguém pode ajudar?.....preciso descobrir o erro, sempre entro em loop infinito...

 

att

[Palc 0]

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 2 0 2

0 * 0 * 2 0 2 0

* + 0 2 * 0 1 2

0 0 + * 2 1 0 0

X 0 * 2 * 2 0 Y

 

onde

1 : possíveis posições do cavalo c/ 1 movimento

2 : possíveis posições do cavalo c/ 2 movimentos

+ : possíveis posições do cavalo c/ n-1 movimentos (observe que p/ o cavalo chegar até X tem que passar por um desses dois pontos)

* : possíveis posições do cavalo c/ n-2 movimentos

n é o número de movimentos do cavalo de Y até X

 

Agora fica fácil de ver q em 5 movimentos temos uma das soluções (siga os números sublinhados):

 

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 2 0 2

0 * 0 * 2 0 2 0

* 4 0 2 * 0 1 2

0 0 + 3 2 1 0 0

5 0 * 2 * 2 0 Y

 

Agora você desenvolve outro algoritmo ;) OU

tenta corrigir/melhorar o seu, parece que seu contador de movimentos (tentativas) é 'k'

e você escreveu 'this.tabuleiro[dx][dy] = i;' só que não sei se só isso (trocar o 'i' pelo 'k') vai resolver !

 

{}

Palc

[tocho 0]

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 2 0 2

0 * 0 * 2 0 2 0

* + 0 2 * 0 1 2

0 0 + * 2 1 0 0

X 0 * 2 * 2 0 Y

 

onde

1 : possíveis posições do cavalo c/ 1 movimento

2 : possíveis posições do cavalo c/ 2 movimentos

+ : possíveis posições do cavalo c/ n-1 movimentos (observe que p/ o cavalo chegar até X tem que passar por um desses dois pontos)

* : possíveis posições do cavalo c/ n-2 movimentos

n é o número de movimentos do cavalo de Y até X

 

Agora fica fácil de ver q em 5 movimentos temos uma das soluções (siga os números sublinhados):

 

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 2 0 2

0 * 0 * 2 0 2 0

* 4 0 2 * 0 1 2

0 0 + 3 2 1 0 0

5 0 * 2 * 2 0 Y

 

Agora você desenvolve outro algoritmo ;) OU

tenta corrigir/melhorar o seu, parece que seu contador de movimentos (tentativas) é 'k'

e você escreveu 'this.tabuleiro[dx][dy] = i;' só que não sei se só isso (trocar o 'i' pelo 'k') vai resolver !

 

{}

Palc

tipo....entendi o que você passou, mas, a idéia é fazer um algoritmo que se eu mudar a posição final, ele execute "automático", por exemplo; se colocar o x na posicao [0][0] ele vá para lá, e assim por diante, o this.tabuleiro[dx][dy] = i; tem o i, porque eu uso ele para incrementar, e assim mostrar o movimento..

 

abraços...

[Palc 0]

Olhei melhor o seu programa, agora que ví o porquê do 'i', beleza.A melhor forma de testar o algoritmo é a mão mesmo.A idéia era só dá uma forcinha para q você tivesse um outro ponto de vista do problema e então, quem sabe, visualizar melhor o (um) algoritmo para resolver.A idéia que passei é ir avançando do Y(início) p/ o X(fim) e do X p/ o Y também e qdo se encontrarem é uma solução.Se bem q isso pode complicar um pouco a "lógica da coisa"Bom, vamos ver se alguém tem mais idéias.{}Palc

[tocho 0]

Olhei melhor o seu programa, agora que ví o porquê do 'i', beleza.A melhor forma de testar o algoritmo é a mão mesmo.A idéia era só dá uma forcinha para q você tivesse um outro ponto de vista do problema e então, quem sabe, visualizar melhor o (um) algoritmo para resolver.A idéia que passei é ir avançando do Y(início) p/ o X(fim) e do X p/ o Y também e qdo se encontrarem é uma solução.Se bem q isso pode complicar um pouco a "lógica da coisa"Bom, vamos ver se alguém tem mais idéias.{}Palc

Então....eu tava pensando em backtracking que segue a seguinte lógica:1- Passos em direção ao objetivo final são tentados e registrados2- Caso esses passos nao leve a solução final, tire o registro do passo anterior e tente um novo passoE foi o que tentei fazer no algoritmo..só que sem sucesso...Vamos ver se alguém tem mais idéias..vou tentando aqui..e qualquer sucesso aviso..aguardo..{}

[tocho 0]

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