// 2) Find the solution to this specific 9x9 Sudoku puzzle:
//                 8 7 6 9 0 0 0 0 0
//				   0 1 0 0 0 6 0 0 0
//				   0 4 0 3 0 5 8 0 0
//				   4 0 0 0 0 0 2 1 0
//				   0 9 0 5 0 0 0 0 0
//				   0 5 0 0 4 0 3 0 6
//				   0 2 9 0 0 0 0 0 8
//				   0 0 4 6 9 0 1 7 3
//				   0 0 0 0 0 1 0 0 4

#include <iostream>
#include <vector>

void PrintFourByFourGrid(const std::vector<int>& grid)
{
	for (int i = 0; i < 9; ++i)
	{
		for (int j = 0; j < 9; ++j)
		{
			std::cout << grid[(i*9) + j] << " ";
		}
		std::cout << std::endl;
	}
	std::cout << std::endl;
}

bool IsLegalRowColumnWhatever(const std::vector<int>& vector)
{
	std::vector<int> occurrences(vector.size() + 1);

	try
	{
		for (const int& i : vector)
		{
			++occurrences.at(i);
		}
	}

	catch (const std::exception&)
	{
		return false;
	}

	for (std::size_t i = 1; i < occurrences.size(); ++i)
	{
		if (occurrences[i] > 1)
		{
			return false;
		}
	}

	return true;
}

bool IsNineByNineSudokuLegal(const std::vector<int>& grid)
{
	int rows[] = { 0, 9, 18, 27, 36, 45, 54, 63, 72 };
	for (const int& i : rows)
	{
		std::vector<int> v{ grid[i], grid[i + 1], grid[i + 2], grid[i + 3], grid[i+4], grid[i+5], grid[i+6], grid[i+7], grid[i+8] };
		if (IsLegalRowColumnWhatever(v) == false)
		{
			return false;
		}
	}

	int columns[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8 };
	for (const int& i : columns)
	{
		std::vector<int> v{ grid[i], grid[i + 9], grid[i + 18], grid[i + 27], grid[i + 36], grid[i + 45], grid[i + 54], grid[i + 63], grid[i + 72] };
		if (IsLegalRowColumnWhatever(v) == false)
		{
			return false;
		}
	}

	int squares[] = { 0, 3, 6, 27, 30, 33, 54, 57, 60 };
	for (const int& i : squares)
	{
		std::vector<int> v{ grid[i], grid[i + 1], grid[i + 2], grid[i + 9], grid[i + 10], grid[i + 11], grid[i + 18], grid[i + 19], grid[i + 20] };
		if (IsLegalRowColumnWhatever(v) == false)
		{
			return false;
		}
	}

	return true;
}

void GenerateValidNineByNineGrids(std::vector<int>& grid, int index)
{
	if (index == 81)
	{
		PrintFourByFourGrid(grid);
	}
	else
	{
		for (int i = 1; i <= 9; ++i)
		{
			if (grid[index] == 0)
			{
				GenerateValidNineByNineGrids(grid, index + 1);

			}
			if (IsNineByNineSudokuLegal(grid) == true)
			{
				GenerateValidNineByNineGrids(grid, index + 1);
			}
		}
	}
}

void GenerateAllValidNineByNineGrids()
{
	std::vector<int> grid(81, 0);

	GenerateValidNineByNineGrids(grid, 0);
}

int main()
{
	std::vector<int> grid(81, 0);
	grid[0] = 8;
	grid[1] = 7;
	grid[2] = 6;
	grid[3] = 9;
	grid[10] = 1;
	grid[14] = 6;
	grid[19] = 4;
	grid[21] = 3;
	grid[23] = 5;
	grid[24] = 8;
	grid[27] = 4;
	grid[33] = 2;
	grid[34] = 1;
	grid[37] = 9;
	grid[39] = 5;
	grid[46] = 5;
	grid[49] = 4;
	grid[51] = 3;
	grid[53] = 6;
	grid[55] = 2;
	grid[56] = 9;
	grid[62] = 8;
	grid[65] = 4;
	grid[66] = 6;
	grid[67] = 9;
	grid[69] = 1;
	grid[70] = 7;
	grid[71] = 3;
	grid[77] = 1;
	grid[80] = 4;
	GenerateValidNineByNineGrids(grid, 0);
	//             8 7 6 9 0 0 0 0 0
//				   0 1 0 0 0 6 0 0 0
//				   0 4 0 3 0 5 8 0 0
//				   4 0 0 0 0 0 2 1 0
//				   0 9 0 5 0 0 0 0 0
//				   0 5 0 0 4 0 3 0 6
//				   0 2 9 0 0 0 0 0 8
//				   0 0 4 6 9 0 1 7 3
//				   0 0 0 0 0 1 0 0 4

	system("PAUSE");
	return 0;
}