/**
bugz.cpp : Solver for the "four bugs on a card" puzzle.
  This puzzle has 9 cards with pictures of bugs on them. 
  Each edge has the front or back of a bug.  There is an 
  3 by 3 arrangement of the cards that all bugs fit together

This program finds those arrangements.
*/


#include "assert.h"

#include <afx.h>

#include "stdafx.h"

#include "Card.h"


#define NUM_CARDS 9
#define EDGE_LEN  3


//char* bugNames[5] = {"", "spider  ", "lady bug ", "red roach", "flies    "};
char* bugNames[5] = {"", "blue  ", "purple", "red   ", "green "};

CCard universe[NUM_CARDS];
int solutionCnt;

int solution[EDGE_LEN][EDGE_LEN];
/* 
solution[i][j] is the set of cards on the point 
in the table of (i,j) pairs:

(0,0) (1,0) (2,0)
(0,1) (1,1) (2,1)
(0,2) (1,2) (2,2)
*/
	

// test the card at the position given
bool constraint(int iPos, int jPos)
{
	int s1, s2;
	if (iPos>0)  // test above
	{
		s1 = universe[solution[iPos-1][jPos]].getSide(BOTTOM);
		s2 = universe[solution[iPos][jPos]].getSide(TOP);
		if ( (s1+s2) != 0) 
			return false;
	}

	if (jPos>0)  // test left
	{
		s1 = universe[solution[iPos][jPos-1]].getSide(RIGHT);
		s2 = universe[solution[iPos][jPos]].getSide(LEFT);
		if ( (s1+s2) != 0)
			return false;
	}

	return true;
}


void dumpBug(int bug) 
{
	if (bug < 0) 
		printf(" back %s", bugNames[-bug]);
	else
		printf("front %s", bugNames[bug]);
}


void dumpCard(int i) 
{
	printf("card %i\n         ", i);
	int side = universe[i].getSide(TOP);
	dumpBug(side);
	printf("\n");
	dumpBug(universe[i].getSide(LEFT));
	printf("  ");
	dumpBug(universe[i].getSide(RIGHT));
	printf("\n         ");
	dumpBug(universe[i].getSide(BOTTOM));
	printf("\n");
}
				

void dumpUniverse() 
{
	printf("looking for a grid of these cards\n");
	for (int i=0; i<NUM_CARDS; i++)
	{
		dumpCard(i);
		printf("\n");
	}
	printf("\n");
}


void dumpSolution() 
{
	int iPos, jPos;
	for (iPos=0; iPos<EDGE_LEN; iPos++)
	{
		for (jPos=0; jPos<EDGE_LEN; jPos++)
		{
			int cardNum = solution[iPos][jPos];
			if (cardNum == -1)
			{
				printf("\n");
				return;
			}
			else
			{
				int side = universe[cardNum].getSide(RIGHT);
				if (side < 0) 
					side = -side;

				printf("(%i, %i) %s ", cardNum + 1, universe[cardNum].orient, bugNames[side]);
			}
		}

		printf("\n");
		for (jPos=0; jPos<EDGE_LEN; jPos++)
		{
			int cardNum = solution[iPos][jPos];
			int side = universe[cardNum].getSide(BOTTOM);
			if (side < 0) 
				side = -side;
			printf("%s       ", bugNames[side]);
		}


		printf("\n");
	}
}


// recursively try to find a solution. 
bool solveOnePosition(int pos) 
{
	if (pos == NUM_CARDS)
	{
		solutionCnt++;
		printf("\nsolution:\n", solutionCnt);
		dumpSolution();
		return true;
	}

	int iPos = pos / EDGE_LEN; // vertical position
	int jPos = pos % EDGE_LEN; // horizontal
	
	assert(jPos < 3);
	assert(iPos < 3);

	int i, j;

	//try all available cards
	for (i=0; i<NUM_CARDS; i++)
	{
		if (! universe[i].inUse)
		{
			assert(universe[i].inUse == false);

			universe[i].inUse = true;
			solution[iPos][jPos] = i;

			//in all available orientations
			for (j=0; j<=LEFT; j++)
			{
				universe[i].orient = j;
				if (constraint(iPos, jPos))
					solveOnePosition(pos+1);
			}

			universe[i].inUse = false;
		}
	}

	solution[iPos][jPos] = -1;

	return false;
}


int main(int argc, char* argv[])
{
/* creepy crawlies
	universe[0].init(-2,-2, 1, 3);
	universe[1].init( 2,-1, 3, 4);
	universe[2].init( 4,-4,-1, 2);
	universe[3].init(-3,-4, 1, 2);
	universe[4].init(-1,-4,-3,-2);
	universe[5].init( 4, 3,-2,-1);
	universe[6].init( 1,-2,-3,-4);
	universe[7].init( 2,-1,-3,-4);
	universe[8].init( 3, 2,-1, 4);
*/

/* dragons blue ==> 1,  purple ==> 2,   red ==> 3,  green ==> 4 */
	universe[0].init( 3, 4,-2, 1);
	universe[1].init( 2, 1,-3,-4);
	universe[2].init(-4, 2, 3,-1);
	universe[3].init( 2,-4,-3, 1);
	universe[4].init( 3,-1,-2, 4);
	universe[5].init(-3, 4, 2, 1);
	universe[6].init( 3,-1,-4, 2);
	universe[7].init( 2, 4, 1, 1);
	universe[8].init(-2,-3,-2,-4);

	dumpUniverse();

	
	//node from universe
    int i, j;

	for (i=0; i<NUM_CARDS; i++)
	{
		solution[i/EDGE_LEN][i%EDGE_LEN] = -1;
	}


	for (i=0; i<NUM_CARDS; i++)
	{
		solution[0][0] = i;
		universe[i].inUse = true;

		for (j=0; j<=LEFT; j++)
		{
			universe[i].orient= j;
			solveOnePosition(1);
		}
		universe[i].inUse = false;
	}
	
	printf("found %i solutions to the bug problem.\n", solutionCnt);
	return 0;
}