#pragma once
#ifndef SUDOKU_SOLVE_H
#define SUDOKU_SOLVE_H

//#include <list>
#include <vector>
#include "sudoku.H"
#include <iostream>
// just a bunch of data structure declarations for the new solving algorithm...
// NOTE: 'box' means 1x1 square, 'bigbox' means 3x3 square, 'board' is the whole 9x9 shebang.
namespace sudoku
{
	enum CONSTANTS
	{
		ROWS = 9,
		COLS = ROWS,
		BIGBOXES = ROWS,
		BOXES = ROWS * COLS,
	};

	enum MOVE_KIND
	{
		// setup move: this move is part of the problem and can't possibly be undone
		MOVE_FIXED,
		// forced move: not to make this move would be incorrect
		MOVE_FORCED,
		// move predicted to be likely to be correct, not purely random
		MOVE_LIKELY,
		// randomised move: randomly chosen within the constraints of the current position
		MOVE_RANDOM,
	};

	struct rcb
	{
		int row, col, bigbox;
	};

	rcb RCB(unsigned int index);
	unsigned int Index(const rcb& rcb);
	inline unsigned int Index(unsigned int row, unsigned int col)
	{
		return col + row * COLS;
	}

	template<typename digit, digit digits> class Possible
	{
	protected:
		digit count;
		bool val[digits];
	public:
		void clear()
		{
			count = 0;
			for (digit i = 0; i < digits; ++i)
				val[i] = false;
		}
		Possible()
		{
			all();
		}

		/* add digit to possibilities, if not already on there. Returns whether the digit was
		 * previously present. */
		bool push(digit n)
		{
			if (!val[n])
			{
				val[n] = true;
				++count;
				return false;
			}
			return true;
		}
		/* remove digit from possibilities, return true if it was actually a member. */
		bool pop(digit n)
		{
			if (val[n])
			{
				val[n] = false;
				--count;
			}
			return n;
		}
		void all()
		{
			for (count = 0; count < digits; ++count)
				val[count] = true;
		}

		digit num() const
		{
			return count;
		}

		bool operator[](digit n) const
		{
			return val[n];
		}

		Possible operator&(const Possible& rhs) const
		{
			Possible tmp;
			tmp.clear();
			for (digit i = 0; i < digits; ++i)
			{
				tmp.val[i] = val[i] && rhs[i];
				if (tmp[i])
					++tmp.count;
			}
			return tmp;
		}
		Possible& operator&=(const Possible& rhs)
		{
			for (digit i = 0; i < digits; ++i)
			{
				if (val[i])
				{
					val[i] = rhs[i];
					if (!val[i])
						--count;
				}
			}
			return *this;
		}
		Possible operator|(const Possible& rhs) const
		{
			Possible tmp;
			tmp.clear();
			for (digit i = 0; i < digits; ++i)
			{
				tmp.val[i] = val[i] || rhs[i];
				if (tmp[i])
					++tmp.count;
			}
			return tmp;
		}
		Possible& operator|=(const Possible& rhs)
		{
			for (digit i = 0; i < digits; ++i)
			{
				if (!val[i])
				{
					val[i] = rhs[i];
					if (val[i])
						++count;
				}
			}
			return *this;
		}
	};


/*	struct group
	{
		Possible<int, 9> unset;
		stack<int, 9> positions[9];

		bool Solveable()
		{
			// for every unset digit, make sure that there are spaces available to
			// place that digit
			for (size_t n = 0; n < 9; ++n)
			{
				if (unset[n])
				{
					if (positions[n].size() == 0)
						return false;
				}
			}
			return true;
		}
	};*/

	class Board
	{
	public:
		struct choice
		{
			// -1 = unset, 0..8: digits 1-9
			int val;
			Possible<int, 9> poss;

			choice()
			{
				val = -1;
			}
		};

	protected:
		choice item[BOXES];
		Possible<int, 9> row[ROWS];
		Possible<int, 9> col[COLS];
		Possible<int, 9> bigbox[BIGBOXES];

		unsigned int filled;
	public:
		Board()
		{
			filled = 0;
		}
		bool UnSet(unsigned int index);
		bool Set(unsigned int index, int n);
		const choice& operator[](unsigned int index) const
		{
			return item[index];
		}

		unsigned int Blanks()
		{
			return BOXES - filled;
		}
		unsigned int Filled()
		{
			return filled;
		}

		// this isn't guaranteed - even if true, it might not be solveable. but if false, it's certainly not solveable
		bool Solveable();

		template<bool debug> void Print();
	};

	struct move
	{
		move()
		{}

		// convert from old 'attempt' struct.
		move(const Sudoku::attempt& old, MOVE_KIND type)
		{
			value = old.value;
			tries = old.tries;
			index = old.index;
			kind = type;
		}

		operator Sudoku::attempt() const
		{
			Sudoku::attempt old;
			old.value = value;
			old.tries = tries;
			old.index = index;
			rcb pos = RCB(index);
			old.row = pos.row;
			old.col = pos.col;
			old.box = pos.bigbox;
			return old;
		}

		unsigned int index;
		/*unsigned int row;
		unsigned int col;
		unsigned int bigbox;*/
		MOVE_KIND kind;
		// used for likely and random moves:
		// value assigned
		unsigned int value;
		// attempts of values at this location (once we hit 9 and can't solve it, we need to go back)
		unsigned int tries;

		bool Do(Board& b)
		{
			return b.Set(index, value);
		}
		bool Undo(Board& b)
		{
			return b.UnSet(index);
		}
		
		void Print();
	};

	bool ForcedPossibilities(Board& board, std::vector<move>& moves);
	bool FillOptions(Board& board, std::vector<move>& moves, const std::vector<unsigned int>& indices);
	bool ForcedOptions(Board& board, std::vector<move>& moves);
	// solve given board with some moves already performed.
	bool Solve(Board& board, std::vector<move>& moves);
	// solve given board
	inline bool Solve(Board& board)
	{
		std::vector<move> moves;
		return Solve(board, moves);
	}

	template<bool debug> void Board::Print()
	{
		const char top[]    = "    A   B   C   D   E   F   G   H   I  \n";
		const char across[] = "  +---+---+---#---+---+---#---+---+---+\n";
		const char boss[]   = "  +===+===+===#===+===+===#===+===+===+\n";
		
		std::cout << top;
		for (int r = 0; r < 9; ++r)
		{
			if (r % 3 == 0)
				std::cout << boss;
			else
				std::cout << across;
			
			if (!debug)
				std::cout << r + 1;
			else
				std::cout << r + 1 << " ";
			
			for (int c = 0; c < 9; ++c)
			{
				if (!debug)
					std::cout << " | ";
				else
					std::cout << "|";
				
				if (item[r * 9 + c].val >= 0)
					std::cout << item[r * 9 + c].val + 1;
				else
					std::cout << " ";
				
				if (debug)
					std::cout << ":" << item[r * 9 + c].poss.num();
				
			}
			if (debug)
				std::cout << "| " << row[r].num() << "\n";
			else
				std::cout << " |\n";
		}
		std::cout << boss;
		
		if (debug)
		{
			std::cout << " ";
			for (int c = 0; c < 9; ++c)
			{
				std::cout << "   ";
				std::cout << col[c].num();
			}
			std::cout << " |\n";
		}
	}
}


#endif