Modificar o programa abaixo

[TamiresLelis 0]

Preciso fazer esse programa ficar bastante diferente ao ponto que quando eu colocar no google: backtraking UFMG aparece um diferente.

E outra esse algoritmo está faltando essa parte do trabalho:Pois,além do mais a unica coisa o que esse algoritmo faz é achar o caminho do cavalo e ele nao calcula possibilidade ou profundidade

Objetivo: Este trabalho tem como objetivo a implementação do Passeio do Cavalo e sua avaliação para um tabuleiro 8 x

8. Pede-se:

1. O possível Passeio do Cavalo começando na posição (1; 1) (canto superior esquerdo do tabuleiro)

2. Suponha a geração do Passeio do Cavalo, cada um começando em uma das 64 casas do tabuleiro.

Deseja-se calcular:

(a) a profundidade que se consegue alcançar na árvore de possibilidades até a primeira vez que se chega a

uma posição que não seja possível caminhar mais e deve ser feito um retrocesso;

(B) o número de possibilidades até esse momento.

Por exemplo, para um tabuleiro 4 x 4, começando na posição (1; 1) e sempre tentando as posições na

ordem de 1 a 8, temos o seguinte passeio:

Legenda: Casa visitada no n-ésimo passo {Identificação (n°) dos movimentos válidos}, sendo que o primeiro movimento

(n°) que aparece é o que foi escolhido.

Neste caso, a primeira casa visitada (que tem o número 1) está no canto superior esquerdo. A partir dessa casa, só é

possível executar dois movimentos: 7 e 8. Como o primeiro movimento é escolhido, a segunda casa visitada recebe o

número 2 e foi alcançada executando o movimento 7. Ao se chegar à 14 a casa visitada, não é possível prosseguir. Até

esse momento, temos a seguinte quantidade de possibilidades:

2 x 3 x 2 x 2 x 2 x 2 x 2 x 2 x 1 x 1 x 2 x 1 x 2 = 29 x 3 = 1536:

Ao não ser possível continuar, teríamos que retornar até à 13a casa, escolher o movimento 7 e tentar prosseguir. Se ainda

assim não for possível prosseguir, teríamos que retornar até à 11a casa, escolher o movimento 5 e tentar continuar. Veja

que nesse exemplo só existe uma alternativa na 12a casa, fazendo com que seja necessário retornar até a primeira casa

onde haja mais de uma possibilidade de movimento, que nesse momento é a 11a casa.

 

#include<iostream>
#include <iomanip.h>
const int n = 8;
struct desloc{  // deslocamentos nas direções x e y 
   int dx; 
   int dy; 
};
// vetor de deslocamentos que define os possíveis  
// movimentos do cavalo no tabuleiro de xadrez 
desloc mov_cav[8]={{ 2, 1},{ 1, 2},{-1, 2},{-2, 1},{-2,-1},{-1,-2},{ 1,-2},{ 2,-1}}; 
int **T;      //  tabuleiro 
int nsq;      //  número de posiçoes no tabuleiro n^2 
bool tente_mov(int i, int x, int y){  
   int u, v;    // posição do próximo movimento 
   bool q;     // true => movimento com sucesso  
   int k=0;  
   do{ 
       q=false; 
       u = x+mov_cav[k].dx; 
       v = y+mov_cav[k].dy; 
       k=k+1;
       // verifica se a posição é válida no tabuleiro  
       // e se a posição ainda não foi visitada 
       if (0 <= u && u < n && 0 <= v && v < n && T[u][v]==0){ 
           T[u][v]=i;            // registra a visita 
           if (i < nsq){        
               // ainda há posições no tabuleiro não visitadas  
               q = tente_mov(i+1,u,v); 
               if (!q)         // movimento sem sucesso 
                   T[u][v]=0;    // remova o registo de "visita" 
           }else q=true; 
       } 
   }while (!q && k<8); 
   return q; 
}
main(){
   bool ok; 
   nsq = n*n; 
   // Aloca espaço para o tabuleiro 
   T=new (int* [n]); 
   for (int i=0; i < n; i++) 
       T[i]=new (int[n]); 
   for (int i=0; i < n; i++) 
       for (int j=0; j < n; j++) 
           T[i][j]=0; 
   T[0][0]=1; 
   ok=tente_mov(2,0,0); 
   if (ok){ 
       cout.setf(ios::right); 
       for (int i=0; i < n; i++){ 
           for (int j=0; j < n; j++) 
               cout << setw(4) << T[i][j] << "  "; 
           cout << endl; 
       } 
   }else cout << "Nao ha solucao \n"; 
   system("pause");
}

[Kakashi_Hatake 267]

O bom seria você fazer um do zero, em vez de pegar um pronto e "maquiar" para não descobrirem que foi outra pessoa quem fez.