/**
JumpPegs.cpp : 

This program solves the peg jumping puzzle found in Cracker Barrel 
restaurants around the country.

Imagine a triangular block of wood with 15 holes in it.
You fill the holes with 14 golf tees.  You can jump over a peg to 
remove it.  The goal is to get down to one peg.
*/

/*
testing peg puzzle with starting hole 0,0
0,0:0
1,0:X 1,1:X
2,0:X 2,1:X 2,2:X
3,0:X 3,1:X 3,2:X 3,3:X
4,0:X 4,1:X 4,2:X 4,3:X 4,4:X
move 15 jump up left from 2,2 to 0,0
0,0:X
1,0:X 1,1:0
2,0:X 2,1:X 2,2:0
3,0:X 3,1:X 3,2:X 3,3:X
4,0:X 4,1:X 4,2:X 4,3:X 4,4:X

*/
#include "stdafx.h"

#define EDGE_LEN 5


bool testJump(char * sDir, int numPegs, 
			  int x, int y, int x1, int y1, int x2, int y2);


/* 
represents the peg board, 
  true ==> peg is filled
  false ==> empty

for pegBoard[x][y]
don't use x < y or x >= EDGE_LEN
*/
bool pegBoard[EDGE_LEN][EDGE_LEN];
int minPegs;


void init() 
{
	int x, y; 
	for (x=0; x<EDGE_LEN; x++)
		for (y=0; y<=x; y++)
			pegBoard[x][y] = true;

	minPegs = ((EDGE_LEN+1) * EDGE_LEN) / 2 - 1;
}



void dumpBoard()
{
	int x, y;

	//printf("\npegs left: %i\n", numPegs);

	for (x=0; x<EDGE_LEN; x++)
	{
		for (int i=0; i<EDGE_LEN-x; i++)
			printf(" ");

		for (y=0; y<=x; y++)
			printf("%c ", pegBoard[x][y] ? 'X' :'0');
//			printf("%i,%i:%c ", x, y, pegBoard[x][y] ? 'X' :'0');
		printf("\n");
	}
}


bool jump(int numPegs)
{
	if (numPegs < minPegs)
		minPegs = numPegs;

	if (numPegs == 1)
		return true;

	int x, y; 
	for (x=0; x<EDGE_LEN; x++)
	{
		for (y=0; y<=x; y++)
		{
			if (!pegBoard[x][y])
			{
				// try to jump from all directions
				//if one succeeds, return
				//otherwise keep searching
				if (testJump("up", numPegs, x, y, x+1, y, x+2, y) ||
					testJump("down", numPegs, x, y, x-1, y, x-2, y) ||
					testJump("right", numPegs, x, y, x, y-1, x, y-2) ||
					testJump("left", numPegs, x, y, x, y+1, x, y+2) ||
					testJump("up left", numPegs, x, y, x+1, y+1, x+2, y+2) ||
					testJump("up right", numPegs, x, y, x+1, y-1, x+2, y-2) ||
					testJump("down left", numPegs, x, y, x-1, y+1, x-2, y+2) ||
					testJump("down right", numPegs, x, y, x-1, y-1, x-2, y-2))
					return true;
			}
		}
	}
	return false;
}


// try to jump x2,y2 over x1,y1 into x,y
bool testJump(char * sDir, int numPegs, 
			  int x, int y, int x1, int y1, int x2, int y2)
{
	// check for edge of board
	// don't use x<y or x>=EDGE_LEN
	if (x<0 || y<0 || x2<0 || y2<0)
		return false;
	
	if (x<y || x1<y1 || x2<y2)
		return false;

	if (x>=EDGE_LEN || x2>=EDGE_LEN)
		return false;


	// check that jumping and jumped points have pegs 
	if ( !pegBoard[x1][y1] || !pegBoard[x2][y2])
		return false;


	// looks ok, do the jump
	pegBoard[x][y] = true;
	pegBoard[x1][y1] = false;
	pegBoard[x2][y2] = false;

	
	// recur ...
	bool bOk = jump(numPegs-1);
	
	if(bOk)
	{
		printf("\nmove %i jump %s from %i,%i to %i,%i\n", numPegs-1, sDir, x2, y2, x, y);
		dumpBoard();
	}

	// put board back
	pegBoard[x][y] = false;
	pegBoard[x1][y1] = true;
	pegBoard[x2][y2] = true;
	
	return bOk;
}


bool test(int x, int y)
{
	// prepare pegBoard and minPegs, leaving one hole
	init();
	pegBoard[x][y] = false;

	printf("testing peg puzzle with starting hole %i,%i\n", x, y);

	if (jump(minPegs))
	{
		printf("\nfound a solution to:\n");
		dumpBoard();
		return true;
	}
	return false;
}


int main(int argc, char* argv[])
{
	//try all 4 starting spots
	test(0,0);
	test(1,0);
	test(2,0);
	test(2,1);

	return 0;
}