#include "board.h"
#include "os.h"
#include <string.h>


/*

	TODO:
	-----

	* When solving, instead of finding the first empty cell, pick a random one
	* when generating, make a list of all the cells, random-order it, and remove one by one as long as there's a single result ?

*/



CBoard::CBoard(void)
{
	PreCalcPaths();

	ClearBoard();
}

CBoard::~CBoard(void)
{
}

void CBoard::PreCalcPaths()
{
	for (int i=0; i<BOARD_SIZE; i++)
	{
		Path	&row	= m_paths[i];
		Path	&col	= m_paths[BOARD_SIZE+i];
		Path	&box	= m_paths[BOARD_SIZE*2+i];

		uint32 sU = (i%3)*3;
		uint32 sV = (i/3)*3;

		for (int x=0; x<BOARD_SIZE; x++)
		{
			row[x].u = x;
			row[x].v = i;

			col[x].u = i;
			col[x].v = x;

			box[x].u = sU + (x%3);
			box[x].v = sV + (x/3);
		}
	}
}

void CBoard::ClearBoard()
{
	memset(m_board, 0, sizeof(m_board));
}

BoardStatusType	CBoard::GetBoardStatus()
{
	bool	foundIncompleteness = false;
	int		nineBitsOn			= 0x3fe;	//	00000011 11111110
						  			   //	   15     8 7      0

	for (int p=0; p<NUM_PATHS; p++)
	{
		Path	&path	= m_paths[p];
		int		sum		= 0;
		int		bit;

		sum = 0;

		for (int i=0; i<BOARD_SIZE; i++)
		{
			bit = 1 << GET_FIXED(m_board[path[i].v][path[i].u]);
			if (sum & nineBitsOn & bit)
			{
				return BS_ERROR;
			}
            sum |= bit;
		}
		if (sum != nineBitsOn) foundIncompleteness = true;
	}

	// the board is solved
	return foundIncompleteness ? BS_INCOMPLETE : BS_COMPLETE;
}

void CBoard::SetItem(int u, int v, int val, bool isOption, bool onOff)
{
	// range check
	if (u < 0 || u >= BOARD_SIZE || v < 0 || v >= BOARD_SIZE || val > 10) return;

	// our item
	uint16&	item = m_board[v][u];

	if (!isOption)
	{
		item = val;										// set the fixed value and remove any options
		//item &= ~BOARD_ITEM_FIXED_MASK;							// remove any previously stored FIXED number
		//item = val;										// store the new value (0..10)
	}
	else
	{
		uint16 shift = BOARD_ITEM_OPTIONS_START_BIT + val - 1;
		if (onOff)	item |= (1<<shift);	// turn on
		else		item &= ~(1<<shift);	// turn off
	}
}

uint16 CBoard::GetItem(int u, int v)
{
	// range check
	if (u < 0 || u >= BOARD_SIZE || v < 0 || v >= BOARD_SIZE) return 0xffff;

	return m_board[v][u];
}

void CBoard::FillPencilMarks()
{
	// turn on all the options
	for (int v=0; v<BOARD_SIZE; v++)
	{
		for (int u=0; u<BOARD_SIZE; u++)
		{
			uint16& b = m_board[v][u];

			if (HAS_FIXED(b))	b &= ~BOARD_ITEM_OPTIONS_MASK;	// all options OFF
			else				b |= BOARD_ITEM_OPTIONS_MASK;	// all options ON
		}
	}

	int	nineBitsOn = 0x3fe;	//	00000011 11111110
					//	15     8 7      0

	for (int p=0; p<NUM_PATHS; p++)
	{
		Path	&path	= m_paths[p];
		int		sum		= 0;

		// figure out all the numbers that are used, and create a mask out of it
		for (int i=0; i<BOARD_SIZE; i++) sum |= (1 << GET_FIXED(m_board[path[i].v][path[i].u]));

		// check (ignore first bit which can be set by '1<<0')
		if ((sum&(~1)) != nineBitsOn)
		{
			// all 'on' bits on sum must be masked out of the item's OPTIONS
			sum = (~((sum >> 1) << BOARD_ITEM_OPTIONS_START_BIT)) | ~BOARD_ITEM_OPTIONS_MASK;

			// apply it to all the items in this path
			for (int i=0; i<BOARD_SIZE; i++) m_board[path[i].v][path[i].u] &= sum;
		}
	}
}

int CBoard::ApplyRule1()
{
	int numSolved = 0;

	// go over all the board, looking for items that have only 1 option
	for (int v=0; v<9; v++)
	{
		for (int u=0; u<9; u++)
		{
			uint16	&b = m_board[v][u];

			// if this guy has a value, skip it
			if (HAS_FIXED(b)) continue;

			uint16	o = GET_OPTIONS(b);

			// find what options are on, and if only one is one, store it's index
			int		numOptions = 0;
			uint16	optionVal;
			for (int x=0; x<BOARD_SIZE; x++)
			{
				if ((o>>x) & 1)
				{
					numOptions++;
					optionVal = x+1;
				}
			}

			// if there's 1 option -> fix this baby to this one option
			if (numOptions == 1)
			{
				b |= optionVal;
				numSolved++;
			}
		}
	}

	return numSolved;
}


int CBoard::ApplyRule2()
{
	int numSolved = 0;

	// go over all the paths
 	for (int p=0; p<NUM_PATHS; p++)
	{
		Path	&path = m_paths[p];

		struct
		{
			Point	lastCell;	// the last cell this option appeared in
			int	counter;	// how many cells had this option on
		} options[BOARD_SIZE];

		memset(&options, 0, sizeof options);

		// for each path, scan all the cells and their options. for each possible option write down that it was possible
		// and increase the 'how many times was this possible counter' for it.

		// go over this path
		for (int i=0; i<BOARD_SIZE; i++)
		{
			uint16	b = m_board[path[i].v][path[i].u];

			int tttt = GET_FIXED(b);

			// if this guy doesn't have a value, great, pick up it's options
			if (NO_FIXED(b))
			{
				int cellOptions = GET_OPTIONS(b);

				// go over all the options
				for (int x=0; x<BOARD_SIZE; x++)
				{
					if ((cellOptions>>x) & 1)
					{
						options[x].lastCell = path[i];
						options[x].counter++;
					}
				}
			}
			// otherwise, we need to let the other's know that this number is taken,
			// we'll fake it by maxing out this option
			else
			{
				options[GET_FIXED(b) - 1].counter = 2;
			}
		}

		// we completed the path, now check if there are any options that appear in only 1 place
		for (int x=0; x<BOARD_SIZE; x++)
		{
			if (options[x].counter == 1)
			{
				// great, this option appeared in only 1 place, it means this cell must contain this value
				uint16& b = m_board[options[x].lastCell.v][options[x].lastCell.u];

				// remove any fixed value that may be there (when we're working on an erronous board, a single
				// cell can be found to be able to contain several FIXED values, hence a mere |= causes lots of trouble)
				b &= ~BOARD_ITEM_FIXED_MASK;
				b |= x+1;

				numSolved++;
			}
		}
	}

	return numSolved;
}

// helper function to take options-bit-mask and return a randomly-sorted array of the options
static void RandomifyOptions(uint16 options, int* result, int* numResults)
{
	int	num = 0;
	int	x;

	// find all the ON options and store in an array
	for (x=0; x<BOARD_SIZE; x++)
	{
		// is this option on ?
		if ((options >> x) & 1)	result[num++] = x+1;
	}

	// random-sort the array
	// for each position in the array, choose a random digit from the rest of the array
	for (x=0; x<num-1; x++)
	{
		int src = x + 1 + (OS_RAND % (num-x-1));
		
		// switch between 'x' and 'src'
		int	tmp = result[x];
		result[x] = result[src];
		result[src] = tmp;
	}

    // return number of results
	*numResults = num;
}

SolutionType CBoard::Solve(bool determineIfMultiple)
{
	int	numSolved				= 1;
	int	numSolved1, numSolved2;
	int	numSteps				= 0;

	for (;;)
	{
		// check board status
		BoardStatusType	boardStatus = GetBoardStatus();

		if		(boardStatus == BS_COMPLETE)	return SOLUTOIN_SINGLE;	// we're done
		else if	(boardStatus == BS_ERROR)		return SOLUTOIN_NONE;	// the board leads to an error
		else if (numSolved == 0)				break;		// not done but can't get anything else, out of this loop

		// fill-in trivial pencil marks
		FillPencilMarks();

		// apply first solving rule
		numSolved1 = ApplyRule1();
		numSolved2 = ApplyRule2();

		// increase counters
		numSolved = numSolved1 + numSolved2;
		numSteps++;

//		printf("Step %3d: solved %2d [method 1: %2d, method 2: %2d]\n", numSteps, numSolved, numSolved1, numSolved2);
	}

	// trial-and-error

	// find a cell that doesn't have a fixed value
	int		u, v;
	int		found;

	for (v=0; v<BOARD_SIZE; v++)
	{
		for (u=0; u<BOARD_SIZE; u++)
		{
			if ((found = NO_FIXED(m_board[v][u])) != 0) break;
		}

		if (found) break;
	}

	// [v][u] doesn't have a fixed value
	uint16	cellOptions = GET_OPTIONS(m_board[v][u]);
	int		options[BOARD_SIZE];
	int		numOptions;
	int		foundSol = -1;
	CBoard	tempBoard;

	// random sort the options
	RandomifyOptions(cellOptions, options, &numOptions);

	// go over it's options and try them each at a time
	for (int x=0; x<numOptions; x++)
	{
		// create a new board for the experiment
		tempBoard = *this;

		// set the value we're going to test
		tempBoard.SetItem(u, v, options[x]);

		// now try to recursively solve
		SolutionType sol = tempBoard.Solve(determineIfMultiple);

		// see if we're going to send back the result
		if ((sol == SOLUTOIN_MULTPLE) ||						    // we have multiple results, send them back
			(sol == SOLUTOIN_SINGLE && !determineIfMultiple) ||			// we have one result, and we were'nt asked for more than that
			(sol == SOLUTOIN_SINGLE && determineIfMultiple && foundSol != -1))	// we got one result, but already have one stored
																				// and we're looking for more than one, great
		{
			*this = tempBoard;
			return (sol == SOLUTOIN_MULTPLE || foundSol != -1) ? SOLUTOIN_MULTPLE : SOLUTOIN_SINGLE;
		}

		// is this the first solution, and we're looking for multiple ?
		if (sol == SOLUTOIN_SINGLE && determineIfMultiple && foundSol == -1)
		{
             		// yes, mark the fact that we found a singlue solution
			foundSol = x;
		}

		// move on
	}

	// if we're here, we either have no result, or we're looking for multiple results and found just one
	if (foundSol == -1) return SOLUTOIN_NONE;

	// we found just one solution, reconstruct the solution and send it back
	SetItem(u, v, options[foundSol]);
	Solve();

	return SOLUTOIN_SINGLE;
}

SolutionType CBoard::IsSolveable()
{
	CBoard	temp = *this;
	return temp.Solve(true);
}

void CBoard::Generate(uint16 seed, int difficulty)	// 1..3
{
	ClearBoard();

	// set a random seed
	OS_SRAND(seed);

	// 'solve' this board (fill it up)
	Solve();

	//
	// remove cells
	//
	int	numVisibleCells = BOARD_SIZE*BOARD_SIZE;
	int	targetVisible	= 50;//30+(3-difficulty)*5;

	while (numVisibleCells > targetVisible)
	{
		int u = OS_RAND % BOARD_SIZE;
		int v = OS_RAND % BOARD_SIZE;

		// is it already clear ?
		if (NO_FIXED(m_board[v][u])) continue;

		CBoard	tempBoard = *this;
		
		tempBoard.SetItem(u, v, 0);

		if (tempBoard.Solve(true) != SOLUTOIN_SINGLE) continue;

		// clear it
		m_board[v][u] = 0;

		numVisibleCells--;
	}

	// done
}