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

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

	for ( int i = 0; i < 9; ++i ) {
		for ( int j = 0; j < 9; ++j ) {
			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;
	}
}