#include <iostream>

int isAvailable(int puzzle[][9], int row, int col, int num)
{
	int sqCol = col / 3 * 3;
	int sqRow = row / 3 * 3;
	for (int i = 0; i<9; ++i)
	{
		if (puzzle[row][i] == num) return 0;
		if (puzzle[i][col] == num) return 0;
		if (puzzle[sqRow + (i % 3)][sqCol + (i / 3)] == num) return 0;
	}
	return 1;
}

int solveSudoku(int puzzle[][9], int row, int col)
{
	if (col == 9) {
		col = 0;
		row++;
	}
	if (row == 9) {
		return 1;
	}

	if (puzzle[row][col] != 0) {
		return solveSudoku(puzzle, row, col + 1);
	}

	for (int i = 1; i <= 9; ++i)
	{
		if (isAvailable(puzzle, row, col, i))
		{
			puzzle[row][col] = i;
			if (solveSudoku(puzzle, row, col + 1))
				return 1;
		}
	}

	puzzle[row][col] = 0;
	return 0;
}

void printSudoku(int puzzle[9][9])
{
	for (int i = 0; i<9; ++i)
	{
		for (int j = 0; j<9; ++j) {
			std::cout << puzzle[i][j] << " ";
		}
		std::cout << "\n";
	}
}

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

	solveSudoku(puzzle, 0, 0);
	printSudoku(puzzle);
}