/*
 * Peg Soliteire
 *
 * conjugate でなければ 15 手、conjugate なら 18 手 (H.O.Davis)
 *
 * -------  board address for ------------
 *        program         solution diagram
 *        0  1  2               a b c
 *        3  4  5               d e f
 *  6  7  8  9 10 11 12     g h i j k l m
 * 13 14 15 16 17 18 19     n o p x P O N
 * 20 21 22 23 24 25 26     M L K J L H G
 *       27 28 29               F E D
 *       30 31 32               C B A
 */

#include <stdio.h>
#include <signal.h>
#include <time.h>

#define SIZE		33			/* # of holes */
#define MAX_MOVE	31			/* SIZE - 2 */

int jt[][SIZE] = {	/* jump table */
/* over, to, over, to, ..                       from */
  { 1, 2, 3, 8, -1},				/* 0 */
  { 4, 9, -1},					/* 1 */
  { 1, 0, 5, 10, -1},				/* 2 */
  { 4, 5, 8, 15, -1},				/* 3 */
  { 9, 16, -1},					/* 4 */
  { 4, 3, 10, 17, -1},				/* 5 */
  { 7, 8, 13, 20, -1},				/* 6 */
  { 8, 9, 14, 21, -1},				/* 7 */
  { 9, 10, 3, 0, 7, 6, 15, 22, -1},		/* 8 */
  { 10, 11, 4, 1, 8, 7, 16, 23, -1},		/* 9 */
  { 11, 12, 5, 2, 9, 8, 17, 24, -1},		/* 10 */
  { 10, 9, 18, 25, -1},				/* 11 */
  { 11, 10, 19, 26, -1},			/* 12 */
  { 14, 15, -1},				/* 13 */
  { 15, 16, -1},				/* 14 */
  { 16, 17, 8, 3, 14, 13, 22, 27, -1},		/* 15 */
  { 17, 18, 9, 4, 15, 14, 23, 28, -1},		/* 16 */
  { 18, 19, 10, 5, 16, 15, 24, 29, -1},		/* 17 */
  { 17, 16, -1},				/* 18 */
  { 18, 17, -1},				/* 19 */
  { 21, 22, 13, 6, -1},				/* 20 */
  { 22, 23, 14, 7, -1},				/* 21 */
  { 23, 24, 15, 8, 21, 20, 27, 30, -1},		/* 22 */
  { 24, 25, 16, 9, 22, 21, 28, 31, -1},		/* 23 */
  { 25, 26, 17, 10, 23, 22, 29, 32, -1},	/* 24 */
  { 18, 11, 24, 23, -1},			/* 25 */
  { 19, 12, 25, 24, -1},			/* 26 */
  { 28, 29, 22, 15, -1},			/* 27 */
  { 23, 16, -1},				/* 28 */
  { 24, 17, 28, 27, -1},			/* 29 */
  { 31, 32, 27, 22, -1},			/* 30 */
  { 28, 23, -1},				/* 31 */
  { 29, 24, 31, 30, -1}				/* 32 */
};

int b[SIZE] = {		/* board */
        1, 1, 1,
        1, 1, 1,
  1, 1, 1, 1, 1, 1, 1,
  1, 1, 1, 0, 1, 1, 1,
  1, 1, 1, 1, 1, 1, 1,
        1, 1, 1,
        1, 1, 1 };

int move[MAX_MOVE][3];	/* from, to, by */
char lastsol[65];	/* last solution */
int minmove;		/* minumum move */
char bestsol[65];	/* best solution */

int cnt = 0;		/* solution counter */
time_t start, end;

int vflg;
char *cmd;

main(argc, argv) char **argv;
{
  void onint();
  char *s;

  cmd = argv[0];
  while (--argc > 0 && (*++argv)[0] == '-')
	for (s = argv[0]+1; *s; s++)
		switch(*s) {
		case 'v':
			vflg++;
			break;
		default:
			Usage();
		}
  minmove = 32;
  time(&start);
  signal(SIGINT, onint);
  /* 対称解を除去するスマートな方法を思いつけない */
  forward(0, 4, 9, 16);	/* 4 からスタート */
  forward(1, 7, 8, 9);	/* 対称解のかなりを避ける */
  search(2);		/* 後は虱潰し */
  time(&end);		/* ここまでたどりついたことがない */
  printf("総数 %d 個, 時間 %d Sec\n", cnt, end - start );
  return 0;
}

/* バックトラックで n 回目の飛び越しから検索 */

search(n)
{
  int from, by, to, i;

  if (n == MAX_MOVE && b[16]) {
    /* move vector */
    outsol();
    /* move illustration */
    if (vflg)
	disp();
  }
  else {
    for (from = 0; from < SIZE; from++)
      if (b[from]) {
	for (i = 0; (by = jt[from][i++]) != -1; ) {
	  to = jt[from][i++];
	  if (b[by] && !b[to]) {	/* jumpable */
	    forward(n, from, by, to);
	    search(n + 1);
	    back(from, by, to);
	  }
	}
      }
  }
}

/* from から by を飛び越して to に移動 */

forward(n, from, by, to)
{
  b[from] = 0;
  b[by] = 0;
  b[to] = 1;
  move[n][0] = from;
  move[n][1] = to;
  move[n][2] = by;
}

/* to から by を埋めもどして from に戻る */

back(from, by, to)
{
  b[from] = 1;
  b[by] = 1;
  b[to] = 0;
}

/* 解の出力 */

outsol()
{
  int i, j, k, n;

  n = 32;
  for (i = 0; i < MAX_MOVE; i++) {
	k = move[i][0];
	lastsol[i*2] = (k == 16) ? 'x' : ((k < 16) ? k + 'a' : 32 - k + 'A');
	k = move[i][1];
	lastsol[i*2+1] = (k == 16) ? 'x' : ((k < 16) ? k + 'a' : 32 - k + 'A');
	if (0 < i && move[i-1][1] == move[i][0])
		n--;
  }
  lastsol[i*2] = '\0';
  printf("%d %d %s\n", ++cnt, n, lastsol);
  /* 最小手順解を更新 */
  if (n < minmove) {
	minmove = n;
	strcpy(bestsol, lastsol);
  }
}

void
onint()
{
  time(&end);
  printf("\nCurrent best solution in %d sec\n", end - start);
  printf("%d move: %s\n", minmove, bestsol);
  exit(0);
}

/* 以下、主としてデバック用 */

int bd[SIZE];

disp()
{
  int i, j, k;

  for (i = 0; i < SIZE; i++)
	bd[i] = 1;
  bd[16] = 0;
  dispbd();

  for (i = 0, j = 1; i < MAX_MOVE; i++, j++) {
    bd[move[i][0]] = bd[move[i][2]] = -1;
    bd[move[i][1]] = 1;
    dispbd();
    for ( ; j < MAX_MOVE; i++, j++) {
	if (move[i][1] != move[j][0])
	  break;
	bd[move[j][0]] = bd[move[j][2]] = -1;
	bd[move[j][1]] = 1;
	dispbd();
    }
  }
}

dispbd()
{
  int i, j, k;

  for (i = k = 0; i < 2; i++) {
    if (bd[k] == -1) {
	printf("     .");
	bd[k++] = 0;
    }
    else
	printf("     %d", bd[k++]);
    for (j = 0; j < 2; j++)
	if (bd[k] == -1) {
		printf(" .");
		bd[k++] = 0;
	}
	else
		printf(" %d", bd[k++]);
    printf("\n");
  }
  for (i = 0; i < 3; i++) {
    for (j = 0; j < 7; j++)
	if (bd[k] == -1) {
		printf(" .");
		bd[k++] = 0;
	}
	else
		printf(" %d", bd[k++]);
    printf("\n");
  }
  for (i = 0; i < 2; i++) {
    if (bd[k] == -1) {
	printf("     .");
	bd[k++] = 0;
    }
    else
	printf("     %d", bd[k++]);
    for (j = 0; j < 2; j++)
	if (bd[k] == -1) {
		printf(" .");
		bd[k++] = 0;
	}
	else
		printf(" %d", bd[k++]);
    printf("\n");
  }
  printf("\n");
}

Usage()
{
  static char *t[] = {
"コマンド	%s - Peg Solitaire を解く",
"構文		%s [-v]",
"得られた解を「解番号 手数 ペグの移動順」で表示しますが、移動順は下記の座標系",
"に置ける移動元と移動先の2文字の連続で表示しています。",
"         a b c",
"         d e f",
"     g h i j k l m",
"     n o p x P O N",
"     M L K J I H G",
"         F E D",
"         C B A",
"例えば、「ex」は「e を j 超しに x に移動」という意味です。-v を指定するとこれ",
"らの移動を図示し、Ctrl-C で打ち切ると、それまでの最小手数の解の1つを表示して",
"終了します。"
  };
  int i;

  for (i = 0; t[i] != NULL; i++) {
	fprintf(stderr, t[i], cmd);
	fprintf(stderr, "\n");
  }
  exit(1);
}