#include <iostream>

typedef std::pair<int, int> cell;

bool sudoku_solve( int array[9][9] );
bool sudoku_solve_internal( int array[9][9], cell unoccupied[81], int count );
int find_cells( int array[9][9], cell unoccupied[81] );
bool is_valid( int array[9][9], int value, int m, int n );
void print_board( int array[9][9] );

/*
 * The value 0 indicates a blank.
 */

int main() {
	int array[9][9] = {
		{5, 0, 4, 0, 0, 0, 0, 6, 0},
		{0, 6, 0, 3, 0, 0, 1, 0, 0},
		{0, 9, 2, 5, 4, 0, 0, 0, 0},
		{6, 0, 8, 0, 0, 1, 0, 0, 0},
		{0, 0, 0, 8, 0, 4, 0, 0, 0},
		{0, 0, 0, 2, 0, 0, 6, 0, 1},
		{0, 0, 0, 0, 9, 5, 8, 1, 0},
		{0, 0, 1, 0, 0, 2, 0, 3, 0},
		{0, 8, 0, 0, 0, 0, 2, 0, 7}
	};

	if ( sudoku_solve( array ) ) {
		print_board( array );
	} else {
		std::cout << "No solution found..." << std::endl;
		print_board( array );
	}

	return 0;
}

/*
 * The backtracking algorithm for solving Sudoku
 */

bool sudoku_solve( int array[9][9] ) {
	cell unoccupied[81];

	int count = find_cells( array, unoccupied );

	sudoku_solve_internal( array, unoccupied, count );
}

bool sudoku_solve_internal( int array[9][9], cell unoccupied[81], int count ) {
	// If all the entries are filled, we are done
	if ( count == 0 ) {
		return true;
	}

	--count;

	// Attempt to place each value from 1 to 9 in the
	// next available location
	//  - if it does not cause a duplication attempt to
	//    solve the puzzle recursively
	int const i = unoccupied[count].first;
	int const j = unoccupied[count].second;

	for ( int value = 1; value <= 9; ++value ) {
		if ( is_valid( array, value, i, j ) ) {
			array[i][j] = value;

			if ( sudoku_solve_internal( array, unoccupied, count ) ) {
				return true;
			}

		}
	}

	// We did not find a solution
	array[i][j] = 0;
	return false;
}

/*
 * Find the entries that is not yet assigned a value from 1 to 9
 *  - traverse the board in the following order:
 *
 *      1  2  3   10 11 12   19 20 21 
 *      4  5  6   13 14 15   22 23 24 
 *      7  8  9   16 17 18   25 26 27 
 *   
 *     28 29 30   37 38 39   46 47 48 
 *     31 32 33   40 41 42   49 50 51 
 *     34 35 36   43 44 45   52 53 54 
 *   
 *     55 56 57   64 65 66   73 74 75 
 *     58 59 60   67 68 69   76 77 78 
 *     61 62 63   70 71 72   79 80 81 
 *   
 */

int find_cells( int array[9][9], cell unoccupied[81] ) {
	int count = 0;

	for ( int i1 = 0; i1 < 3; ++i1 ) {
		for ( int j1 = 0; j1 < 3; ++j1 ) {
			for ( int i2 = 0; i2 < 3; ++i2 ) {
				for ( int j2 = 0; j2 < 3; ++j2 ) {
					int const i = 3*i1 + i2;
					int const j = 3*j1 + j2;

					if ( array[i][j] == 0 ) {
						unoccupied[count].first = i;
						unoccupied[count].second = j;
						++count;
					}
				}
			}
		}
	}

	return count;
}

/*
 * Determine if a Sudoku board is valid:
 *  - no number is repeated in the same 3x3 square, row or column
 */

bool is_valid( int array[9][9], int value, int m, int n ) {
	for ( int i = 0; i < 9; ++i ) {
		if ( (array[m][i] == value) || ( array[i][n] == value ) ) return false;
	}

	int ioff = 3*(m/3);
	int joff = 3*(n/3);

	for ( int i = 0; i < 3; ++i ) {
		for ( int j = 0; j < 3; ++j ) {
			if ( array[ioff + i][joff + j] == value ) return false;
		}
	}

	return true;
}

/*
 * Print the board in a formatted manner
 *   
 *     5 3 4   1 7 8   9 6 2 
 *     8 6 7   3 2 9   1 4 5 
 *     1 9 2   5 4 6   3 7 8 
 *   
 *     6 7 8   9 3 1   5 2 4 
 *     2 1 5   8 6 4   7 9 3 
 *     3 4 9   2 5 7   6 8 1 
 *   
 *     4 2 3   7 9 5   8 1 6 
 *     7 5 1   6 8 2   4 3 9 
 *     9 8 6   4 1 3   2 5 7 
 */

void print_board( int array[9][9] ) {
	for ( int i = 0; i < 9; ++i ) {
		if ( i % 3 == 0 ) {
			std::cout << std::endl;
		}

		for ( int j = 0; j < 9; ++j ) {
			if ( j % 3 == 0 ) {
				std::cout << "  ";
			}

			if ( array[i][j] == 0 ) {
				std::cout << "  ";
			} else {
				std::cout << array[i][j] << " ";
			}
		}

		std::cout << std::endl;
	}
}