#include <stdio.h>
#include <string.h>

int search(int, char *, int);
void show_solution();
char *position_name(int);

/*
 * l m n o p q r
 *  f g h i j k
 *   a b c d e
 *    6 7 8 9
 *     3 4 5
 *      1 2
 *       0
 */

struct move {
	char *mesg;
	int before;
	int after;
};

/* first row */
#define PEG_0 0x00000001
/* second row */
#define PEG_1 0x00000002
#define PEG_2 0x00000004
/* third row */
#define PEG_3 0x00000008
#define PEG_4 0x00000010
#define PEG_5 0x00000020
/* fourth row */
#define PEG_6 0x00000040
#define PEG_7 0x00000080
#define PEG_8 0x00000100
#define PEG_9 0x00000200
/* fifth row */
#define PEG_A 0x00000400
#define PEG_B 0x00000800
#define PEG_C 0x00001000
#define PEG_D 0x00002000
#define PEG_E 0x00004000

#if defined(BOARD6) || defined(BOARD7)
/* sixth row */
#define PEG_F 0x00008000
#define PEG_G 0x00010000
#define PEG_H 0x00020000
#define PEG_I 0x00040000
#define PEG_J 0x00080000
#define PEG_K 0x00100000
#endif

#if defined(BOARD7)
/* seventh row */
#define PEG_L 0x00200000
#define PEG_M 0x00400000
#define PEG_N 0x00800000
#define PEG_O 0x01000000
#define PEG_P 0x02000000
#define PEG_Q 0x04000000
#define PEG_R 0x08000000
#endif

#ifdef BOARD5
#define BOARD (PEG_0 | PEG_1 | PEG_2 | PEG_3 | PEG_4 | PEG_5 | PEG_6 | PEG_7 | PEG_8 | PEG_9 | PEG_A | PEG_B | PEG_C | PEG_D | PEG_E)
#define NSTEPS 15
#endif

#ifdef BOARD6
#define BOARD (PEG_0 | PEG_1 | PEG_2 | PEG_3 | PEG_4 | PEG_5 | PEG_6 | PEG_7 | PEG_8 | PEG_9 | PEG_A | PEG_B | PEG_C | PEG_D | PEG_E | PEG_F | PEG_G | PEG_H | PEG_I | PEG_J | PEG_K) 
#define NSTEPS 21
#endif

#ifdef BOARD7
#define BOARD 0x0fffffff
#define NSTEPS 28
#endif

#ifndef BOARD
#error You must define one of BOARD5 BOARD6 or BOARD7
#endif

#define P0_EMPTY (BOARD & (~PEG_0))
#define P1_EMPTY (BOARD & (~PEG_1))
#define P3_EMPTY (BOARD & (~PEG_3))
#define P4_EMPTY (BOARD & (~PEG_4))
#define P6_EMPTY (BOARD & (~PEG_6))
#define P7_EMPTY (BOARD & (~PEG_7))
#define PC_EMPTY (BOARD & (~PEG_C))

struct move possible_moves[] = {
	{ "0 jumps 1 to 2", (PEG_0 + PEG_1), PEG_2 },
	{ "0 jumps 2 to 5", (PEG_0 + PEG_2), PEG_5 },

	{ "1 jumps 3 to 6", (PEG_1 + PEG_3), PEG_6 },
	{ "1 jumps 4 to 8", (PEG_1 + PEG_4), PEG_8 },

	{ "2 jumps 4 to 7", (PEG_2 + PEG_4), PEG_7 },
	{ "2 jumps 5 to 9", (PEG_2 + PEG_5), PEG_9 },

	{ "3 jumps 1 to 0", (PEG_3 + PEG_1), PEG_0 },
        { "3 jumps 4 to 5", (PEG_3 + PEG_4), PEG_5 },
	{ "3 jumps 7 to c", (PEG_3 + PEG_7), PEG_C },
	{ "3 jumps 6 to a", (PEG_3 + PEG_6), PEG_A },

	{ "4 jumps 7 to b", (PEG_4 + PEG_7), PEG_B },
	{ "4 jumps 8 to d", (PEG_4 + PEG_8), PEG_D },

	{ "5 jumps 2 to 0", (PEG_5 + PEG_2), PEG_0 },
	{ "5 jumps 4 to 3", (PEG_5 + PEG_4), PEG_3 },
	{ "5 jumps 8 to c", (PEG_5 + PEG_8), PEG_C },
	{ "5 jumps 9 to e", (PEG_5 + PEG_9), PEG_E },

	{ "6 jumps 3 to 1", (PEG_6 + PEG_3), PEG_1 },
	{ "6 jumps 7 to 8", (PEG_6 + PEG_7), PEG_8 },
#if defined(BOARD6) || defined(BOARD7)
	{ "6 jumps b to h", (PEG_6 + PEG_B), PEG_H },
	{ "6 jumps a to f", (PEG_6 + PEG_A), PEG_F },
#endif

	{ "7 jumps 4 to 2", (PEG_7 + PEG_4), PEG_2 },
	{ "7 jumps 8 to 9", (PEG_7 + PEG_8), PEG_9 },
#if defined(BOARD6) || defined(BOARD7)
	{ "7 jumps c to i", (PEG_7 + PEG_C), PEG_I },
	{ "7 jumps b to g", (PEG_7 + PEG_B), PEG_G },
#endif

	{ "8 jumps 4 to 1", (PEG_8 + PEG_4), PEG_1 },
	{ "8 jumps 7 to 6", (PEG_8 + PEG_7), PEG_6 },
#if defined(BOARD6) || defined(BOARD7)
	{ "8 jumps c to h", (PEG_8 + PEG_C), PEG_H },
	{ "8 jumps d to j", (PEG_8 + PEG_D), PEG_J },
#endif

	{ "9 jumps 5 to 2", (PEG_9 + PEG_5), PEG_2 },
	{ "9 jumps 8 to 7", (PEG_9 + PEG_8), PEG_7 },
#if defined(BOARD6) || defined(BOARD7)
	{ "9 jumps d to i", (PEG_9 + PEG_D), PEG_I },
	{ "9 jumps e to k", (PEG_9 + PEG_E), PEG_K },
#endif

	{ "a jumps 6 to 3", (PEG_A + PEG_6), PEG_3 },
	{ "a jumps b to c", (PEG_A + PEG_B), PEG_C },
#if defined(BOARD7)
	{ "a jumps g to n", (PEG_A + PEG_G), PEG_N },
	{ "a jumps f to l", (PEG_A + PEG_F), PEG_L },
#endif

	{ "b jumps 7 to 4", (PEG_B + PEG_7), PEG_4 },
	{ "b jumps c to d", (PEG_B + PEG_C), PEG_D },
#if defined(BOARD7)
	{ "b jumps h to o", (PEG_B + PEG_H), PEG_O },
	{ "b jumps g to m", (PEG_B + PEG_G), PEG_M },
#endif


	{ "c jumps 7 to 3", (PEG_C + PEG_7), PEG_3 },
	{ "c jumps 8 to 5", (PEG_C + PEG_8), PEG_5 },
	{ "c jumps b to a", (PEG_C + PEG_B), PEG_A },
	{ "c jumps d to e", (PEG_C + PEG_D), PEG_E },
#if defined(BOARD7)
	{ "c jumps h to n", (PEG_C + PEG_H), PEG_N },
	{ "c jumps i to p", (PEG_C + PEG_I), PEG_P },
#endif

	{ "d jumps 8 to 4", (PEG_D + PEG_8), PEG_4 },
	{ "d jumps c to b", (PEG_D + PEG_C), PEG_B },
#if defined(BOARD7)
	{ "d jumps i to o", (PEG_D + PEG_I), PEG_O },
	{ "d jumps j to q", (PEG_D + PEG_J), PEG_Q },
#endif

	{ "e jumps 9 to 5", (PEG_E + PEG_9), PEG_5 },
	{ "e jumps d to c", (PEG_E + PEG_D), PEG_C },
#if defined(BOARD7)
	{ "e jumps j to p", (PEG_E + PEG_J), PEG_P },
	{ "e jumps k to r", (PEG_E + PEG_K), PEG_R },
#endif

#if defined(BOARD6) || defined(BOARD7)
	{ "f jumps a to 6", (PEG_F + PEG_A), PEG_6 },
	{ "f jumps g to h", (PEG_F + PEG_G), PEG_H },

	{ "g jumps b to 7", (PEG_G + PEG_B), PEG_7 },
	{ "g jumps h to i", (PEG_G + PEG_H), PEG_I },

	{ "h jumps g to f", (PEG_H + PEG_G), PEG_F },
	{ "h jumps b to 6", (PEG_H + PEG_B), PEG_6 },
	{ "h jumps c to 8", (PEG_H + PEG_C), PEG_8 },
	{ "h jumps i to j", (PEG_H + PEG_I), PEG_K },

	{ "i jumps h to g", (PEG_I + PEG_H), PEG_G },
	{ "i jumps c to 7", (PEG_I + PEG_C), PEG_7 },
	{ "i jumps d to 9", (PEG_I + PEG_D), PEG_9 },
	{ "i jumps j to k", (PEG_I + PEG_J), PEG_K },

	{ "j jumps i to h", (PEG_J + PEG_I), PEG_H },
	{ "j jumps d to 8", (PEG_J + PEG_D), PEG_8 },

	{ "k jumps j to i", (PEG_K + PEG_J), PEG_I },
	{ "k jumps e to 9", (PEG_K + PEG_E), PEG_9 },
#endif

#if defined(BOARD7)
	{ "l jumps f to a", (PEG_L + PEG_F), PEG_A },
	{ "l jumps m to n", (PEG_L + PEG_M), PEG_N },

	{ "m jumps g to b", (PEG_M + PEG_G), PEG_B },
	{ "m jumps n to o", (PEG_M + PEG_N), PEG_O },

	{ "n jumps m to l", (PEG_N + PEG_M), PEG_L },
	{ "n jumps g to a", (PEG_N + PEG_G), PEG_A },
	{ "n jumps h to c", (PEG_N + PEG_H), PEG_C },
	{ "n jumps o to p", (PEG_N + PEG_O), PEG_P },

	{ "o jumps n to m", (PEG_O + PEG_M), PEG_N },
	{ "o jumps h to b", (PEG_O + PEG_H), PEG_B },
	{ "o jumps i to d", (PEG_O + PEG_I), PEG_D },
	{ "o jumps p to q", (PEG_O + PEG_P), PEG_Q },

	{ "p jumps o to n", (PEG_P + PEG_O), PEG_N },
	{ "p jumps i to c", (PEG_P + PEG_I), PEG_C },
	{ "p jumps j to e", (PEG_P + PEG_J), PEG_E },
	{ "p jumps q to r", (PEG_P + PEG_Q), PEG_R },

	{ "q jumps p to o", (PEG_Q + PEG_P), PEG_O },
	{ "q jumps j to d", (PEG_Q + PEG_J), PEG_D },

	{ "r jumps q to p", (PEG_R + PEG_Q), PEG_P },
	{ "r jumps k to e", (PEG_R + PEG_K), PEG_E },
#endif
};

int places[sizeof(possible_moves)/sizeof(struct move)];

/* no side effects on j - evaluated twice */
#define POSSIBLE(i, j) ((i & places[j]) == possible_moves[j].before)
#define RESULT(i, j) ((i & (~(places[j]))) | possible_moves[j].after)
#define MESG(i) (possible_moves[i].mesg)

char *
position_name(int position) {
	switch (position) {

		case PEG_0: return "0 left";
		case PEG_1: return "1 left";
		case PEG_2: return "2 left";
		case PEG_3: return "3 left";
	  	case PEG_4: return "4 left";
		case PEG_5: return "5 left";
		case PEG_6: return "6 left";
		case PEG_7: return "7 left";
		case PEG_8: return "8 left";
		case PEG_9: return "9 left";
		case PEG_A: return "a left";
		case PEG_B: return "b left";
		case PEG_C: return "c left";
		case PEG_D: return "d left";
		case PEG_E: return "e left";
#if defined(BOARD6) || defined(BOARD7)
		case PEG_F: return "f left";
		case PEG_G: return "g left";
		case PEG_H: return "h left";
		case PEG_I: return "i left";
		case PEG_J: return "j left";
		case PEG_K: return "k left";
#endif
#if defined(BOARD7)
		case PEG_L: return "l left";
		case PEG_M: return "m left";
		case PEG_N: return "n left";
		case PEG_O: return "o left";
		case PEG_P: return "p left";
		case PEG_Q: return "q left";
		case PEG_R: return "r left";
#endif
	}
	return "Program ended with illegal peg state.";
}

int visited[8*1024*1024];

/* don't do side effects in i: evaluated multiple times */
#define REMEMBERED(i) ((visited[i>>5] & (1<<(i & 0x01f)))!=0)
#define REMEMBER(i) (visited[i>>5] |= (1<<(i & 0x01f)))
/* more aggressive memoization remembers mirrored, rotated positions */
/* mirror on the 3-r axis:
 * 0 1 2 3 4 5 6  6 5 4 3 2 1 0
 *  7 8 9 a b c    c b a 9 8 7
 *   d e f g h      h g f e d
 *    i j k l        l k j i 
 *     m n o          o n m
 *      p q            q p
 *       r              r
 *
 * 0 -> 6  - 6 left
 * 1 -> 5  - 4 left
 * 2 -> 4  - 2 left
 * 3 -> 3  - 0 left
 * 4 -> 2  - 2 right
 * 5 -> 1  - 4 right
 * 6 -> 0  - 6 right
 * 7 -> c  - 5 left
 * 8 -> b  - 3 left
 * 9 -> a  - 1 left
 * a -> 9  - 1 right
 * b -> 8  - 3 right
 * c -> 7  - 5 right
 * d -> h  - 4 left
 * e -> g  - 2 left
 * f -> f  - 0 left
 * g -> e  - 2 right
 * h -> d  - 4 right
 * i -> l  - 3 left
 * j -> k  - 1 left
 * k -> j  - 1 right
 * l -> i  - 3 right
 * m -> o  - 2 left
 * n -> n  - 0 left
 * o -> m  - 2 right
 * p -> q  - 1 left
 * q -> p  - 1 right
 * r -> r  - 0 left
 *
 * rotation, 120 clockwise:
 * 0 1 2 3 4 5 6  r p m i d 7 0
 *  7 8 9 a b c    q n j e 8 1
 *   d e f g h      o k f 9 2
 *    i j k l        l g a 3
 *     m n o          h b 4
 *      p q            c 5
 *       r              6
 *
 * 0 -> 6  - 6 left
 * 1 -> c  - 11 left
 * 2 -> h  - 15 left
 * 3 -> l  - 18 left
 * 4 -> o  - 20 left
 * 5 -> q  - 21 left
 * 6 -> r  - 22 left
 * 7 -> 5  - 2 right
 * 8 -> b  - 3 left
 * 9 -> g  - 7 left
 * a -> k  - 10 left
 * b -> n  - 12 left
 * c -> p  - 13 left
 * d -> 4  - 9 right
 * e -> a  - 4 right
 * f -> f  - 0 left
 * g -> j  - 3 left
 * h -> m  - 5 left
 * i -> 3  - 15 right
 * j -> 9  - 10 right
 * k -> e  - 6 right
 * l -> i  - 3 right
 * m -> 2  - 20 right
 * n -> 8  - 15 right
 * o -> d  - 11 right
 * p -> 1  - 24 right
 * q -> 7  - 19 right
 * r -> 0  - 27 right
 *
 * mirror on the 0-l axis:
 * 0 1 2 3 4 5 6  0 7 d i m p r
 *  7 8 9 a b c    1 8 e j n q
 *   d e f g h      2 9 f k o
 *    i j k l        3 a g l
 *     m n o          4 b h
 *      p q            5 c
 *       r              6
 *
 * 0 -> 0  - 0 left
 * 1 -> 7  - 6 left
 * 2 -> d  - 11 left
 * 3 -> i  - 15 left
 * 4 -> m  - 18 left
 * 5 -> p  - 20 left
 * 6 -> r  - 22 left
 * 7 -> 1  - 6 right
 * 8 -> 8  - 0 left
 * 9 -> e  - 5 left
 * a -> j  - 9 left
 * b -> n  - 12 left
 * c -> q  - 14 left
 * d -> 2  - 11 right
 * e -> 9  - 5 right
 * f -> f  - 0 left
 * g -> k  - 4 left
 * h -> o  - 7 left
 * i -> 3  - 15 right
 * j -> a  - 9 right
 * k -> g  - 4 right
 * l -> l  - 0 left
 * m -> 4  - 18 right
 * n -> b  - 12 right
 * o -> h  - 7 right
 * p -> 5  - 20 right
 * q -> c  - 14 right
 * r -> 6  - 22 right
 *
 * Strategy: mask into reflection 0 shifts.
 * for i = 1 to 27, shift left, mask into symmetries
 * for i = 1 to 27, shift right, mask into symmetries
 * masks populate two 27 by 5 matrices corresponding to
 * (left,right) shift x 27 shifts x 5 other symmetries (two rotations, three mirrors)
 *
 * this method turned out to be unneeded, and its computational cost might outweigh
 * its benefit
 */

char *steps[NSTEPS];

int
main(int argc, char *argv[], char *env[]) {

  int i;

#if defined(BOARD7)
	printf("l m n o p q r\n");
#endif
#if defined(BOARD6) || defined(BOARD6)
	printf(" f g h i j k\n");
#endif
	printf("  a b c d e\n");
	printf("   6 7 8 9\n");
	printf("    3 4 5\n");
	printf("     1 2\n");
	printf("      0\n");

	memset(visited, 0, sizeof(visited));
	for (i = 0; i < (sizeof(places)/sizeof(int)); i++) {
	  places[i] = possible_moves[i].before | possible_moves[i].after;
	}

	search(P0_EMPTY,"start with 0 empty",0);
	search(P1_EMPTY,"start with 1 empty",0);
	search(P3_EMPTY,"start with 3 empty",0);
	search(P4_EMPTY,"start with 4 empty",0);
#if defined(BOARD7)
	search(P6_EMPTY,"start with 6 empty",0);
#endif
#if defined(BOARD6) || defined(BOARD7)
	search(P7_EMPTY,"start with 7 empty",0);
#endif
#if defined(BOARD7)
	search(PC_EMPTY,"start with c empty",0); 
#endif
	printf("Search finished.\n");
}

int
search(int start_position, char *prior_move, int prior_step) {
	int i;
        int success;

        success = 0;

	steps[prior_step++] = prior_move;

	if (prior_step == (NSTEPS - 1)) {
		steps[NSTEPS-1]=position_name(start_position);
		show_solution();
		return 1;
	};

	for (i = 0; i < (sizeof(possible_moves)/sizeof(struct move)); i++) {
		if (POSSIBLE(start_position, i) &&
			!REMEMBERED(RESULT(start_position,i))) {
			success |= search(RESULT(start_position, i), MESG(i), prior_step);
		};
	};

	if (!success) {
		REMEMBER(start_position);
	}
        return success;
}

void
show_solution() {
  int i;

	for (i=0; i < NSTEPS; i++) {
		printf("%s\n", steps[i]);
	};
	printf(".oO()Oo.oO()Oo.oO()Oo.oO()Oo.oO()Oo.oO()Oo.oO()Oo.oO()Oo.\n");
}