Problema do Passeio do Cavalo

Prévia do material em texto

Problema do Passeio do Cavalo: A partir de uma posição inicial é possível 
visitar todas as posições do tabuleiro com o cavalo (peça), de modo a passar 
por cada casa uma única vez?
Algumas posições centrais 
permitem escolher oito 
possíveis movimentos
Estratégia: Vamos 
ordenar os possíveis 
movimentos no sentido 
antí-horário.
1
2
3
45
6
7
8
Um possível passeio, .... Upa, upa cavalinho
1
2
3
45
6
7
8
E assim, sucessivamente, ..., 
Problema do Passeio do Cavalo
Algumas posições próximas 
das bordas do tabuleiro não 
permitem escolher a 
totalidade dos oito 
movimentos
Problema? 
Estou 
representando o 
tabuleiro por um 
array 2D.
Problema do Passeio do Cavalo
Problema 01: O tabuleiro 
está sendo representado por 
uma matriz (array 2d). Como 
detectar se o cavalo está fora do 
tabuleiro?
Problema 02: Como detectar 
se uma dada casa já foi visitada? 
Lembre-se que eu quero visitar 
cada casa (posição), uma única 
vez. 
A solução para o 
Problema 01 seria 
criar linhas e colunas 
adjacentes ao 
tabuleiro original, 
mas não permitir que 
estas posições sejam 
visitadas (a rigor elas 
não existem), ou 
seja, representá-las, 
mas não permitir que 
o movimento seja 
realizado para elas.
Já que estamos 
representando o 
tabuleiro por um 
array 2D, a solução 
para o Problema 
02 seria associar o 
valor 0 (zero) para 
indicar as casas 
não visitadas e o 
valor 1 (um) para 
as casas já
visitadas. Com 
essa abordagem é
possível saber se a 
partir de uma casa, 
podemos ou não 
realizar um dado 
movimento. 
0 1 2 3 4 5 6 7 8 9 10 11
0
1 
2 
3 
4 
5
6
7
8
9
10
11
Inicialização
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
0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
Código Associado a Inicialização do Tabuleiro. 
#define MAX1 12
#define MAX2 10
...
int Tabuleiro[MAX1][MAX1];
...
void Inicializa_Tabuleiro(void){
int i,j;
// visitando todas as casas
for(i=0; i < MAX1; i++)
for(j=0; j < MAX1; j++) Tabuleiro[i][j] = 1;
// atualizando corretamente as casas verdadeiras do tabuleiro real
for(i=2; i < MAX2; i++)
for(j=2; j < MAX2; j++) Tabuleiro[i][j] = 0;
return;
}
Código Associado a Impressão do Tabuleiro. 
void Imprime_Tabuleiro(void) {
int i = 0, j;
for (; i < MAX1; i++) {
for (j=0; j < MAX1; j++) printf("%4d", Tabuleiro[i][j]);
printf("\n");
} // for mais interno
return;
}
Vamos associar ao conteúdo da matriz Tabuleiro na posição (i,j) (Tabuleiro[i][j]), 
o número inteiro que corresponde a ordem em que a “casa” foi visitada. 
Código Associado a Leitura da Posição Inicial de onde o cavalo irá iniciar o passeio. 
Observe que o usuário não possui as informações de como o tabuleiro está
representado. Para todos os efeitos, ele conhece um tabuleiro 8x8 (normal).
void Leitura_Posicao_Inicial(int *Posi, int *Posj) {
printf(" Introduza a linha da POSICAO INICIAL>> ");
scanf("%d",Posi); // 1 <= Posi <= 8
printf("\n\n");
printf(" Introduza a coluna da POSICAO INICIAL>> ");
scanf("%d",Posj); // 1 <= Posj <= 8
// atualizando as posições para o tabuleiro real (12x12)
(*Posi)++; // atualizando a posição da linha
(*Posj)++; // atualizando a posição da coluna
return;
} // Leitura_Posicao_Inicial
Questão Fundamental: Como descobrir o próximo movimento a partir de uma 
posição (i,j) arbitrária ?
Movimento 1 : (i-2,j+1)
Movimento 2 : (i-1,j+2)
Movimento 3 : (i+1,j+2)
Movimento 4 : (i+2,j+1)
Movimento 5 : (i+2,j-1)
Movimento 6 : (i+1,j-2)
Movimento 7 : (i-1,j-2)
Movimento 8 : (i-2,j-1)
i
j
i
j
Código Associado a descoberta do Próximo Movimento para onde o cavalo irá a partir 
de onde ele está, ou seja, continuar o seu passeio. 
int Proximo_Movimento(int Posx, int Posy) {
int pos=0; // indica que não é possível continuar
if (Tabuleiro[Posx-2][Posy+1] == 0) pos=1;
else if (Tabuleiro[Posx-1][Posy+2] == 0) pos=2;
else if (Tabuleiro[Posx+1][Posy+2] == 0) pos=3;
else if (Tabuleiro[Posx+2][Posy+1] == 0) pos=4;
else if (Tabuleiro[Posx+2][Posy-1] == 0) pos=5;
else if (Tabuleiro[Posx+1][Posy-2] == 0) pos=6;
else if (Tabuleiro[Posx-1][Posy-2] == 0) pos=7;
else if (Tabuleiro[Posx-2][Posy-1] == 0) pos=8;
return(pos);
} // Proximo_Movimento
Código associado a atualização da posição para onde o cavalo irá a partir de onde ele 
está, ou seja, esta posição recebe um valor diferente de zero. 
void Atualiza_Nova_Posicao(int Visita, int Mov, 
int *Posx, int *Posy) {
switch( Mov ) {
case 1: *Posx-=2; *Posy+=1; break;
case 2: *Posx-=1; *Posy+=2; break;
case 3: *Posx+=1; *Posy+=2; break;
case 4: *Posx+=2; *Posy+=1; break;
case 5: *Posx+=2; *Posy-=1; break;
case 6: *Posx+=1; *Posy-=2; break;
case 7: *Posx-=1; *Posy-=2; break;
case 8: *Posx-=2; *Posy-=1;
}
Tabuleiro[*Posx][*Posy] = Visita;
return;
}
Código associado a função main(). 
int main(void) {
int pi, pj, continua_loop = 1, ordem_visita = 1;
int prox_mov = 0;
Inicializa_Tabuleiro();
Leitura_Posicao_Inicial(&pi, &pj);
Tabuleiro[pi][pj] = 1;
do {
prox_mov = Proximo_Movimento(pi,pj);
if ( prox_mov ) {
ordem_visita++;
Atualiza_Nova_Posicao(ordem_visita, prox_mov, &pi, &pj);
}
else continua_loop = 0;
} while (continua_loop);
printf("\n\n\n");
Imprime_Tabuleiro();
printf("\n\n\nNumero de casas visitadas >>> %d \n\n", ordem_visita);
system("Pause");
return(0);
} // main
Pergunta 1: A partir de qual posição inicial, eu consigo maximizar o 
número de movimentos do cavalo?
Pergunta 2: Há mais de uma posição que maximiza o número 
movimentos do cavalo?
Pergunta 3: Qual a posição inicial em que o número de 
movimentos do cavalo é mínimo?
Pergunta 4: Existe uma posição inicial que permite passear por 
todas as casas do tabuleiro, segundo a estratégia adotada?
Observação: Observem que nossa estratégia é muito simples, 
podemos implementar estratégias mais elaboradas com o uso de 
pilhas (backtracking) que conseguem realizar um percurso por 
todas as casas do tabuleiro uma única vez.