// ********************** //
// Parcours du cavalier //
// ********************** //
#include <stdio.h>
#include <stdlib.h>
// for sleep() :
#include <windows.h>
// choix langue fr/en
//#define ENLANG 1
// dim max de l'echiquier
#define NMAX 54
// NCOUP = NMAX^2
#define NCOUP (NMAX*NMAX)
// nombre de deplacements maxi du sauteur 8*MAXCOMB
#define MAXMOVE 32
// max deltax,deltay du sauteur
#define MAXD 5
// largeur tableau bordé de flags, de preference une puissance de 2
#define MAXW (NMAX + 2*MAXD)
// premier indice utile
#define I0 (MAXD*(MAXW+1))
// table des valeurs
// case (i,j) index (MAXD+i)*MAXW + MAXD + j = I0 + i*MAXW + j
// bit 64 = occupé, bit 128 = hors champ (le reste = valeur <= MAXMOVE)
int f[MAXW*MAXW];
int ik[NCOUP]; // position des coups (indice dans f[])
int xk[NCOUP]; // choix du keme coup (indice dans x0k[k])
// liste triée des coups possibles
int x0k[NCOUP][MAXMOVE]; // déplacement
int f0k[NCOUP][MAXMOVE]; // valeur
int circ; // flag solution fermee
int imax; // dimensions utilisées
int jmax;
int kmax; // nbre de coups = imax*jmax
int maxsol; // nbre de solutions a chercher
int nbsol; // nb de sol trouvees
int btrack; // flag si retour en arriere
int trac; // mode trace
int kabrt; // min du retour en arriere
// tables des sauteurs
char *nom[] = {
#ifdef ENLANG
" leaper",
" knight (1,2)",
" (0,3)(2,2) leaper",
" giraffe (1,4)",
" zebre (2,3)",
"n antelope (3,4)"
#else
" sauteur",
" cavalier (1,2)",
" sauteur (0,3)(2,2)",
"e girafe (1,4)",
" zebre (2,3)",
"e antilope (3,4)"
#endif
};
// nombre max de combinaisons de sauteurs simples
#define MAXCOMB 4
// table des sauts du sauteur
// nb,x,y,[x,y]* nb paires x,y, au maximum MAXCOMB paires
int ts[][(2*MAXCOMB+1)] = {
{0,0,0,0,0,0,0,0,0}, // libre (user defined)
{1,1,2,0,0,0,0,0,0}, // cavalier
{2,0,3,2,2,0,0,0,0}, // sauteur
{1,1,4,0,0,0,0,0,0}, // girafe
{1,2,3,0,0,0,0,0,0}, // zebre
{1,3,4,0,0,0,0,0,0} // antilope
};
// choix du sauteur, indice dans les tableaux precedents
int typ;
// valeur des sauts (offsets dans tableau f[])
int di[MAXMOVE];
// nb de déplacements possibles de ce sauteur
int nd;
// prototypes
// **********
void inif(void);
int minmove(int k);
void restore(int i, int k);
int other(int k);
void edit(int k);
int closed();
void getargs(int argc, char *argv[]);
void help(int full);
// programme principal
// *******************
int main(int argc, char *argv[]) {
int k; // numero du coup
int r; // mini trouvé
int dx,dy;
// valeurs par defaut
ik[0] = I0; // démarre case 0,0
imax=8; // echiquier normal
jmax=8;
circ=0; // solution ouverte
maxsol=1; // 1 seule solution
typ=1; // cavalier ordinaire
trac=0; // no trace
kabrt=0;
getargs(argc, argv); // parametres d'appel
kmax=imax*jmax; // nbre de cases = nb de coups
inif(); // init tableaux
k=0; // 1er coup
btrack=0; // raz flag retour arriere
nbsol=0; // nb solutions trouvees
do { // tant qu'on est pas revenu en arriere jusqu'au coup 0
do { // tant qu'on peut avancer
k++;
r=minmove(k); // si min = 0 fini ou bloqué, si min=MAXMOVE=8 on est bloqué
} while (r!=0 && r!=MAXMOVE);
if (r==0 && k>=kmax-1) { // solution trouvée
// ici test conditions particulières
if (circ==0 || closed())
edit(k);
if (nbsol>=maxsol) break; // limite nombre de solutions
}
// retour en arriere coup k mauvais, ou suite apres une solution trouvee
btrack=1;
// tant qu'il n'existe plus de choix pour ce coup, retourner en arriere, sinon autre choix
do { // tant qu'il faut retourner en arriere
if (r!=MAXMOVE) restore(ik[k-1],k);
r=0;
k--;
} while (k>0 && other(k)<0);
} while (k>0 && k>kabrt);
#ifdef ENLANG
if (nbsol==0) fprintf(stderr,"\nNo solution found\n");
else if (nbsol>1) fprintf(stderr,"\n%d solutions found\n",nbsol);
else fprintf(stderr,"\nfinished\n");
#else
if (nbsol==0) fprintf(stderr,"\npas de solution trouvees\n");
else if (nbsol>1) fprintf(stderr,"\n%d solutions trouvees\n",nbsol);
else fprintf(stderr,"\nfini\n");
#endif
if (argc<2) { // si appel sans parametres
help(0);
sleep(3000);
}
return 0; // ok
} // main()
// sous programmes
// ***************
// Init de f[] et d[]
void inif(void) {
int i,j,k,x,nf;
// init table de déplacements d[]
nd=0; //nb de deplacements
// pour chaque paire de coordonnees de saut
for (k=ts[typ][0]; k>0; k--) {
i = ts[typ][2*k-1];
j = ts[typ][2*k]; // ici 0<=i<=j par definition de la table ts[]
do { // pour i,j et j,i
do { // pour i et -i
do { // pour j et -j
// deplacement i,j a compter
di[nd++] = i*MAXW + j;
j=-j;
} while (j<0); // j,-j si j!=0
i=-i;
} while (i<0); // i,-i si i!=0
x=i; i=j; j=x; // echange i,j
} while (i>j); // deux valeurs (i,j) et (j,i) si i!=j
} // for paires k
// init table f[] des valeurs des cases
// bordures
for(i=0; i<MAXW*MAXD; i++) f[i]=128; // bord supérieur
for(j=0;j<imax; j++) { // partie utile, imax lignes
for (k=0; k<MAXD; k++) { f[i]=128; i++; } // bord gauche
for (k=0; k<jmax; k++) { f[i]=0; i++; } // partie utile, jmax colonnes
for (; k<NMAX+MAXD; k++) { f[i]=128; i++; } // bord droite
}
for (; i<MAXW*MAXW; i++) f[i]=128; // bord inférieur
// valeurs des cases
for (i=0; i<imax; i++) {
for (j=0; j<jmax; j++) {
nf=0;
k = I0 + i*MAXW + j;
// compte les deplacements possibles depuis cette case
for (x=0; x<nd; x++) {
if (f[k+di[x]]<=MAXMOVE) nf++;
} // for x
f[k]=nf;
if (nf==0) {
#ifdef ENLANG
fprintf(stderr,"\nUnreachable square %d,%d\nNo solution\n",i,j);
#else
fprintf(stderr,"\ncase %d,%d inaccessible\npas de solution\n",i,j);
#endif
exit(-1);
}
} // for j
} // for i
} // inif()
// recherche du coup minimal
// pour le coup k
// met a jour ik[], xk[], x0k[]
// retourne valeur min
// effet de bord : occupe la case précédente
int minmove(int k) {
int ni,j,u,min;
int i=ik[k-1]; // position précédente
// occupe i,j
f[i] |= 64; // flag case occupée
// raz liste triee des coups au rang k
xk[k]=0;
min=MAXMOVE; // flag aucune case accessible
for (u=0; u<nd; u++) { // pour chacun des sauts
ni=i+di[u]; // nouvelle case
if (f[ni]<=MAXMOVE) { // case libre
f[ni]--; // occupe case precedente, suite
// insere dans la liste triee
for (j=xk[k]; j>=0; j--) {
if (j==0 || (f0k[k][j-1] > f[ni]) ) {
// emplacement trouve
f0k[k][j]=f[ni];
x0k[k][j]=di[u];
break;
}
else { // shift
f0k[k][j] = f0k[k][j-1];
x0k[k][j] = x0k[k][j-1];
}
}
xk[k]++;
} // case libre
} // for u
if (xk[k]!=0) { // au moins une case trouvee
// la valeur mini est au rang xk[k]-1 dans la liste
min = f0k[k][xk[k]-1];
ik[k] = i+x0k[k][xk[k]-1];
}
return min;
} // minmove()
// Restaure les cases décrémentées à tort
// autour de la case i
// libere la case i
void restore(int i, int k) {
int u,ni,nj;
f[i] &= ~64; // libere
for (u=0; u<nd; u++) {
ni=i+di[u];
if ( f[ni]<=MAXMOVE) { // existe et libre
f[ni]++;
} // case libre
}
} // restore()
// autre choix
// pour la case k
// retourne -1 si pas de nouveau choix
int other(int k) {
int i,j,ni,nj,x;
ni = ik[k]; // case actuelle
i = ik[k-1]; // case précédente
f[ni] &= ~64; // libere
xk[k]--; // autre choix
if ( xk[k]==0 ) return -1; // plus de choix
// else
ik[k] = i + x0k[k][xk[k]-1]; // deplacement correspondant
return 0; // ok
} // other()
// edition d'une solution
void edit(int k) {
int i,j,ni,x;
nbsol++;
printf("\n%d :",nbsol);
#ifdef ENLANG
if (btrack==0) printf(" (immediate)");
#else
if (btrack==0) printf(" (immediat)");
#endif
for (i=0; i<imax; i++) {
printf("\n");
for (j=0; j<jmax; j++) {
ni = I0 + i*MAXW + j;
// recherche du coup
for (x=0; x<=k; x++) {
if (ik[x]==ni) break;
} // for
if (x<=k) printf(" %2d ", x);
else printf(" -- ");
} // for j
} // for i
printf("\n");
} // edit()
// test si solution fermée
int closed() {
int i,j,ni,nj,u;
i=ik[0];
ni=ik[kmax-1];
for (u=0; u<nd; u++) {
if (i==ni+di[u]) return 1;
}
return 0;
}
// Entree des parametres
// -d4x8 dimensions imax x jmax, par defaut = 8*8
// -f fermées, par defaut = ouvertes
// -(1,3) départ, par defaut 0,0, entre 0 et imax-1, jmax-1
// -n100 nbsols, par defaut 1
// -1 cavalier, -2 sauteur (0,3)(2,2), -3 girafe, -4 zebre, -5 antilope
// par defaut cavalier
//
// -h ? help
#ifdef ENLANG
#define ERRMSG "\nillegal parameter %s"
#else
#define ERRMSG "\nparametre illegal %s"
#endif
void getargs(int argc, char *argv[]) {
int i,j,ni,nj,x,y,jj;
char c;
char *p;
ni=0; nj=0;
for (i=1; i<argc; i++) {
c = argv[i][0];
if (c=='-' || c=='/') { // key
c=argv[i][1];
switch (c) {
case 'h' :
case 'H' :
help(1);
exit(0);
break;
case 'd' :
case 'D' :
imax=(int)strtol(argv[i]+2, &p, 10);
if (*p!='x' && *p!='X') {
fprintf(stderr,ERRMSG,argv [i]);
help(1);
exit(-1);
}
jmax=(int)strtol(p+1, &p, 10);
if (imax<3 || imax>NMAX || jmax<3 || jmax>NMAX || ni>=imax || nj>=jmax) {
fprintf(stderr,ERRMSG,argv [i]);
help(1);
exit(-1);
}
break;
case 'f' :
case 'F' :
circ=1;
break;
case '(' :
ni=(int)strtol(argv[i]+2, &p, 10);
if (*p!=',') {
fprintf(stderr,ERRMSG,argv [i]);
help(1);
exit(-1);
}
nj=(int)strtol(p+1, &p, 10);
if (ni<0 || ni>=imax || nj<0 || nj>=jmax || *p!=')') {
fprintf(stderr,ERRMSG,argv [i]);
help(1);
exit(-1);
}
ik[0] = I0 + ni*MAXW + nj;
break;
case 'n' :
case 'N' :
maxsol=(int)strtol(argv[i]+2, &p, 10);
if (maxsol<1) {
fprintf(stderr,ERRMSG,argv [i]);
help(1);
exit(-1);
}
break;
case '1' : // cavalier
case '2' : // sauteur
case '3' : // girafe
case '4' : // zebre
case '5' : // antilope
typ = c-'0';
break;
case 't' :
case 'T' :
trac=1;
kabrt=(int)strtol(argv[i]+2, &p, 10);
if (kabrt<0 || kabrt>kmax) {
fprintf(stderr,ERRMSG,argv [i]);
help(1);
exit(-1);
}
break;
case 's' : // sauteur generique
case 'S' :
typ = 0;
p=argv[i]+2; // 1ere '('
j=0;
while (*p == '(' && j<MAXCOMB) { // pour chaque paire de (x,y)
x = (int)strtol(p+1, &p, 10);
if (x<0 || x>MAXD || *p!=',') {j=0; break;}
y = (int)strtol(p+1, &p, 10);
if (y<0 || y>MAXD || *p!=')') {j=0; break;}
if (x<=y) { // tri x<=y
ts[0][2*j+1]=x; ts[0][2*j+2]=y;
}
else {
ts[0][2*j+1]=y; ts[0][2*j+2]=x;
}
x=ts[0][2*j+1]; y=ts[0][2*j+2]; // triee
for (jj=0; jj<j; jj++) { // verifie unicite
if (ts[0][2*jj+1]==x && ts[0][2*jj+2]==y) j=-1;
}
p++; // skip ')'
if (j<0) { j=0; break; } // erreur unicite
j++;
}
if (j==0 || *p!=0) {
fprintf(stderr,ERRMSG,argv [i]);
help(1);
exit(-1);
}
ts[0][0]=j; // nbre de sauts elementaires
break;
default :
fprintf(stderr,ERRMSG,argv [i]);
help(1);
exit(-1);
} // switch
} // if key
else if (c=='?') { help(1); exit(0); }
else { // not a key
fprintf(stderr,ERRMSG,argv [i]);
help(1);
exit(-1);
} // not a key
} // for i
#ifdef ENLANG
if (circ) printf("Closed p");
else printf("\nP");
printf("ath of a%s ",nom[typ]);
if (typ==0) { // sauteur generique
for (i=0; i<ts[0][0]; i++) {
printf("(%d,%d)",ts[0][2*i+1],ts[0][2*i+2]);
}
} // sauteur generique
printf(" on a %dx%d checkerboard, from(%d,%d)\n",imax,jmax,ni,nj);
#else
printf("\nParcours");
if (circ) printf(" fermes");
printf(" d'un%s ",nom[typ]);
if (typ==0) { // sauteur generique
for (i=0; i<ts[0][0]; i++) {
printf("(%d,%d)",ts[0][2*i+1],ts[0][2*i+2]);
}
} // sauteur generique
printf(" sur un echiquier %dx%d, depart(%d,%d)\n",imax,jmax,ni,nj);
#endif
} // getargs()
void help(int full) {
if (full) {
#ifdef ENLANG
fprintf(stderr,"\nKnight's tour");
fprintf(stderr,"\nParameters :");
fprintf(stderr,"\n -d8x8 Checkerboard size min 3x3 max %dx%d",NMAX,NMAX);
fprintf(stderr,"\n -(0,0) initial square");
fprintf(stderr,"\n -n1 max number of edited solutions");
fprintf(stderr,"\n -f closed paths");
fprintf(stderr,"\n -1 usual knight (1,2)");
fprintf(stderr,"\n 2 = (0,3)(2,2) leaper");
fprintf(stderr,"\n 3 = giraffe (1,4)");
fprintf(stderr,"\n 4 = zebra (2,3)");
fprintf(stderr,"\n 5 = antelope (3,4)");
fprintf(stderr,"\n -s(x,y)(x,y)... generic leaper %d moves maxi",MAXCOMB);
fprintf(stderr,"\n -t5 limit backtrack to move n\n");
#else
fprintf(stderr,"\nParcours du cavalier");
fprintf(stderr,"\nParametres :");
fprintf(stderr,"\n -d8x8 dimensions de l'echiquier min 3x3 max %dx%d",NMAX,NMAX);
fprintf(stderr,"\n -(0,0) case de depart");
fprintf(stderr,"\n -n1 nombre de solutions editees");
fprintf(stderr,"\n -f solutions fermees");
fprintf(stderr,"\n -1 cavalier ordinaire (1,2)");
fprintf(stderr,"\n 2 = sauteur (0,3)(2,2)");
fprintf(stderr,"\n 3 = girafe (1,4)");
fprintf(stderr,"\n 4 = zebre (2,3)");
fprintf(stderr,"\n 5 = antilope (3,4)");
fprintf(stderr,"\n -s(x,y)(x,y)... sauteur generique %d sauts maxi",MAXCOMB);
fprintf(stderr,"\n -t5 limite retour arrière au coup n\n");
#endif
}
else {
#ifdef ENLANG
fprintf(stderr,"\nParameters :\n -h help...");
#else
fprintf(stderr,"\nParametres :\n -h aide...");
#endif
}
}
|