//	This is an algorithm for solving a sudoku puzzle. The algorithm used is called "Backtracking", which can be easily
//	looked up on wikipedia

#include <iostream>
#include <random>		//	For random generator engine
#include <chrono>
#include <thread>

using namespace std;

bool isValidInput(int number);
void moveForward();
void moveBackward();
int returnIncreasedNum();


int gameBoard[9][9] = {
{ 0,0,0,0,0,0,0,0,0 },
{ 0,0,0,0,0,0,0,0,0 },
{ 0,0,0,0,0,0,0,0,0 },
{ 0,0,0,0,0,0,0,0,0 },
{ 0,0,0,0,0,0,0,0,0 },
{ 0,0,0,0,0,0,0,0,0 },
{ 0,0,0,0,0,0,0,0,0 },
{ 0,0,0,0,0,0,0,0,0 },
{ 0,0,0,0,0,0,0,0,0 }
//int gameBoard[9][9] = {
//{ 0,0,4,1,0,0,0,0,2 },
//{ 0,7,6,0,0,8,3,0,0 },
//{ 0,1,0,0,3,2,0,0,0 },
//{ 0,6,7,2,0,3,0,0,0 },
//{ 0,2,8,4,0,1,7,6,0 },
//{ 0,0,0,8,0,7,2,3,0 },
//{ 0,0,0,3,2,0,0,9,0 },
//{ 0,0,2,7,0,0,1,5,0 },
//{ 5,0,0,0,0,9,4,0,0 }
};
int gameBoardStatic[9][9] = {
{ 0,0,4,1,0,0,0,0,2 },
{ 0,7,6,0,0,8,3,0,0 },
{ 0,1,0,0,3,2,0,0,0 },
{ 0,6,7,2,0,3,0,0,0 },
{ 0,2,8,4,0,1,7,6,0 },
{ 0,0,0,8,0,7,2,3,0 },
{ 0,0,0,3,2,0,0,9,0 },
{ 0,0,2,7,0,0,1,5,0 },
{ 5,0,0,0,0,9,4,0,0 }
};

int row = 0;	//	Row
int col = 0;	//	Column

const int MAXNUMBERS = 20;	//	max amount of numbers to be filled into the board

int main()
{
	std::random_device rd;  //Will be used to obtain a seed for the random number engine
	std::mt19937 gen(rd()); //Standard mersenne_twister_engine seeded with rd()

	for (int i = 0; i < MAXNUMBERS; i++)
	{
		bool notAccepted = true;

		while (notAccepted)
		{
			row = (rd() % 9);			//	Get a random row
			col = (rd() % 9);		//	Get a random column

			if (gameBoard[row][col] == 0)
				notAccepted = false;
		}

		cout << i << endl;

		while (true)
		{
			int number = rd() % 9 + 1;	//	"+ 1" because we want numbers from 1-9, not 0-9

			if (isValidInput(number))			// If the number does not violate any rules
			{
				gameBoard[row][col] = number;		//	Add 'k' to the cell
				break;
			}
		}
	}

	//	SET THE STATIC BOARD = NEWLY GENERATED BOARD
	for (int i = 0; i < 9; i++)
	{
		for (int j = 0; j < 9; j++)
		{
			gameBoardStatic[i][j] = gameBoard[i][j];
		}
	}

	//	JUST FOR PRINTOUT
	for (int i = 0; i < 9; i++)
	{
		for (int j = 0; j < 9; j++)
		{
			cout << gameBoard[i][j] << " ";
		}
		cout << "\n";
	}
	cout << "\n";


	row = col = 0;	//	Reset numbers for the backtracking algorithm

	//	BACKTRACKING ALGORITHM
	while (row < 9 && col < 9)
	{
		bool backTrack = true;

		for (int k = gameBoard[row][col]; k <= 9; k++)															//	First go through all possible numbers 1-9
		{
			if (k == 0)
				k = 1;

			if (isValidInput(k))		//	If the number 'k' does not violate any rules
			{
				gameBoard[row][col] = k;		//	Add 'k' to the cell
				moveForward();
				backTrack = false;
				break;
			}
		}

		if (backTrack)																			//	If no numbers from 1-9 matches in the cell, start backtracking
		{
			gameBoard[row][col] = 0;		//	Clear the current cell in which there was no match
			moveBackward();					//	Move to the previous cell

			if (returnIncreasedNum() != 0)	//	If we can increase the number in the cell
			{
				gameBoard[row][col] = returnIncreasedNum();					//	Increase the number by the next allowed number
				moveForward();
			}
			else
			{
				gameBoard[row][col] = 0;
				moveBackward();
				continue;
			}
		}
	}
		//	JUST FOR PRINTOUT
		for (int i = 0; i < 9; i++)
		{
			for (int j = 0; j < 9; j++)
			{
				cout << gameBoard[i][j] << " ";
			}
			cout << "\n";
		}
		cout << "\n";
}


int returnIncreasedNum()		//	Checks if we can increase the number in the cell. If yes return number, if no return 0
{
	if (gameBoard[row][col] == 9)
		return 0;
	else
	{
		for (int i = gameBoard[row][col] + 1; i <= 9; i++)	//	+1 to get the next number
		{
			if (isValidInput(i))
				return i;						//	Return the valid number
		}
		return 0;
	}
}

void moveForward()		//	Moves to the next cell infront
{
	bool isTemplate = true;		//	If we hit a cell from the template

	while (isTemplate)			//	Continues as long as there is a blank space available
	{
		if (col == 8)
		{
			row++;
			col = 0;
		}
		else
			col++;
		if (gameBoardStatic[row][col] == 0)
			isTemplate = false;
	}
}

void moveBackward()		//	Moves to the previous cell behind
{
	bool isTemplate = true;		//	If we hit a cell from the template

	while (isTemplate)			//	Continues as long as there is a blank space available
	{
		if (col == 0)
		{
			row--;
			col = 8;
		}
		else
			col--;
		if (gameBoardStatic[row][col] == 0)
			isTemplate = false;
	}
}

bool isValidInput(int number)		//	Checks if the cell number does not violate any rules
{
	//Check the box constraints:
	//	Get's the top left position
	int newR = row - (row % 3);
	int newC = col - (col % 3);

	for (int r = 0; r < 3; r++)			//	local row
	{
		newC = col - (col % 3);
		for (int c = 0; c < 3; c++)		//	local columnn
			if (gameBoard[newR + r][newC + c] == number && gameBoard[newR + r][newC + c] != gameBoard[row][col])		//	If the number k already exists in the block
				return false;
	}

	//	Check if the same numbers exist on the row/column lines
	for (int l = 0; l < 9; l++)		//	For hver rad/kolonne
		if (number == gameBoard[l][col] || number == gameBoard[row][l])	//	Sjekke om tallet k eksisterer i samme rad/kolonne
			return false;

	return true;
}