#include#include #define MAX 20 /* (lato matrice di lavoro) >= lato+2*bordo*/ #define BORDO 2 /* il bordo da non oltrepassare */ #define LATO 8 /* la dimensione effettiva della scacchiera*/ typedef struct { int A, B, Ragg; } work; /*la casella con coordinate e raggiungibilità*/ typedef work MWorking[8]; /* tutte le caselle attualmente raggiungibili*/ int MOSSA[8][2] = /* la descrizione del passo del nostro animale*/ { {-2, -1}, {-2, +1}, {-1, -2}, {-1, +2}, {+1, -2}, {+1, +2}, {+2, -1}, {+2, +1} }; int SCACCHIERA[MAX][MAX], DIMSC =LATO+BORDO+BORDO, /* la scacchiera pi— il bordo*/ ULTIMO=LATO*LATO; /* numero caselle da occupare*/ work temp; /* usata nella fase di ordinamento*/ void muovi(int n, int x, int y), init(void), outsol(void); int main(void) { init(); /* muovi(1, BORDO+random(LATO), BORDO+random(LATO)); pos. start casuale*/ muovi(1, BORDO+1, BORDO+1); /*pos. start 1,1*/ return(0); } void muovi(int n, int X, int Y) { int i, j, /* indici di scorrimento*/ A, B; /* le coordinate temporanee*/ MWorking M; /* le mosse possibili attuali*/ if(n == ULTIMO) { outsol(); } else /* per ogni mossa calcolo coordinate(A,B) e indice di raggiungibilità (Ragg)*/ for(i=0; i < 8; ++i) { M[i].A =X+MOSSA[i][0]; M[i].B =Y+MOSSA[i][1]; M[i].Ragg=0; A=M[i].A; B=M[i].B; if(SCACCHIERA[A][B] == 0) { for(j=0; j < 8; ++j) { if(SCACCHIERA[A+MOSSA[j][0]][B+MOSSA[j][1]] == 0) { ++M[i].Ragg; } } } } /*ordino le mosse per indice di raggiungibilità*/ for(i=0; i < 8; ++i) { for(j=i+1; j < 8; ++j) { if(M[i].Ragg > M[j].Ragg) { temp=M[i]; M[i]=M[j]; M[j]=temp; } } } /*Eseguo le mosse in ordine*/ for(i=0; i < 8; ++i) { if(M[i].Ragg > 0) { A=M[i].A; B=M[i].B; SCACCHIERA[A][B]=n; muovi(n+1, A, B); SCACCHIERA[A][B]=0; } } } } void init(void) { int i, j; for(i=0; i < DIMSC; ++i) { for(j=0; j < DIMSC; ++j) { if(i < BORDO || i >= DIMSC-BORDO || j < BORDO || j >= DIMSC-BORDO) { SCACCHIERA[i][j] = -1; /*Il bordo inaccessibile*/ } else { SCACCHIERA[i][j] = 0; /*La scacchiera da occupare*/ } } } /*randomize();*/ //clrscr(); } void outsol(void) { int i, j; printf("\n"); /*gotoxy(1, 1);*/ for(i=0; i < DIMSC; ++i) { for(j=0; j < DIMSC; ++j) { printf("%3d", SCACCHIERA[i][j]); } printf("\n"); } getchar(); }
Problema del brocco
Le mosse possibili sono diverse...
int MOSSA[8][2] = { {-3, +0}, {+3, +0}, {-2, -2}, {-2, +2}, {+2, -2}, {+2, +2}, {+0, -3}, {+0, +3} };
e di conseguenza il bordo della scacchiera ha dimensione 3
#define BORDO 3