PDA

Visualizza la versione completa : [C] Implementazione "Giro del cavallo" e ricorsione


pastoreerrante
06-12-2010, 13:30
Ciao ragazzi,

sono alle prese con un classico: il giro del cavallo. Il cavallo deve visitare ogni casella della scacchiera una e una sola volta.

Il problema è che non riesco a fare effettuare al cavallo tutti i possibili tentativi. Mi spiego: da ogni casella è possibile effettuare 8 diverse mosse. L'algoritmo, a partire da due coordinate di partenza (riga e colonna della scacchiera), tenta tutte le mosse. Se la mossa porta il cavallo in una posizione valida della scacchiera (cioè è dentro la scacchiera e la casella non è già stata visitata) avviene la ricorsione, passando alla funzione le nuove coordinate della scacchiera in cui il cavallo si è spostato e così via. Sin qui tutto bene.

Il problema sorge quando il cavallo si trova in un vicolo cieco (cioè quando qualsiasi mossa lo porterebbe fuori scacchiera oppure su caselle già visitate). In questo caso, la funzione dovrebbe ritornare 1 e passare il controllo alla funzione chiamante, la quale a sua volta dovrebbe ritentare un'altra possibile strada a partire dalla mossa successiva a quella che aveva condotto il cavallo nel vicolo cieco. Ciò non avviene. Quando siamo nel vicolo cieco, il programma semplicemente si conclude e il risultato è che una marea di percorsi possibili non vengono tentati.

Questa è la funzione:



int percorriScacchiera ( int a [][ LATOMATRICE ], int b [ ], int c [ ], int d, int e ) {
/* a è la matrice scacchiera.
* b è il vettore spostamentoOrizzontale.
* c è il vettore spostamentoVerticale.
* d è il contatore x.
* e è il contatore y.
*/
static int contatore = 0;
/* necessario per tenere traccia dei movimenti del cavallo: aumenta
* di una unità ad ogni casella visitata.
*/
int i;
/* variabile di appoggio per ciclo for */

if ( contatore == 0 ) {

a [ d ][ e ] = contatore;
/* le coordinate di partenza del cavallo valgono come una casella visitata
*/
contatore++;

}

for ( i = 0; i <= 7; i++ ) {

d += c [ i ];
e += b [ i ];
/* calcolo la posizione del cavallo alla luce della mossa rappresentata da i.
* d ed e rappresentano le coordinate del cavallo, riga e colonna.
*/

if (( d >= 0 && e >= 0 ) && ( d <= LATOMATRICE - 1 && e <= LATOMATRICE - 1 ) &&
/* SE sono dentro la scacchiera (ciò si verifica se il valore di d ed e
* è >= 0 e <= 7 - condizioni entrambe vere
*/
( a [ d ][ e ] == -1 )) {
/* E INOLTRE la prossima casella in cui si muoverà il cavallo non è mai stata visitata
* (ciò si verifica quando il valore della casella == -1, continuo il giro partendo dalle
* nuove coordinate appena calcolate dalla mossa 0.
*/

a [ d ][ e ] = contatore++;
/* se le nuove coordinate della posizione del cavallo sono accettabili
* (cioè se risultano dentro la scacchiera e se la casella non è mai stata
* visitata), andrò a printare nella casella un intero compreso fra 0 e 63
*/

if ( contatore == 63 ) {
/* se il cont. arriva a 63 significa che il giro è stato completato con successo
* quindi esco dal for e vado a concludere il programma
*/
break;

}

return percorriScacchiera ( a, b, c, d, e );
/* qui avviene la ricorsione. Se ho individuato coordinate accettabili, dalla nuova posizione
* del cavallo tento le altre 8 possibili mosse
*/

}

if ( i == 7 ) {
/* questo if gestisce l'evento "vicolo cieco". Significa che, date le attuali coordinate, il
* cavallo non può più proseguire perchè o andrebbe fuori scacchiera oppure tutte le altre
* possibili caselle di arrivo sarebbero già state visitate. In questo caso l'unica possibilità
* è riportare il cavallo alle precedenti coordinate e tentare con la mossa successiva a quella
* che lo aveva condotto nel vicolo cieco.
*/

contatore--;
/* se sono in un vicolo cieco, significa che devo ricominciare il giro dalle coordinate PRECEDENTI
* a quelle a partire dalle quali mi sono ritrovato bloccato. Tuttavia devo anche decrementare di 1
* il contatore delle caselle visitate perchè l'ultima casella su cui il cavallo si era legalmente
* posizionato non può più essere considerata "visitata", in quanto il cavallo deve tornare sui propri
* passi, cioè su una casella già visitata, cosa nel gioco del giro del cavallo non è ammessa: il cavallo
* può stare su una casella una e una sola volta.
*/


/* Inserire istruzioni per trasformare in -1 la casella da cui ha avuto origine del vicolo cieco */
/* per le stesse motivazioni del commento precedente la casella deve tornare "vergine", come se non fosse
* mai stata visitata, quindi deve tornare a valere -1.
*/

stampaMatrice ( a );

return 1;
/* ritornare 1 significa che il cavallo è in un vicolo cieco. Tramite questa istruzione il controllo
* del flusso del programma ritorna alla funzione chiamante, ovvero sempre percorriScacchiera visto che
* siamo in un contesto ricorsivo.
*/

}

d -= c [ i ];
e -= b [ i ];
/* se la mossa non ha avuto successo ma NON SONO ANCORA IN UN VICOLO CIECO, ritento la mossa successiva dalle
* stesse coordinate che mi hanno condotto ad una posizione non valida. Questo si verifica sino a quando tutte 8
* le mosse possibili non sono state tentate. Per riportarmi sulle coordinate corrette devo però annullare gli
* effetti del calcolo (d += c [ i ] ed e += b [ i ]) che aveva portato il cavallo fuori scacchiera o su posizione
* già visitata .
*/

}

return 0;

}


Evidentemente interpreto male il meccanismo della ricorsione.

Come posso risolvere?

Grazie

mangler666
07-12-2011, 21:26
ho creato un programmino che risolve il "giro del cavallo" in c++, andate nel sito <NO SPAM> sezione download per scaricarlo... nella sezione forum del sito ho postato anke il codice che lo risolve!

alka
08-12-2011, 01:20
Originariamente inviato da mangler666
ho creato un programmino che risolve il "giro del cavallo" in c++, andate nel sito <NO SPAM> sezione download per scaricarlo... nella sezione forum del sito ho postato anke il codice che lo risolve!

Risollevare una discussione vecchia, che chiede aiuto su un problema, per postare il link a un eseguibile non serve a nessuno.

Loading