#include <iostream>
#include <cassert>

#define _DEBUG

typedef struct {
	int first;
	int second;
	int degree;
} 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 available[9][9][10] );
int determine_degree( bool available[9][9][10], int i, int j );
void initialize_availability( int array[9][9], bool available[9][9][10] );
void make_unavailable( bool available[9][9][10], int i, int j, int value );
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}
	};

	print_board( array );

	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];
	bool available[9][9][10];

	int count = find_cells( array, unoccupied, available );

	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], bool available[9][9][10] ) {
	int count = 0;

	initialize_availability( array, available );

	for ( int i = 0; i < 9; ++i ) {
		for ( int j = 0; j < 9; ++j ) {
			if ( array[i][j] == 0 ) {
				int deg = determine_degree( available, i, j );

				assert( deg > 0 );

				if ( deg == 1 ) {
					for ( int k = 1; k <= 9; ++k ) {
						if ( available[i][j][k] ) {
							array[i][j] = k;
						}
					}
				} else {
					unoccupied[count].first = i;
					unoccupied[count].second = j;
					unoccupied[count].degree = deg;

					std::cout << i << ", " << j << ", " << determine_degree( available, i, j ) << std::endl;
				}

				++count;
			}
		}
	}

	return count;
}

void initialize_availability( int array[9][9], bool available[9][9][9] ) {
	for ( int i = 0; i < 9; ++i ) {
		for ( int j = 0; j < 9; ++j ) {
			for ( int k = 0; k < 9; ++k ) {
				available[i][j][k] = true;
			}
		}
	}

	for ( int i = 0; i < 9; ++i ) {
		for ( int j = 0; j < 9; ++j ) {
			if ( array[i][j] != 0 ) {
				make_unavailable( available, i, j, array[i][j] );
			}
		}
	}
}

void make_unavailable( bool available[9][9][9], int i, int j, int value ) {
	for ( int k = 0; k < 9; ++k ) {
		available[i][k][value] = false;
		available[k][j][value] = false;
	}

	int ioff = 3*(i/3);
	int joff = 3*(j/3);

	for ( int m = 0; m < 3; ++m ) {
		for ( int n = 0; n < 3; ++n ) {
			available[ioff + m][joff + n][value] = false;
		}
	}
}

int determine_degree( bool available[9][9][9], int i, int j ) {
	int degree = 0;

	for ( int k = 0; k < 9; ++k ) {
		if ( available[i][j][k] ) {
			++degree;
		}
	}

	return degree;
}

/*
 * 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;
	}
}