import 'math';

class Sudoku {
	public int[] $board;
	int $size;

	public void __construct(int[] $board) {
		$this->board = $board;
		$this->size = sizeof($this->board);
	}

	public bool isSafe(int $row, int $col, int $n) {
		int $d, $r;
		for($d = 0; $d < $this->size; $d++) {
			if($this->board[$row][$d] == $n) {
				return false;
			}
		}
		for($r = 0; $r < $this->size; $r++) {
			if($this->board[$r][$col] == $n) {
				return false;
			}
		}
		int $sqrt = (int) sqrt($this->size);
		int $boxRowStart = $row - $row % $sqrt;
		int $boxColStart = $col - $col % $sqrt;
		int $w, $q;
		for($w = $boxRowStart; $w < $boxRowStart + $sqrt; $w++) {
			for($q = $boxColStart; $q < $boxColStart + $sqrt; $q++) {
				if($this->board[$w][$q] == $n) {
					return false;
				}
			}
		}
		return true;
	}

	public void print() {
		int $r, $d;
		for($r = 0; $r < $this->size; $r++) {
			for($d = 0; $d < $this->size; $d++) {
				print($this->board[$r][$d] + " ");
			}
			print("\n");
		}
	}

	public bool solve() {
		int $row = -1;
		int $col = -1;
		bool $isEmpty = true;
		int $i, $j;
		for($i = 0; $i < $this->size; $i++) {
			for($j = 0; $j < $this->size; $j++) {
				if($this->board[$i][$j] == 0) {
					$row = $i;
					$col = $j;
					$isEmpty = false;
					break;
				}
			}
			if(!$isEmpty) {
				break;
			}
		}
		if($isEmpty) {
			return true;
		}
		int $n;
		for($n = 1; $n <= $this->size; $n++) {
			if($this->isSafe($row, $col, $n)) {
				$this->board[$row][$col] = $n;
				if($this->solve()) {
					return true;
				} else {
					$this->board[$row][$col] = 0;
				}
			}
		}
		return false;
	}

}

class Program {

	void main() {
		int[] $board = {
			{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}
		};
		object $sudoku = new Sudoku($board);
		$sudoku->print();
		print("=================\n");
		if($sudoku->solve()) {
			$sudoku->print();
		} else {
			print("No solution found\n");
			var_dump($sudoku->board);
		}
	}

}