/* cavalier.c
 * 
 * Jean-Paul Davalan <jpdvl@wanadoo.fr>
 * 
 * Parcours du cavalier sur un échiquier
 *
 * Cycles hamiltoniens dans un graphe
 *
 * compilation :
 *   gcc -O2 -o cavalier cavalier.c
 * usage : 
 *   Pour un échiquier de 8x8 cases faire
 *   cavalier 8
 */
#include<stdio.h>
#include <stdlib.h>
#include <time.h>
#define DIF dif_cv   // cv: cavalier
// #define DIF dif_ct // ct casse-tête
#define NMAX 12 // nbre MAX de cases horiz. et vert.

int     N = 5, NN,	  // nbre MAX de cases horiz. et vert.
        num = 0,	  // nbre de solutions
        quiet = 0,	  // = 1 n'affiche pas
        quad[NMAX][NMAX]; // tableau, damier, échiquier
/* déplacements relatifs en x ou en y */ 
int    dif_ct[8][2] =    /* casse-tête */
  {{3,0},{2,2},{0,3},{-2,2},{-3,0},{-2,-2},{0,-3},{2,-2}};
int    dif_cv[8][2] =	 /* déplacements du cavalier */
  {{2,1},{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2},{1,-2},{2,-1}};

void solution()
{
  int i, j;
  printf("# %d\n", num);
  for (i = 0; i < N; i++) {
    printf("    ");
    for (j = 0; j < N; j++) printf("%3d", quad[i][j] - 1);
    printf("\n");
  }
  printf("\n");
}

void  next(int n, int x, int y)	/* position suivante */
{
  int  k, X, Y;
  quad[x][y] = n;
  if (n < NN) {
    for (k = 0; k < 8; k++) {
      X = x + DIF[k][0], Y = y + DIF[k][1];
      if (X >= 0 && X < N && Y >= 0 && Y < N && quad[X][Y] == 0) 
	next(n + 1, X, Y);
    }
  } else if (n == NN) {		/* affichage de la solution  */
    num++;
    if (!quiet || num <= 1) solution();
  }
  quad[x][y] = 0;
}

int main(int argc, char *argv[])
{
  int i, j;
  long long c_begin = (long long)clock();
  if (argc > 1) N = atoi(argv[1]);
  N = (N <= NMAX) ? N : 5;
  NN = N * N;
  if (argc > 2 && *argv[2] == 'q') quiet = 1;
  printf("# Solutions du casse-tête %dx%d\n", N, N);
  for (i = 0; i < N; i++)
    for (j = 0; j < N; j++) quad[i][j] = 0;
  next(1, 0, 0);
  printf("# %d solutions  (%Ld s)\n\n", 
    num,(clock()-c_begin)/CLOCKS_PER_SEC);
  return 0;
}