segunda-feira, 21 de maio de 2012

Passeio do cavalo


A recursividade pode ser usada para resolver problemas cuja solução é tentar todas as alternativas possíveis. A idéia para algoritmos tentativa e erro é decompor  o problema em um número finitos de sub-tarefas  parciais que devem ser exploradas exaustivamente.  Isso significa que devemos testar todas as possibilidades de resultados em um problema à fim de descobrir qual o melhor resultado para esse. Costumam ser algoritmos com uma implementação simples, porém com uma complexidade geralmente elevada.

Exemplo: Dado um tabuleiro com n x n posições, o cavalo movimenta-se segundo as regras do xadrez. Enconte um passeio de um cavalo no tabuleiro de xadrez que visite todas as posições do tabuleiro.


A partir da posição inicial (x0,y0), o problema consiste em encontrar, se existir, um passeio do valo com n2 – 1 movimentos, tal que todos os pontos do tabuleiro são visitados uma única vez. Um caminho para resolver o problema é considerar a possibilidade de realizar o próximo movimento ou verificar que ele não é possível.

Algoritmo Básico


 Um exemplo de uma solução para o problema do passeio de um cavalo para o tabuleiro 8x8.  






















#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int t[8][8],a[8],b[8];
void imprime(){
 int i,j;
 for(i=0;i<8;i++){ 
   for(j=0;j<8;j++){ 
     printf("%3d",t[i][j]);} 
    printf("\n"); 
   }
}
int cavalo(int i, int x, int y){
 int u,v,k,q; 
 if(i==65){ imprime(); return 1;}
 //executa movimentos
 for(k=0;k<8;k++){
  u = x + a[k];  v = y + b[k];
  //testa limites do tabuleiro
  if( (u>=0 && u<=7) && (v>=0 && v<=7)){
   if(t[u][v]==0){ //posicao livre
    t[u][v]=i; //registre o movimento
    q = cavalo(i+1,u,v);
    if(q==0) t[u][v]=0; //se não alcançou todos, desfaça 
    else return 1; // se alcançou todos, retorne 1
   }
  }
 }
 return 0;
}
int main(){
 int cont;
 //inicializa��o dos deslocamentos dos movimentos
 a[0]=2;a[1]=1;a[2]=-1;a[3]=-2; 
 b[0]=1;b[1]=2;b[2]=2;b[3]=1;
 
 a[4]=-2;a[5]=-1;a[6]=1;a[7]=2;
 b[4]=-1;b[5]=-2;b[6]=-2;b[7]=-1; 
 memset(t,0,sizeof(t));
 cont =1;
 t[0][0]=1;
 cavalo(2,0,0);
 system("PAUSE");
}










Bibliografia
Ziviani, N. Projeto de Algoritmos Com Implementações em Pascal e C, Pioneira Thomson Learning, 1993.

8 comentários:

Gabriel disse...

Por favor, qual o significado das variáveis:
i, x, y, u, v, k, q

Wladimir Araújo Tavares disse...

i, x, y, u, v, k, q
i representa o número do movimento do cavalo
x, y posição do último cavalo posicionado
u,v próxima posição do cavalo
q guarda retorno da função cavalo(i,x,y)
se q==0 significa que o cavalo não conseguiu
atingiu 64 casas do tabuleiro
se q==1 significa que o cavalo atingiu 64 casas do tabuleiro
k variável de controle do for para variar 8 tipos de movimento

tupete disse...

como eu consigo mudar a posição inicial do cavalo?

Samara Silva disse...

Como eu faço pra acrescentar um contador que
conte o número de deslocamento do cavalo?
Tipo, tem 64 posições que ele tem que percorrer em L, mas como
esse é um problema de Backtracking na qual se o cavalo acessa
uma posição já ocupada, ele desfaz o movimento. Dessa forma,
preciso saber cmo implementar o programa, de forma que será contada
todas as posiçoes que ele percorrer.

samara.silva1994@hotmail.com
Muito Obrigada

Cristian disse...

É muito inteligente explicar essas coisas com xadrez. Eu gosto de jogar xadrez com os meus amigos na minha casa. o meu melhor amigo tem um cão para aqui quando se trata de minha casa, levar o cachorro em seu carro e amarrado com Tubline por questões de segurança no carro. Beijos

gabrissk disse...

Cara, e seu eu quisesse fazer para um tabuleiro de n² casas? Tem jeito?

skox disse...

Saudações ...

Gostei muito desde blog e em particular, deste post.

Apenas uma indagação [retórica] minha: já imaginaram jogar xadrez em um tabuleiro n x n de tamanho infinito ?!?!

Tchau e até a próxima ...

benny disse...

Como seria para ele começar o passeio em qualquer uma das 64 casas. No caso 64 probabilidades de passeios.