|
Ficheiro:Knights_tour_(Euler).png|Solução com refinamento matématico onde a soma das colunas e fileiras é 260..
</gallery></center>
== {{Ver também}} ==
O problema pode ser resolvido com uma implementação de uma árvore genérica que irá reproduzir o maior número de soluções possíveis. Porém, é necessário à implementação de uma heurística, que irá calcular o nó mais propenso para que busca pelo caminho completo seja realizada.
O algoritmo abaixo demonstra milhares de soluções para diferentes coordenadas em um tabuleiro 8 x 8. Árvores genéricas são uma boa solução quando se quer resolver um problema com a força bruta.
=== [[Linguagem de programação C|C]] ===
<source lang="c">
#include <stdio.h>
#include <stdlib.h>
//Realizado em 10/01/2007
//fabone.moreira@gmail.com
struct No{//No responsabile per criazione dell albero
int B;//inteiro che fa evventuale differenza fra i No tra quelli genitori e quelli figli
int F;
int folha;//
int scacch[9][9];//qui mettiamo le posizioni coi cavalli
struct No *ant;
struct No *Brother;
struct No *Father;
};
int gnum=0; //variabile globale per contare i no
typedef struct No *Lista;
Lista Raiz(Lista L){
register int i;
L=(Lista)malloc(sizeof(struct No));
L->B=-1;//in questo modo sappiamo che é la radice
L->F=-1;
L->folha=0;
L->ant=NULL;
for(i=0;i < 81;i++)//zera tutte le scacchiere
*(L->scacch[0]+i)=0;
L->Brother=NULL;
L->Father=NULL;
return L;
}
Lista Brother(Lista L){
register int i;
gnum++;//cosi contiamo i vari no dell albero
Lista aux;
aux=(Lista)malloc(sizeof(struct No));
aux->folha=0;
aux->Father=NULL;
for(i=0;i < 81;i++)//zera tutte le scacchiere
*(aux->scacch[0]+i)=0;
aux->ant=L;//poter ritornare al No antecedente
L->Brother=aux;
aux->Father=NULL;
aux->Brother=NULL;
return aux;
}
Lista Father(Lista L){
register int i;
gnum++;//cosi contiamo i vari no dell albero
Lista aux;
aux=(Lista)malloc(sizeof(struct No));
aux->folha=0;
aux->Brother=NULL;
for(i=0;i < 81;i++)//zera tutte le scacchiere
*(aux->scacch[0]+i)=0;
aux->ant=L;//poter ritornare al No antecedente
L->Father=aux;
aux->Brother=NULL;
aux->Father=NULL;
return aux;
}
int gfine=0;//cosi sappiamo i vari Nó incontrati
void Mostrar(Lista L){
register int l,c;
printf("Numero di No foglie attuali %d \n",gnum);
printf("Quantitá di soluzioni incontrate ( %d )\n",gfine);
for(l=0;l < 8;l++){
for(c=0;c < 8;c++){
printf(" %d ",L->scacch[l][c]);
}
printf("\n\n");
}
}
int CercaFoglia(Lista L){
int k,y,m=0,l,c;
for(k=0;k < 8;k++){
for(y=0;y < 8;y++){
if( L->scacch[k][y] == 0 ){
m=0;
l=k;
c=y;
if( l+1 < 8 && c+1 < 8){
if(L->scacch[l+1][c+2]== 0 && l+1 >= 0 && c+2 >= 0 && l+1 < 8 && c+2 < 8)
m++;//serve per poter passar alla prossima verificazione di possibilita!
}
if(l+1 < 8 && c-2 >= 0){
if(L->scacch[l+1][c-2]==0 && l+1 >= 0 && c-2 >= 0 && l+1 < 8 && c-2 < 8)
m++;
}
if(l+2 < 8 && c+1 < 8 ){
if(L->scacch[l+2][c+1]==0 && l+2 >= 0 && c+1 >= 0 && l+2 < 8 && c+1 < 8)
m++;
}
if(l+2 < 8 && c-1 >= 0){
if(L->scacch[l+2][c-1]==0 && l+2 >= 0 && c-1 >= 0 && l+2 < 8 && c-1 < 8)
m++;
}
if(l-2 >= 0 && c+1 < 8){
if(L->scacch[l-2][c+1]==0 && l-2 >= 0 && c+1 >= 0 && l-2 < 8 && c+1 < 8)
m++;
}
if(l-2 >= 0 && c-1 >= 0){
if(L->scacch[l-2][c-1]==0 && l-2 >= 0 && c-1 >= 0 && l-2 < 8 && c-1 < 8)
m++;
}
if(l-1 >=0 && c+2 <= 8){
if(L->scacch[l-1][c+2]==0 && l-1 >= 0 && c+2 >= 0 && l-1 < 8 && c+2 < 8)
m++;
}
if(l-1 >=0 && c-2 >= 0){
if(L->scacch[l-1][c-2]==0 && l-1 >= 0 && c-2 >= 0 && l-1 < 8 && c-2 < 8)
m++;
}
if(m == 0){
L->folha=1;
return 0;
}
}
}
}
}
int Inserisce(Lista L,register int l,register int c,int cav){
if(l > 7||c > 7|| l < 0|| c < 0|| cav > 64|| cav < 1){//caso entri un paramentro sbagliato
printf("Parametri della funzione sbagliati\nSchiaccia enter per uscire pirlone!!\n\n");
getchar();
exit(1);
}else{
if(L->scacch[l][c] == 0 && L->folha == 0){
L->scacch[l][c]=cav;
CercaFoglia(L);
CercaFine(L);
}
}
}
void PiuGrande(Lista L,int Posgrande[3]){//cerca prima il piu grande
register int l,c,lin,col,grande=0;//cerchiamo il "cavallo" piu grande!!cosi possiamo inserire altri nella sequenza giusta
grande=L->scacch[0][0];
lin=0;
col=0;
for(l=0;l < 8;l++){
for(c=0;c < 8;c++){
if(grande < L->scacch[l][c]){
grande=L->scacch[l][c];
lin=l;
col=c;
}
}
}
Posgrande[0]=lin;
Posgrande[1]=col;
Posgrande[2]=grande;
}
int InseriscePossibilita(Lista L,register int lin,register int col,int possib[9][3]){
register int l,c;
if(lin > 7||col > 7|| lin < 0|| col < 0)
return 0;
for(l=0;l < 9;l++){
for(c=0;c < 2;c++){
if(possib[l][c]== -1){
possib[l][0]=lin;
possib[l][1]=col;
l=20;
c=20;
}
}
}
}
int TamanhoPossi(int possi[9][3]){
register int l,c,cont=0;
for(l=0;l < 9;l++){
cont++;
for(c=0;c < 2;c++){
if(possi[l][c]==-1)
return --cont;
}
}
}
void setPosizioni(Lista L,int Poscav[9][9]){//serve per copiare la scacchiera
register int l,c;
for(l=0;l < 8;l++){
for(c=0;c < 8;c++){
Poscav[l][c]=L->scacch[l][c];
}
}
}
void getPosizioni(Lista L,int Poscav[9][9]){//trasferisce la scacchiera alla prossima per riprodurre i vari No
register int l,c;
for(l=0;l < 8;l++){
for(c=0;c < 8;c++){
L->scacch[l][c]=Poscav[l][c];
}
}
}
void Scacchiera(int mtx[9][9]){//crazione della scacchiera speciale per fare rifereimento tutte le volte que si vuole inserire il cavallo
register int l,c;
for(l=0;l < 8;l++){
for(c=0;c < 8;c++){
if(l == 0 || l == 7 || c == 0 || c == 7){
mtx[l][c]=1;
}else if(l == 1 || l == 6 || c == 1 || c == 6){
mtx[l][c]=2;
}else if(l == 2 || l == 5 || c == 2 || c == 5){
mtx[l][c]=3;
}else
mtx[l][c]=4;
}
}
}
int PrimaVerificazione(Lista L,register int l,register int c,int cav,int possib[9][3]){
int mtx[9][9],ct=0,k=l,y=c,m=0,x=3,i=0;//serve solo per encontrare le possibilita
Scacchiera(mtx);
while(i!= 2){
if( l+1 < 8 && c+1 < 8){
if(mtx[l+1][c+2]< x&& L->scacch[l+1][c+2]== 0 && l+1 >= 0 && c+2 >= 0 && l+1 < 8 && c+2 < 8){
InseriscePossibilita(L,l+1,c+2,possib);
m++;//serve per poter passar alla prossima verificazione di possibilita!
}
}
if(l+1 < 8 && c-2 >= 0){
if(mtx[l+1][c-2]< x&& L->scacch[l+1][c-2]==0 && l+1 >= 0 && c-2 >= 0 && l+1 < 8 && c-2 < 8){
InseriscePossibilita(L,l+1,c-2,possib);
m++;
}
}
if(l+2 < 8 && c+1 < 8 ){
if(mtx[l+2][c+1]< x&& L->scacch[l+2][c+1]==0 && l+2 >= 0 && c+1 >= 0 && l+2 < 8 && c+1 < 8){
InseriscePossibilita(L,l+2,c+1,possib);
m++;
}
}
if(l+2 < 8 && c-1 >= 0){
if(mtx[l+2][c-1]< x&& L->scacch[l+2][c-1]==0 && l+2 >= 0 && c-1 >= 0 && l+2 < 8 && c-1 < 8){
InseriscePossibilita(L,l+2,c-1,possib);
m++;
}
}
if(l-2 >= 0 && c+1 < 8){
if(mtx[l-2][c+1]< x&& L->scacch[l-2][c+1]==0 && l-2 >= 0 && c+1 >= 0 && l-2 < 8 && c+1 < 8){
InseriscePossibilita(L,l-2,c+1,possib);
m++;
}
}
if(l-2 >= 0 && c-1 >= 0){
if(mtx[l-2][c-1]< x&& L->scacch[l-2][c-1]==0 && l-2 >= 0 && c-1 >= 0 && l-2 < 8 && c-1 < 8){
InseriscePossibilita(L,l-2,c-1,possib);
m++;
}
}
if(l-1 >=0 && c+2 <= 8){
if(mtx[l-1][c+2]< x&& L->scacch[l-1][c+2]==0 && l-1 >= 0 && c+2 >= 0 && l-1 < 8 && c+2 < 8){
InseriscePossibilita(L,l-1,c+2,possib);
m++;
}
}
if(l-1 >=0 && c-2 >= 0){
if(mtx[l-1][c-2]< x&& L->scacch[l-1][c-2]==0 && l-1 >= 0 && c-2 >= 0 && l-1 < 8 && c-2 < 8){
InseriscePossibilita(L,l-1,c-2,possib);
m++;
}
}
i++;
if(m != 0)//caso abbia incontrato alcune possibilita si ferma
return 1;
if(i == 1)//caso abbia non abbia incontrato nessuna possibilita comincia un diverso cammino
x=5;
if(i == 2){//caso while gire 2 volte vuol dire che o ha incontrato il cammino oppure no)
// exit(1);
L->folha=1;
return 0;
}
}
}
//crear i vari No dell albero
int CreaBrother(Lista L,int num,int Poscav[9][9],int possib[9][3]){//Riceva la giusta quantita per poter criare I fratelli
int i=0,lin,col,Posgrande[3],cav,x=0;
while(i < num){//stabilisce la quantita giusta e insere i Brother con le nuove possizione incontrate
L=Brother(L);
L->B=1;
L->F=0;
getPosizioni(L,Poscav);
PiuGrande(L,Posgrande);
cav=Posgrande[2];
lin=possib[i][0];
col=possib[i][1];
Inserisce(L,lin,col,cav+1);
i++;
}
}
//crea i vari No dell albero
int CreaFather(Lista L,int num,int Poscav[9][9],int possib[9][3]){//Riceva la giusta quantita per poter criare I fratelli
int i=0,lin,col,Posgrande[3],cav,x=0;
while(i < num ){//stabilisce la quantita giusta e insere i Father con le nuove possizione incontrate
L=Father(L);
L->F=1;
L->B=0;
getPosizioni(L,Poscav);
PiuGrande(L,Posgrande);
cav=Posgrande[2];//prende l ultima posizione del cavallo per sapere appunto chji é il piu grande
lin=possib[i][0];//prende nella sequenzia le possibilita
col=possib[i][1];
Inserisce(L,lin,col,cav+1);
i++;
}
}
int InsereBrother(Lista L){
int Tam=0,Posgrande[3],ct=0,Poscav[9][9],possi[9][3],lin,col,cta=0,cav,x,c;
int l;
for(l=0;l < 27;l++)//numero -1 che il vetore conterra tutte le prime possibilita!!
*(possi[0]+l)=-1;
for(l=0;l < 81;l++)//numero -1 che il vetore conterra tutte le prime possibilita!!
*(Poscav[0]+l)=0;
setPosizioni(L,Poscav);
PiuGrande(L,Posgrande);
lin=Posgrande[0];
col=Posgrande[1];
cav=Posgrande[2];
PrimaVerificazione(L,lin,col,cav,possi);
Tam=TamanhoPossi(possi);
CreaBrother(L,Tam,Poscav,possi);
if(Tam == 0)
return 0;
else
return 1;
}
int InsereFather(Lista L){
int Tam=0,Posgrande[3],Poscav[9][9],lin,col,cav,possi[9][3];
int l;
for(l=0;l < 27;l++)//numero -1 che il vetore conterra tutte le prime possibilita!!
*(possi[0]+l)=-1;
for(l=0;l < 81;l++)//numero -1 che il vetore conterra tutte le prime possibilita!!
*(Poscav[0]+l)=0;
setPosizioni(L,Poscav);
PiuGrande(L,Posgrande);
lin=Posgrande[0];
col=Posgrande[1];
cav=Posgrande[2];
PrimaVerificazione(L,lin,col,cav,possi);
Tam=TamanhoPossi(possi);
CreaFather(L,Tam,Poscav,possi);
if(Tam == 0)
return 0;
else
return 1;
}
int CercaFine(Lista L){
int l,c,ct=0;
for(l=0;l < 8;l++){
for(c=0;c < 8;c++){
if(L->scacch[l][c]!= 0)
ct++;
}
}
if(ct == 64){
L->folha=1;
gfine++;
Mostrar(L);
return 1;
}else{
return 0;
}
}
int Inserisci_No(Lista L){
if( L->B == 1 && L->F == 0 && L->Father == NULL)
InsereFather(L);
if( L->F == 1 && L->B == 0 && L->Brother == NULL)
InsereBrother(L);
return 0;
}
int Euler(Lista L){
Inserisci_No(L);
if(L == NULL)
return 0;
if(L->folha == 0 && gnum < 1999999){//gnum quantita massima che puo raggiungere l albero
if(L->Brother!= NULL)
Euler(L->Brother);
if(L->Father != NULL )
Euler(L->Father);
}else
return 0;
}
int main(int argc, char *argv[])
{
Lista L;
int lin=0,col=0,l,c;
int cav=1;
L=Raiz(L);
printf(" As soluções encontradas forma de 334,316 para um total de 42 coordinadas do tabuleiro. \n As coordenadas que não foram encontradas estão logo abaixo: \n");
printf(" linha 0,coluna 4 \n linha 1,coluna 0 \n linha 1,coluna 3 \n linha 1,coluna 7 \n linha 2,coluna 0 \n linha 2,coluna 4 \n linha 2,coluna 6 \n linha 2,coluna 7 \n linha 3,coluna 0 \n linha 3,coluna 3 \n linha 3,coluna 6 \n linha 3,coluna 7 \n linha 4,coluna 0 \n linha 4,coluna 6 \n linha 5,coluna 6 \n linha 6,coluna 0 \n linha 6,coluna 2 \n linha 6,coluna 5 \n linha 6,coluna 6 \n linha 6,coluna 7 \n linha 7,coluna 3 \n linha 7,coluna 7\n");
do{
printf("\nDigite a posição da linha\n");
scanf("%d",&lin);
printf("Digite a posição da coluna\n");
scanf("%d",&col);
}while( lin > 7 || col > 7 ||lin < 0 || col < 0);
Inserisce(L,lin,col,cav);
InsereBrother(L);
Euler(L->Brother);
if(gfine == 0)
printf("Erro, Escolheo as coordenadas inválidas!\n");
system("PAUSE");
return 0;
}
</source>
== {{Ver também}} ==
*[[Problema das oito damas]]
| 