#include "sudoku-solve.H"

#include <iostream>
#include <vector>
#include <cassert>
namespace sudoku
{
#ifndef SUDOKU_SOLVE_DEBUG
	const bool debug_output = false;
#else
	const bool debug_output = SUDOKU_SOLVE_DEBUG;
#endif
	rcb RCB(unsigned int index)
	{
		rcb t;
		t.row = index / COLS;
		t.col = index % COLS;
		t.bigbox = (t.row / 3) * 3 + (t.col / 3);
		return t;
	}

	unsigned int Index(const rcb& rcb)
	{
		return rcb.col + rcb.row * COLS;
	}

	bool Board::UnSet(unsigned int index)
	{
		if (item[index].val < 0)
		{
			return false;
		}

		--filled;

		int n = item[index].val;
		item[index].val = -1;

		rcb rcb = RCB(index);

		row[rcb.row].push(n);
		col[rcb.col].push(n);
		bigbox[rcb.bigbox].push(n);

		// possible moves are cross-section of all possible moves in groups
		item[index].poss = row[rcb.row];
		item[index].poss &= col[rcb.col] & bigbox[rcb.bigbox];

		// NOTE: division and remultiplication is not redundant: rounding!
		const unsigned int bigboxcol = rcb.bigbox % 3;
		const unsigned int bigboxrow = rcb.bigbox / 3;
		const unsigned int bigboxstart = bigboxrow * 27 + bigboxcol * 3;
		// add the number to the possible choices of the rest of the bigbox, ...
		{
			const unsigned int colstart = bigboxcol * 3;
			const unsigned int colend = colstart + 3;
			const unsigned int rowstart = bigboxrow * 3;
			const unsigned int rowend = rowstart + 3;

			unsigned int bigboxrowstart = bigboxstart;

			for (unsigned int r = rowstart; r < rowend; ++r)
			{
				Possible<int, 9> initial = row[r] & bigbox[rcb.bigbox];
				for (unsigned int c = colstart; c < colend; ++c)
				{
					const int i = bigboxrowstart + c - colstart;
					if (item[i].val < 0)
						item[i].poss = initial & col[c];
				}
				bigboxrowstart += COLS;
			}
		}
		// ... row, ...
		{
			const unsigned int rowindex = rcb.row * COLS;
			for (unsigned int bbc = 0; bbc < 3; ++bbc)
			{
				if (bbc == bigboxcol)
					continue;

				const unsigned int colstart = bbc * 3;
				const unsigned int colend = colstart + 3;

				Possible<int, 9> initial = row[rcb.row] & bigbox[bbc + bigboxrow * 3];

				for (unsigned int c = colstart; c < colend; ++c)
				{
					const int i = rowindex + c;
					if (item[i].val < 0)
						item[i].poss = initial & col[c];
				}
			}
		}
		// ... and column
		{
			for (unsigned int bbr = 0; bbr < 3; ++bbr)
			{
				if (bbr == bigboxrow)
					continue;

				const unsigned int rowstart = bbr * 3;
				const unsigned int rowend = rowstart + 3;

				Possible<int, 9> initial = col[rcb.col] & bigbox[bbr * 3 + bigboxcol];

				for (unsigned int r = rowstart; r < rowend; ++r)
				{
					const int i = rcb.col + r * COLS;
					if (item[i].val < 0)
						item[rcb.col + r * COLS].poss = initial & row[r];
				}
			}
		}
		return true;
	}

	bool Board::Set(unsigned int index, int n)
	{
		if (n == item[index].val)
			return true;
		if (n < 0)
		{
			return false;
		}

		rcb pos = RCB(index);
		// validate move
		if (item[index].val >= 0)
			return false;

		if (! (row[pos.row][n] && col[pos.col][n] && bigbox[pos.bigbox][n]))
			return false;

		++filled;
		item[index].val = n;
		item[index].poss.clear();
		//item[index].poss.push(n);

		row[pos.row].pop(n);
		col[pos.col].pop(n);
		bigbox[pos.bigbox].pop(n);

		// TODO: the following contains some redundancy, which should probably be eliminated
		// remove the number from the possible choices of the rest of the row, ...
		{
			const unsigned int rowstart = COLS * pos.row;
			const unsigned int rowmid = rowstart + pos.col;
			const unsigned int rowend = COLS * (pos.row + 1);
			for (unsigned int i = rowstart; i < rowmid; ++i)
				item[i].poss.pop(n);

			for (unsigned int i = rowmid + 1; i < rowend; ++i)
				item[i].poss.pop(n);
		}

		// ... column, ...
		{
			const unsigned int colstart = pos.col;
			const unsigned int colmid = colstart + pos.row * COLS;
			const unsigned int colend = BOXES;
			for (unsigned int i = colstart; i < colmid; i += COLS)
				item[i].poss.pop(n);

			for (unsigned int i = colmid + COLS; i < colend; i += COLS)
				item[i].poss.pop(n);
		}

		// ... and bigbox
		{
			// NOTE: division and remultiplication is not redundant: rounding!
			const unsigned int boxstart = (pos.row / 3) * 27 + (pos.col / 3) * 3;
			unsigned int boxrowstart = boxstart;
			for (unsigned int i = 0; i < 3; ++i)
			{
				for (unsigned int j = 0; j < 3; ++j)
				{
					item[boxrowstart + j].poss.pop(n);
				}
				boxrowstart += COLS;
			}
		}
		return true;
	}


	bool Board::Solveable()
	{
		for (int i = 0; i < BOXES; ++i)
		{
			if (item[i].val < 0 && item[i].poss.num() == 0)
				return false;
		}

		for (int bb = 0; bb < BIGBOXES; ++bb)
		{
			const unsigned int bbcol = (bb % 3);
			const unsigned int bbrow = (bb / 3);
			const unsigned int bbstart = bbrow * 27 + bbcol * 3;
			Possible<int,9> possible;
			possible.clear();
			for (int r = 0; r < 3; ++r)
			{
				for (int c = 0; c < 3; ++c)
				{
					possible |= item[bbstart + r * COLS + c].poss;
					//std::cout << bbstart + r * COLS + c << " ";
					//std::cout << possible.num() << " \n";
				}
			}
			//std::cout << std::endl;
			//std::cout << bigbox[bb].num() << " " << (possible & bigbox[bb]).num() << std::endl << std::endl;
			if (bigbox[bb].num() > (possible & bigbox[bb]).num())
				return false;
		}
		for (int c = 0; c < COLS; ++c)
		{
			Possible<int,9> possible;
			possible.clear();

			for (int r = 0; r < ROWS; ++r)
			{
				possible |= item[c + r * COLS].poss;
			}
			if (col[c].num() > (possible & col[c]).num())
				return false;
		}
		for (int r = 0; r < ROWS; ++r)
		{
			Possible<int,9> possible;
			possible.clear();
			unsigned int rowstart = r * COLS;
			for (int c = 0; c < ROWS; ++c)
			{
				possible |= item[c + rowstart].poss;
			}
			if (row[r].num() > (possible & row[r]).num())
				return false;
		}
		return true;
	}

	/*
	TODO: write a cleaner version of the puzzle generator, currently just use the old solver.
	bool Generate(Board& board, unsigned int fixed)
	{
		return false;
	}
	*/

	bool Solve(Board& board, std::vector<move>& moves)
	{
		// speed up the process a bit by doing all memory allocation up front
		moves.reserve(board.Blanks() + moves.size());
		//const unsigned int fixed = board.Filled();

/*		if (debug_output)
			board.Print<true>();*/

		while (board.Blanks() > 0)
		{
			// check whether we're in a deadlock situation
			if (!board.Solveable())
			{
				if (debug_output)
				{
					std::cout << "We've hit deadlock, trying to resolve. " << moves.size() << " previous moves.\n";
					board.Print<false>();
				}
				// retrace our steps until we come upon a 'random' or 'likely' move that can be amended
				while (true)
				{
					std::vector<move>::iterator cur = moves.end();
					do
					{
						// unsolveable if we've exhausted the possibilities of retracing
						if (cur == moves.begin())
							return false;

						--cur;
						if (debug_output)
						{
							std::cout << "Undo: <" << cur - moves.begin() << "> ";
							cur->Print();
						}
						assert(cur->Undo(board));
					}
					while (cur->kind <= MOVE_FORCED);

					
					{
						std::vector<move>::iterator del = cur;
						++del;
						if (debug_output)
						{
							std::cout << "Undoing " << moves.end() - del << " moves.\n";
							board.Print<false>();
						}
						moves.erase(del, moves.end());
					}

					{
						size_t move_id = cur - moves.begin();
						if (move_id == 9)
							board.Print<false>();
					}
					
					if (debug_output)
					{
						rcb pos(RCB(cur->index));
						std::cout << "Current move, " << cur - moves.begin() << " is at " << pos.col + 1 << ", " << pos.row + 1 << ", value: " << cur->value + 1 << ", " << 9 - cur->tries << " tries remain\n";
					}
					
					// must increment before test for next iteration, see NOTE below.
					++cur->tries;
					while (cur->tries < 10)
					{
						/* NOTE: we had ++cur->tries; on this line before. This was a
						 * problem as the loop didn't terminate on try 10. If the illegal
						 * 10th try was an allowed move, the check after the loop failed
						 * and the illegal move was propagated. Took me many hours to find.
						 * AAARGHHH!!!
						 */
						cur->value = (cur->value + 1) % 9;
						if (cur->Do(board))
						{
							if (board.Solveable())
								break;
							assert(cur->Undo(board));
						}
						// must increment before test for next iteration, see NOTE above.
						++cur->tries;
					}
					if (cur->tries < 10)
					{
						if (debug_output)
						{
							std::cout << "Trying value: " << cur->value + 1<< std::endl;
							if	(cur - moves.begin() == 9)
								board.Print<false>();
						}
						break;
					}
					if (debug_output)
					{
						std::cout << "Ran out of tries, will need to undo more moves.\n";
					}
					// run out of tries, have to backtrace yet further.
					moves.erase(cur);
				}
			}
			// board should now not be in deadlock
			assert(board.Solveable());
/*			if (debug_output)
				board.Print<true>();*/

			bool retrace = false;

			bool success_poss = true;
			bool success_opt = true;
			do
			{
				// first line of attack is to try to find and immediately perform forced
				// moves for boxes with only one placement possibility
				if (success_opt)
				{
					size_t start_moves = moves.size();
					if (debug_output)
					{
						std::cout << "Searching for boxes with only one placement possibility...";
					}
					
					success_poss = ForcedPossibilities(board, moves);
					if (debug_output)
					{
						std::cout << "found: " << moves.size() - start_moves << std::endl;
					}
					start_moves = moves.size();
					
					// if this leaves us in a dead end, go back to the drawing board.
					if (!board.Solveable())
					{
						retrace = true;
						break;
					}

					if (board.Blanks() == 0)
						return true;
				}

				/* the second type of forced moves arises from there only being one
				 * possible box to place a digit in the given row, column, or bigbox.
				 * Note that filling up one of these in rows can free another one up
				 * in columns and bigboxes, so we keep doing it as long as we keep
				 * finding them.
				 */
				if (success_poss || success_opt)
				{
					size_t start_moves = moves.size();
					if (debug_output)
					{
						std::cout << "Searching for rows, columns, and big-boxes with only one placement possibility...";
					}
					
					success_opt = ForcedOptions(board, moves);
					if (debug_output)
					{
						std::cout << "found: " << moves.size() - start_moves << std::endl;
						for (size_t i = start_moves; i < moves.size(); ++i)
						{
							std::cout << "DO: ";
							moves[i].Print();
						}
					}
					start_moves = moves.size();
					// if this leaves us in a dead end, go back to the drawing board.
					if (!board.Solveable())
					{
						retrace = true;
						break;
					}

					if (board.Blanks() == 0)
						return true;

					success_poss = false;
				}
			}
			while (success_poss || success_opt);

			if (retrace)
				continue;

			
			if (debug_output)
			{
				std::cout << "Begin speculative search for move " << moves.size() << ".\n";
			}
			/* once the forced moves have been exhausted, we need to make a 'likely'
			 * move. Such moves are based on trial and error, like random moves, but
			 * more directed, as they will go for the boxes with the fewest possible
			 * mistakes. */
			{
				// assemble list of spaces with <array index> possible moves, -1 is unset
				int poss[10] = {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1};
				for (unsigned int index = 0; index < BOXES; ++index)
				{
					int free = board[index].poss.num();
					poss[free] = index;

					// 2 is always a winner (1 == forced, 0 == already set)
					if (free == 2)
						break;
				}

				move likely;
				likely.kind = MOVE_LIKELY;
				for (int best = 2; best < 10; ++best)
				{
					if (poss[best] >= 0)
					{
						if (debug_output)
						{
							rcb pos(RCB(poss[best]));
							std::cout << "Found location with " << best << " possible values at " << pos.col + 1 << ", " << pos.row + 1;
						}
						likely.index = poss[best];
						break;
					}
				}

				
				for (likely.value = 0; likely.value < 9; ++likely.value)
				{
					if (board[likely.index].poss[likely.value])
					{
						break;
					}
				}
				likely.tries = likely.value + 1;
				if (debug_output)
				{
					std::cout << ": setting to " << likely.value + 1 << std::endl;
				}
				
				likely.Do(board);
				moves.push_back(likely);
			}
			if (debug_output)
			{
				std::cout << "End speculative search.\n";
			}
			if (debug_output)
				board.Print<false>();
		}
/*		if (debug_output)
			board.Print<true>();*/

		return true;
	}

	bool ForcedPossibilities(Board& board, std::vector<move>& moves)
	{
		bool success = false;
		unsigned int index = 0;
		unsigned int tried = 0;
		while (tried < BOXES && board.Blanks() > 0 && board.Solveable())
		{
			if (board[index].poss.num() != 1)
			{
				++tried;
			}
			else
			{
				// forced move found!
				success = true;
				move force;
				force.kind = MOVE_FORCED;
				force.index = index;
				force.tries = 1;
				for (unsigned int n = 0; n < 9; ++n)
				{
					if (board[index].poss[n])
					{
						force.value = n;
						break;
					}
				}
				assert(force.value < 9);

				force.Do(board);
				moves.push_back(force);
//				if (debug_output)
// 					board.Print<true>();

				// reset try counter, as we may have created new forced moves
				tried = 0;
			}
			index = (index + 1) % BOXES;
		}
		return success;
	}


	bool FillOptions(Board& board, std::vector<move>& moves, const std::vector<unsigned int>& indices)
	{
		bool success = false;
		unsigned int options[9] = {0,0,0,0,0,0,0,0,0};
		int opt_index[9] = {-1,-1,-1,-1,-1,-1,-1,-1,-1};

		for (unsigned int i = 0; i < indices.size(); ++i)
		{
			const unsigned int index = indices[i];
			unsigned int left = board[index].poss.num();
			unsigned int n = 0;
			while (left > 0)
			{
				if (board[index].poss[n])
				{
					++options[n];
					opt_index[n] = index;
					--left;
				}
				++n;
			}
			assert(n <= 9);
		}

		for (unsigned int n = 0; n < 9; ++n)
		{
			if (options[n] == 1)
			{
				// bingo - this is exactly what we're looking for.
				move force;
				force.kind = MOVE_FORCED;
				force.index = opt_index[n];
				force.tries = 1;
				force.value = n;

				if (force.Do(board))
				{
					success = true;
					moves.push_back(force);
				}
				/*else
				{
					std::cout << "I'm pretty sure this is bad!\n";
				}
				

				// Actually, I've changed my mind. It's not necessarily bad and can happen occasionally.
				// However, the success indicator had to be moved, as it could potentially trigger an infinite loop.
				*/
				
				//if (debug_output)
				//	board.Print<true>();
			}
		}
		return success;
	}

	bool ForcedOptions(Board& board, std::vector<move>& moves)
	{
		bool success = false;

		std::vector<unsigned int> indices(9);

		// find and fill forced options for each row, ...
		for (unsigned int row = 0; row < ROWS; ++row)
		{
			const unsigned int rowstart = row * COLS;
			for (int i = 0; i < 9; ++i)
			{
				indices[i] = rowstart + i;
			}
			success |= FillOptions(board, moves, indices);
		}
		if (!board.Solveable())
			return false;

		// ... column, ...
		for (unsigned int col = 0; col < COLS; ++col)
		{
			for (int i = 0; i < 9; ++i)
			{
				indices[i] = col + i * COLS;
			}
			success |= FillOptions(board, moves, indices);
		}
		if (!board.Solveable())
			return false;
		// ... and bigbox.
		for (unsigned int bb = 0; bb < BIGBOXES; ++bb)
		{
			const unsigned int rowstart = (bb / 3) * 27;
			const unsigned int colstart = (bb % 3) * 3;
			const unsigned int rowend = rowstart + 27;
			const unsigned int colend = colstart + 3;
			unsigned int i = 0;
			for (unsigned int row = rowstart; row < rowend; row += COLS)
			{
				for (unsigned int c = colstart; c < colend; ++c)
				{
					indices[i] = row + c;
					++i;
				}
			}
			success |= FillOptions(board, moves, indices);
		}
		if (!board.Solveable())
			return false;
		return success;
	}

	void move::Print()
	{
		rcb pos(RCB(index));
		std::cout << "MOVE: Tile " << (char)('A' + pos.col) << (1 + pos.row) << ": value " << value + 1 << ", current try " << tries << ", kind " << kind << std::endl;
	}
}