#include <iostream>
#include <vector>
#include <sys/timeb.h>
#include <time.h>

using namespace std;

//The four possible colors that the ropes can take.
enum color {R, G, B, Y};
//The four directions.
enum dir {N, S, E, W};

//The tile definitions, starting from the left rope on the top
//and preceding clockwise around the tile.  Tiles 1 - 9 are the
//3x3 tiles.  Only the first four colors on the tile are listed
//since the remaining four can be inferred.
color tileDef[25][4] =
{
	{ R, G, Y, B },
	{ R, B, Y, G },
	{ R, B, G, Y },
	{ G, B, Y, R },
	{ G, Y, B, R },
	{ B, R, G, Y },
	{ Y, R, G, B },
	{ Y, G, R, B },
	{ Y, G, B, R },
	{ R, G, B, Y },
	{ R, Y, G, B },
	{ R, Y, B, G },
	{ G, R, B, Y },
	{ G, R, Y, B },
	{ G, B, R, Y },
	{ G, Y, R, B },
	{ B, R, Y, G },
	{ B, G, R, Y },
	{ B, G, Y, R },
	{ B, Y, R, G },
	{ B, Y, G, R },
	{ Y, R, B, G },
	{ Y, B, R, G },
	{ Y, B, G, R },
	{ R, B, G, Y } //The repeated tile.
};

//Records the time spend thinking and the time spent doing.
class doThinkClock
{
private:
	//Variables to keep track of the state of the timer.
	bool doing;
	bool thinking;
	unsigned long lastSecond;
	unsigned long lastMillisecond;
	
	//The time in milliseconds spent thinking and doing.
	__int64 doingTime;
	__int64 thinkingTime;

public:
	//Constructor.
	doThinkClock() : doing(false), thinking(false), lastSecond(-1), lastMillisecond(-1), doingTime(0), thinkingTime(0) {}

	//Start doing.
	void startDo()
	{
		//Container for the time information.
		struct __timeb64 timeBuffer;

		//Retrieve time information.
		_ftime64( &timeBuffer );
		unsigned long second = timeBuffer.time;
		unsigned long millisecond = timeBuffer.millitm;

		if (doing)
			return;
		//If we were thinking, add time to the thinking counter.
		if (thinking)
		{
			thinkingTime += (second - lastSecond) * 1000;
			if (millisecond < lastMillisecond)
				thinkingTime -= lastMillisecond - millisecond;
			else
				thinkingTime += millisecond - lastMillisecond;
			thinking = false;
		}
		doing = true;

		//Remember the current time.
		lastSecond = second;
		lastMillisecond = millisecond;
	}

	//Start thinking.
	void startThink()
	{
		//Container for the time information.
		struct __timeb64 timeBuffer;

		//Retrieve time information.
		_ftime64( &timeBuffer );
		unsigned long second = timeBuffer.time;
		unsigned long millisecond = timeBuffer.millitm;

		if (thinking)
			return;
		//If we were doing, add time to the doing counter.
		if (doing)
		{
			doingTime += (second - lastSecond) * 1000;
			if (millisecond < lastMillisecond)
				doingTime -= lastMillisecond - millisecond;
			else
				doingTime += millisecond - lastMillisecond;
			doing = false;
		}
		thinking = true;

		//Remember the current time.
		lastSecond = second;
		lastMillisecond = millisecond;
	}

	//Stop.
	void stop()
	{
		//Container for the time information.
		struct __timeb64 timeBuffer;

		//Retrieve time information.
		_ftime64( &timeBuffer );
		unsigned long second = timeBuffer.time;
		unsigned long millisecond = timeBuffer.millitm;

		//If we were thinking, add time to the thinking counter.
		if (thinking)
		{
			thinkingTime += (second - lastSecond) * 1000;
			if (millisecond < lastMillisecond)
				thinkingTime -= lastMillisecond - millisecond;
			else
				thinkingTime += millisecond - lastMillisecond;
			thinking = false;
		}
		//If we were doing, add time to the doing counter.
		else if (doing)
		{
			doingTime += (second - lastSecond) * 1000;
			if (millisecond < lastMillisecond)
				doingTime -= lastMillisecond - millisecond;
			else
				doingTime += millisecond - lastMillisecond;
			doing = false;
		}

		//Remember the current time.
		lastSecond = second;
		lastMillisecond = millisecond;
	}

	//Return the time spent thinking.
	unsigned long getDoingTime()
	{ return doingTime; }

	//Return the time spent doing.
	unsigned long getThinkingTime()
	{ return thinkingTime; }
} timer;

//Keeps track of the number of nodes visited.
__int64 nodesVisited = 0;

//Keeps track of the number of consistency checks.
__int64 consistencyChecks = 0;

class tile
{
private:
	int id; //The ID of this tile, to make easier the process of
	//recognizing two tiles which are the same but rotated.
	int orientation; //The orientation of this tile.  It is
	//purely for testing and output purposes.
	color pattern[8]; //The pattern of colors on this tile,
	//starting at the left color on the top and proceeding
	//clockwise around the tile.
public:
	//The constructor for new tiles.
	tile (int newId, color newPattern[4]) : id(newId), orientation(1)
	{
		//Copy the first four colors.
		for (int i = 0; i < 4; i++)
			pattern[i] = newPattern[i];
		//Assign the last four colors.
		pattern[4] = pattern[0];
		pattern[5] = pattern[3];
		pattern[6] = pattern[1];
		pattern[7] = pattern[2];
	}

	//The constructor for rotated tiles.
	tile (int newId, int newOrientation, color newPattern[8]) : id(newId), orientation(newOrientation)
	{
		for (int i = 0; i < 8; i++)
			pattern[i] = newPattern[i];
	}

	//The id accessor function.
	int getId ()
	{ return id; }

	//The orientation accessor function.
	int getOrientation ()
	{ return orientation; }

	//Returns pointers to all possible rotations of this tile.
	void getRotations (tile *&t1, tile *&t2, tile *&t3)
	{
		//The new color patterns.
		color p1[8], p2[8], p3[8];

		for (int i = 0; i < 8; i++)
		{
			p1[i] = pattern[(i + 6) % 8];
			p2[i] = pattern[(i + 4) % 8];
			p3[i] = pattern[(i + 2) % 8];
		}

		//Create new tiles with the same id as this tile.
		t1 = new tile(id, 2, p1);
		t2 = new tile(id, 3, p2);
		t3 = new tile(id, 4, p3);
	}

	//Returns true if this tile matches the given tile in the
	//given direction.
	bool matches (tile *other, dir d)
	{
		//Compare different things depending on what direction
		//this tile is in relation to the other tile.
		switch (d)
		{
			//The other tile is north of this tile.
			case N:
				if (this->pattern[0] == other->pattern[5]
				&& this->pattern[1] == other->pattern[4])
					return true;
				return false;
			//The other tile is south of this tile.
			case S:
				if (this->pattern[4] == other->pattern[1]
				&& this->pattern[5] == other->pattern[0])
					return true;
				return false;
			//The other tile is east of this tile.
			case E:
				if (this->pattern[2] == other->pattern[7]
				&& this->pattern[3] == other->pattern[6])
					return true;
				return false;
			//The other tile is west of this tile.
			case W:
				if (this->pattern[6] == other->pattern[3]
				&& this->pattern[7] == other->pattern[2])
					return true;
				return false;
			default:
				cout << "Illegal direction in 'match' function." << endl;
				exit(1);
		}
	}
};

//Structure representing a spot on the grid.
struct gridSpot
{
	//A vector of tile pointers representing tiles that are
	//still in the domain for this spot on the grid.
	vector<tile*> domain;
	//True if this grid spot has a 'definite' tile placed in it.
	bool placed;
};

//A list of the available tiles, including all rotations.
vector<tile*> availableTiles;

//The size of one side of the grid.
int gridSize;

//The recursive function to do backtracking.
bool recurse (gridSpot grid[5][5], int r, int c, int l)
{
	//Mark another node visited.
	nodesVisited++;

	//Try each tile at (r,c) that's still in the domain.
	for (unsigned int i = 0; i < grid[r][c].domain.size(); i++)
	{
		//Create a new grid for the next level.
		gridSpot newGrid[5][5];
		for (int x = 0; x < gridSize; x++)
			for (int y = 0; y < gridSize; y++)
			{
				newGrid[x][y].domain.assign(grid[x][y].domain.begin(), grid[x][y].domain.end());
				newGrid[x][y].placed = grid[x][y].placed;
			}

		//Put this tile on the new grid.
		newGrid[r][c].domain.clear();
		newGrid[r][c].domain.push_back(grid[r][c].domain[i]);
		newGrid[r][c].placed = true;

		//If this is the last level, we've finished!
		if (l == gridSize * gridSize)
		{
//			for (int x = 0; x < gridSize; x++)
//			{
//				for (int y = 0; y < gridSize; y++)
//					cout << newGrid[y][x].domain[0]->getId() + 1 << "." << newGrid[y][x].domain[0]->getOrientation() << " ";
//				cout << endl;
//			}
			return true;
		}

		//Start thinking.
		timer.startThink();

		//First get rid of any tiles with the same id as this one.
		for (int x = 0; x < gridSize; x++)
			for (int y = 0; y < gridSize; y++)
				if (!newGrid[x][y].placed)
					for (unsigned int z = 0; z < newGrid[x][y].domain.size(); z++)
					{
						consistencyChecks++;
						if (newGrid[r][c].domain[0]->getId() == newGrid[x][y].domain[z]->getId())
						{
							newGrid[x][y].domain.erase(newGrid[x][y].domain.begin() + z);
							z--;
						}
					}

		//If the tile west of us hasn't been placed yet.
		if (r > 0 && !newGrid[r-1][c].placed)
			for (unsigned int i = 0; i < newGrid[r-1][c].domain.size(); i++)
			{
				consistencyChecks++;
				if (!newGrid[r][c].domain[0]->matches(newGrid[r-1][c].domain[i], W))
				{
					newGrid[r-1][c].domain.erase(newGrid[r-1][c].domain.begin() + i);
					i--;
				}
			}

		//If the tile east of us hasn't been placed yet.
		if (r < gridSize - 1 && !newGrid[r+1][c].placed)
			for (unsigned int i = 0; i < newGrid[r+1][c].domain.size(); i++)
			{
				consistencyChecks++;
				if (!newGrid[r][c].domain[0]->matches(newGrid[r+1][c].domain[i], E))
				{
					newGrid[r+1][c].domain.erase(newGrid[r+1][c].domain.begin() + i);
					i--;
				}
			}

		//If the tile north of us hasn't been placed yet.
		if (c > 0 && !newGrid[r][c-1].placed)
			for (unsigned int i = 0; i < newGrid[r][c-1].domain.size(); i++)
			{
				consistencyChecks++;
				if (!newGrid[r][c].domain[0]->matches(newGrid[r][c-1].domain[i], N))
				{
					newGrid[r][c-1].domain.erase(newGrid[r][c-1].domain.begin() + i);
					i--;
				}
			}

		//If the tile south of us hasn't been placed yet.
		if (c < gridSize - 1 && !newGrid[r][c+1].placed)
			for (unsigned int i = 0; i < newGrid[r][c+1].domain.size(); i++)
			{
				consistencyChecks++;
				if (!newGrid[r][c].domain[0]->matches(newGrid[r][c+1].domain[i], S))
				{
					newGrid[r][c+1].domain.erase(newGrid[r][c+1].domain.begin() + i);
					i--;
				}
			}

		//The row and column to try next.
		int nR = 0, nC = 0;
		unsigned int minimumDomain = 1000000;

		//Look for the smallest domain.
		for (int x = 0; x < gridSize; x++)
			for (int y = 0; y < gridSize; y++)
				if (!newGrid[x][y].placed && newGrid[x][y].domain.size() < minimumDomain)
				{
					minimumDomain = newGrid[x][y].domain.size();
					nR = x;
					nC = y;
				}

		//Start doing.
		timer.startDo();

		//Try recursing deeper.
		if (recurse(newGrid, nR, nC, l+1))
			return true;
	}

	return false;
}

int main (int argv, char** argc)
{
	const int trials = 100;

	//This timer times the entire execution of the program.
	doThinkClock executionTimer;
	executionTimer.startDo();

	//Check the command line for large puzzle switch.
	if (argv == 2 && argc[1][0] == '5')
		gridSize = 5;
	else
		gridSize = 3;

	//Initialize the availableTiles vector.
	for (int i = 0; i < gridSize * gridSize; i++)
	{
		//Pointers to tiles which will be rotated.
		tile *t0 = NULL, *t1 = NULL, *t2 = NULL, *t3 = NULL;

		//Create a new tile from the tile definition list.
		t0 = new tile(i, tileDef[i]);

		//Create new tiles by rotating the first tile.
		t0->getRotations(t1, t2, t3);

		//Put tiles into availableTiles vector.
		availableTiles.push_back(t0);
		availableTiles.push_back(t1);
		availableTiles.push_back(t2);
		availableTiles.push_back(t3);
	}

	//Seed the RNG via the time.
	srand((unsigned) time (NULL));

	for (int n = 0; n < trials; n++)
	{
		//Randomize the availableTiles vector.
		for (int i = 0; i < availableTiles.size(); i++)
		{
			//Random index into the availableTiles vector.
			int idx = rand() % availableTiles.size();

			//Temporary tile pointer.
			tile *temp = availableTiles[i];
			availableTiles[i] = availableTiles[idx];
			availableTiles[idx] = temp;
		}

		//Thinking about initializing the constraints.
		timer.startThink();

		//The initial grid.
		gridSpot grid[5][5];
		for (int x = 0; x < gridSize; x++)
			for (int y = 0; y < gridSize; y++)
			{
				grid[x][y].placed = false;
				grid[x][y].domain.assign(availableTiles.begin(), availableTiles.end());
			}

		//Start doing.
		timer.startDo();

		//Start the recursion.
		recurse(grid, 0, 0, 1);

		//Stop the timer.
		timer.stop();
	}

	//Stop the execution timer.
	executionTimer.stop();

	cout << endl;
	cout << "Average total execution time: " << executionTimer.getDoingTime() / trials << "ms" << endl;
	cout << "Average time spent doing: " << timer.getDoingTime() / trials << "ms" << endl;
	cout << "Average time spent thinking: " << timer.getThinkingTime() / trials << "ms" << endl;
	cout << "Average nodes visited: " << nodesVisited / trials << endl;
	cout << "Average consistency checks: " << consistencyChecks / trials << endl;

	return 1;
}