[C] - Programma gioco del cavallo di eulero!!!

[marco83pt]

Qualcuno conosce questo rompicato matematico?
E' tratta di far percorrere un intera scacchiera 8x8 ad un cavallo (mossa ad L), toccando una sola volta ogni singola casella. E' giorni che sto impazzendo per fare un programma in C che accetti in ingresso la casella di partenza, e mi dia come output la sequenza di mosse...
Ho provato ad usare la tecnica della Ricorsione ed con un ciclio for...che quando trova una strada bloccata torna indietro finche non prova una seconda via libera...
ma il programma mi "blocca" quando trova la via cieca e mi tira fuori dei risultati insensati...

qualcuno ha un programma in C che faccia questo lavoro, almeno da prendere per spunto.

Grazie, Saluti, Marco.

[Gregory_House]

Ciao, prova a effettuare una marcatura delle caselle già visitate ed ad utilizzare la tecnica del backtracking, di modo che se capiti in un vicolo cieco torni automaticamente all'ultimo punto in cui hai effettuato una scelta e da li scegli un'altra via.

[marco83pt]

Purtroppo le mie conoscenze di C non sono molto evolute, e non conosco la tecnica "tecnica del backtracking". Il problema sta nel fatto che quando torno indietro dalla casella a vicolo chiedo quella mi viene cancellata, mentre la prima ancora no...questo fatto mi sbarella tutto l'agoritmo che ho fatto, poichè vede tale casella come occupata e mi esce del gioco senza darmi una soluzione "esatta".

[ndakota]

qua c'è un 3d che avevo aperto io un po di tempo fa.. spero possa esserti utile.. http://www.hwupgrade.it/forum/showthread.php?t=1782141

[marco83pt]

qua c'è un 3d che avevo aperto io un po di tempo fa.. spero possa esserti utile.. http://www.hwupgrade.it/forum/showthread.php?t=1782141

esatto, sto proprio studiando quel libro.ti ringrazio per la dritta...ci do un'occhiata.
grazie ancora.

[marco83pt]

ho letto, ti ringrazio per l'aiuto....
ma sto cercando di far percorrere al cavallo l'intera scacchiera.

[marco83pt]

Ciao, prova a effettuare una marcatura delle caselle già visitate ed ad utilizzare la tecnica del backtracking, di modo che se capiti in un vicolo cieco torni automaticamente all'ultimo punto in cui hai effettuato una scelta e da li scegli un'altra via.

Qualcuno mi può indicare una guida per la tecnica backtracking???

[banryu79]

Potrebbe interessarti questo articolo (http://www.devarticles.com/c/a/Development-Cycles/The-Backtracking-Algorithm-Technique/)?

[marco83pt]

Ora do un occhiata all'articolo.
Il mio dilemma è questo.


Quando torno indietro nelle prove (utilizzando la ricorsività delle funzioni), perdo le informazioni sulle caselle visitate, poichè se una iterazione è nulla devo cancellare le caselle fino al punto dove ho una scelta multipla.
Se creo una matrice Nx2 ci salvo le informazioni per ogni passo, ma poi indice che mi tiene conto del passo mi si modifica, e non posso più sapere la tot posizione a che indice corrisponde.

[marco83pt]

Finalmente la soluzione....
spero chi si vuole divertira mi possa correggere qualche inesattezza...
comunque funziona.



#include <stdio.h>
#define SIZE 8
void matrixp (int f[ SIZE ][ SIZE ]); // scrittura a video della board
int ct (int board[ SIZE ][ SIZE ]); // ct:controllo terminazione
int cn (int board[ SIZE ][ SIZE ]); // cn:controllo numeri
int cp (int board[ SIZE ][ SIZE ],int rc,int cc); // cp: controllo di passo
void tt (int board[ SIZE ][ SIZE ],int rc,int cc,int p); // tt: trova totale (funzione principale)
int hor[ 8 ] = { 2 , 1 , -1 , -2 , -2 , -1 , 1 , 2 }; //vettore mosse orizzontali
int ver[ 8 ] = { -1 , -2 , -2 , -1 , 1 , 2 , 2 , 1 }; //vettore mosse verticali
int main() {
int board[ SIZE ][ SIZE ] = {{ 0 },{ 0 }};
int rc,cc;
rc = 1;
cc = 1;
board[ rc ][ cc ] = 1;
tt(board,rc,cc,1);
matrixp(board);
return (0);
}
int ct (int board[ SIZE ][ SIZE ]) {
int i,j,e;
e = 0;
for(i = 0;i < SIZE; ++i) {
for(j = 0;j < SIZE; ++j) {
if(board[ j ][ i ] == 0)
e = 1;
}
}
return(e); // e=1 INCOMPLETA ; e=0 COMPLETA
}
int cn (int board[ SIZE ][ SIZE ]) {
int i,j,n;
n = 0;
for(i = 0;i < SIZE; ++i) {
for(j = 0;j < SIZE; ++j) {
if(board[ j ][ i ] != 0)
++n;
}
}
return(n);
}

int cp(int board[ SIZE ][ SIZE ],int rc,int cc) {
int e = 1;
if(rc < SIZE && rc >= 0 && cc < SIZE && cc >= 0 && board[ rc ][ cc ] == 0) {
e = 0;
}
return(e); // e=1 NEGATO ; e=0 CONSENTITO
}
void matrixp (int f[ SIZE ][ SIZE ]){
int i,j;
for(i = 0;i < SIZE; ++i) {
for(j = 0; j < SIZE; ++j) {
printf("%d\t",f[ i ][ j ]);
if(j == SIZE - 1)
printf("\n");
}
}
} // restituisce a video la board
void tt (int board[ SIZE ][ SIZE ], int rc, int cc,int p) {
int r,trc,tcc,tp;
tp = p;
for(r = 0;r < 8; ++r) {
trc = rc + ver[ r ];
tcc = cc + hor[ r ];
if(cp(board,trc,tcc) == 0) {
board[ trc ][ tcc ] = ++p;
if(p == 64)
break;
tt(board,trc,tcc,p);
}
if(r == 7) {
board[ rc ][ cc ] = 0;
}
p = tp;
}
}