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); } } }