PHP Sodoku Solver Class

Posted in PHP by Karl on February 22, 2010

I wrote this small class to solve Sudoku puzzles. It also has a very basic sudoku puzzle generator method. The code uses a backtracking algorithm to solve the puzzles and should be fairly fast even with slower computers.

1
2
3
4
5
6
7
8
9
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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118

class Sudoku {

private $_matrix;

public function __construct(array $matrix = null) {
if (!isset($matrix)) {
$this->_matrix = $this->_getEmptyMatrix();
} else {
$this->_matrix = $matrix;
}
}

public function generate() {
$this->_matrix = $this->_solve($this->_getEmptyMatrix());
$cells = array_rand(range(0, 80), 30);
$i = 0;
foreach ($this->_matrix as &$row) {
foreach ($row as &$cell) {
if (!in_array($i++, $cells)) {
$cell = null;
}
}
}
return $this->_matrix;
}

public function solve() {
$this->_matrix = $this->_solve($this->_matrix);
return $this->_matrix;
}

public function getHtml() {
echo '<table border="1">';
for ($row = 0; $row < 9; $row++) {
echo '<tr>';
for ($column = 0; $column < 9; $column++) {
echo '<td>' . $this->_matrix[$row][$column] . '</td>';
}
echo '</tr>';
}
echo '</table>';
}

private function _getEmptyMatrix() {
return array_fill(0, 9, array_fill(0, 9, 0));
}

private function _solve($matrix) {
while(true) {
$options = array();
foreach ($matrix as $rowIndex => $row) {
foreach ($row as $columnIndex => $cell) {
if (!empty($cell)) {
continue;
}
$permissible = $this->_getPermissible($matrix, $rowIndex, $columnIndex);
if (count($permissible) == 0) {
return false;
}
$options[] = array(
'rowIndex' => $rowIndex,
'columnIndex' => $columnIndex,
'permissible' => $permissible
);
}
}
if (count($options) == 0) {
return $matrix;
}

usort($options, array($this, '_sortOptions'));

if (count($options[0]['permissible']) == 1) {
$matrix[$options[0]['rowIndex']][$options[0]['columnIndex']] = current($options[0]['permissible']);
continue;
}

foreach ($options[0]['permissible'] as $value) {
$tmp = $matrix;
$tmp[$options[0]['rowIndex']][$options[0]['columnIndex']] = $value;
if ($result = $this->_solve($tmp)) {
return $result;
}
}

return false;
}
}

private function _getPermissible($matrix, $rowIndex, $columnIndex) {
$valid = range(1, 9);
$invalid = $matrix[$rowIndex];
for ($i = 0; $i < 9; $i++) {
$invalid[] = $matrix[$i][$columnIndex];
}
$box_row = $rowIndex % 3 == 0 ? $rowIndex : $rowIndex - $rowIndex % 3;
$box_col = $columnIndex % 3 == 0 ? $columnIndex : $columnIndex - $columnIndex % 3;
$invalid = array_unique(array_merge(
$invalid,
array_slice($matrix[$box_row], $box_col, 3),
array_slice($matrix[$box_row + 1], $box_col, 3),
array_slice($matrix[$box_row + 2], $box_col, 3)
));
$valid = array_diff($valid, $invalid);
shuffle($valid);
return $valid;
}

private function _sortOptions($a, $b) {
$a = count($a['permissible']);
$b = count($b['permissible']);
if ($a == $b) {
return 0;
}
return ($a < $b) ? -1 : 1;
}

}

Usage is very simple, you can either pass to the constructor a two dimensional array representing the grid – 9 arrays of 9 elements – and then call the solve() method, or else do not pass anything in and call generate() to create a new puzzle. Either way the results can be displayed as a HTML table by calling the getHtml() method.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

$grid = array(
array(0,0,0,0,0,0,2,0,3),
array(8,0,7,0,0,0,0,6,0),
array(0,0,2,6,5,0,0,0,8),
array(0,3,0,0,0,0,0,0,0),
array(7,5,0,2,0,0,1,0,0),
array(0,0,1,0,3,0,5,0,0),
array(4,0,0,5,0,0,8,7,0),
array(6,0,0,0,4,2,0,0,0),
array(0,9,5,0,6,0,0,2,0)
);
$s = new Sudoku($grid);
$s->solve();
echo $s->getHtml();

$s2 = new Sudoku();
$s2->generate();
echo $s2->getHtml();

2 comments

Christian July 5, 2010 at 9:19 pm

I think your post is quite ingenious.
How did you conceive of the idea, and what has it meant to you?

Meaning, have you used this for a particular application, or was it for your own enjoyment? Have you created it it with the help of others ( a team effort) or was it your own work?

I find it very amusing. I myself am looking for an application for your class.

Christian
Karl July 5, 2010 at 11:16 pm

Hi Christian,

The algorithm used is clever, but not invented by me I just read about the algorithm here and implemented it in PHP.

I wrote this just for my own enjoyment really, and because I wanted to generate blank sudoku puzzles.

PHP Sodoku Solver Class

2 comments

Leave a Reply Cancel reply