codice:
#include <stdio.h>
#define LATOMATRICE 8
/* prototipi di funzione */
void inizializzaMatrice ( int a [][ LATOMATRICE ] );
void stampaMatrice ( int a [][ LATOMATRICE ] );
int percorriScacchiera ( int a [][ LATOMATRICE ], int b [ ], int c [ ], int d, int e, int f );
int main() {
int scacchiera [ LATOMATRICE ][ LATOMATRICE ];
int spostamentoOrizzontale [ LATOMATRICE ] = { 2, 1, -1, -2, -2, -1, 1, 2 };
int spostamentoVerticale [ LATOMATRICE ] = { -1, -2, -2, -1, 1, 2, 2, 1 };
/* ogni mossa del cavallo è a L; due caselle in una direzione orizz./vert. e
* una perpendicolare alla direttrice precedente. Gli spostamenti orizzontale
* SX e verticale in alto avranno valore negativo in quanto sulla matrice
* spostarsi in queste direzioni significa sottrarre unità dal valore della
* riga/colonna in cui ci si trova. Da un punto centrale della scacchiera
* (3,4) è possibile effettuare 8 mosse a L (da 0 a 7). Quindi la costante
* LATOMATRICE va bene anche per esprimere il numero di mosse del cavallo.
*/
int x = 0;
int y = 0;
/* coordinate di partenza del cavallo */
int mossaIniziale = 0;
int esito;
inizializzaMatrice ( scacchiera );
/* inizializzo tutta la scacchiera/matrice a -1, così da capire
* facilmente quando una casella è già stata visitata dal
* cavallo.
*/
esito = percorriScacchiera ( scacchiera, spostamentoOrizzontale, spostamentoVerticale, x, y, mossaIniziale );
printf ( "esito = %d\n", esito );
stampaMatrice ( scacchiera );
printf ( "\n" );
inizializzaMatrice ( scacchiera );
x = 3;
y = 4;
esito = percorriScacchiera ( scacchiera, spostamentoOrizzontale, spostamentoVerticale, x, y, mossaIniziale );
printf ( "esito = %d\n", esito );
stampaMatrice ( scacchiera );
printf ( "\n" );
inizializzaMatrice ( scacchiera );
x = 6;
y = 3;
esito = percorriScacchiera ( scacchiera, spostamentoOrizzontale, spostamentoVerticale, x, y, mossaIniziale );
printf ( "esito = %d\n", esito );
stampaMatrice ( scacchiera );
printf ( "\n" );
return 0;
}
void inizializzaMatrice ( int a [][ LATOMATRICE ] ) {
int x, y;
for ( x = 0; x < LATOMATRICE; x++ ) {
for ( y = 0; y < LATOMATRICE; y++ ) {
a [ x ][ y ] = -1;
}
}
}
void stampaMatrice ( int a [][ LATOMATRICE ] ) {
int x, y;
for ( x = 0; x < LATOMATRICE; x++ ) {
for ( y = 0; y < LATOMATRICE; y++ ) {
printf ( "%3d", a [ x ][ y ] );
}
printf ( "\n" );
}
}
int percorriScacchiera ( int a [][ LATOMATRICE ], int b [ ], int c [ ], int d, int e, int f ) {
/* a è la matrice scacchiera.
* b è il vettore spostamentoOrizzontale.
* c è il vettore spostamentoVerticale.
* d è il contatore x.
* e è il contatore y.
* f è la variabile mossaIniziale, indicante le mossa che il cavallo deve tentare
*/
static int contatore = 0;
/* necessario per tenere traccia dei movimenti del cavallo: aumenta
* di una unità ad ogni casella visitata e deve sopravvivere alle ricorsioni
*/
d += c [ f ];
e += b [ f ];
/* calcolo la posizione del cavallo alla luce della mossa rappresentata da f.
* d ed e rappresentano le coordinate del cavallo, riga e colonna.
*/
if (( d > LATOMATRICE - 1 || e > LATOMATRICE - 1 ) || ( d < 0 || e < 0 ) ||
/* se sono fuori dalla scacchiera */
( a [ d ] [ e ] > -1 )) {
/* OPPURE la prossima casella in cui si muoverà il cavallo è già stata visitata,
* tento un'altra strada
*/
d -= c [ f ];
e -= b [ f ];
/* in questo caso annullo gli effetti del precedente calcolo (d += c [ f ] etc.) per "riportare" il cavallo alle
* precedenti coordinate. Fatto ciò, posso tentare un'altra mossa, cioè la mossa f+1 (cioè se ad es. ho tentato in una data
* posizione della scacchiera la mossa 3 e quest'ultima mi ha portato fuori scacchiera, torno alla precedente posizione e
* ritento la mossa 4). In questo if avviene il passo ricorsivo.
*/
f++;
/* aumento d di una unità per tentare la mossa successiva
*/
if ( f > 7 ) {
/* in questo caso, significa che sono completamente bloccato. Cioè il cavallo non ha più mosse possibili da tentare, perchè tutte le
* precedenti o lo portavano fuori scacchiera o su caselle già visitate.
*/
contatore = 0;
/* se sono dentro a questo if significa che il cavallo ha fallito, quindi devo ripartire da nuove coordinate. Ovviamente il contatore
* va azzerato perchè altrimenti la prima mossa valida del successivo giro del cavallo non partirebbe da 0, ma da un valore più alto,
* rendendo il contatore stesso privo di senso, anche perchè non si riuscirebbe più a capire se il cavallo ha avuto successo o meno.
* L'unico modo per capirlo è quello di verificare che il contatore sia uguale a 64, cioè il numero di caselle della scacchiera. Se il
* contatore parte da un valore > 0, magari arriva a 64 prima che tutte le caselle siano state realm. visitate, e quindi il programma
* riscontrerebbe un falso successo.
*/
return 1;
}
percorriScacchiera ( a, b, c, d, e, f );
/* a è la matrice scacchiera.
* b è il vettore spostamentoOrizzontale.
* c è il vettore spostamentoVerticale.
* d è il contatore x.
* e è il contatore y.
* f è la variabile mossaIniziale, indicante le mosse che il cavallo deve tentare,
* in questo caso f varrà un'unità in più rispetto al precedente tentativo, stiamo
* cioè tentando una nuova mossa.
*/
}
else {
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 1 e 64
*/
if ( contatore == 63 ) {
/* se contatore vale 63 significa che il cavallo ha visitato con successo
* tutte le 64 caselle della scacchiera. Il contatore parte infatti da 0
* quindi da 0 a 63 sono 64 caselle.
*/
return 0;
}
contatore++;
f = 0;
/* se ho avuto successo, la mossa successiva sarà di nuovo la 0
*/
percorriScacchiera ( a, b, c, d, e, f );
/* in questo caso f (cioè la mossa compiuta) non viene aumentato, perchè la
* precedente mossa ha avuto successo (cioè cavallo dentro scacchiera e casella
* mai visitata). Di conseguenza, provo a fare la mossa successiva ripartendo da
* 0 e, in caso di insuccesso, proverò con la mossa 1.
*/
}
}
Output di esempio (3 scacchiere in cui il cavallo parte da posizioni differenti della scacchiera e dove non completa il giro; le caselle contrassegnate dal valore -1 non sono mai state visitate dal cavallo):
Rispondi quotando
