Introduction
I have enjoyed Sudoku puzzles for a while now and had the idea of trying to teach a computer to play Sudoku. This first release is fairly basic and you won’t have problems finding puzzles that it can’t complete, improvements to the algorithm can be added over time.
This works by programmatically checking each cell as a row, column or box to see if there is a single possible value for the cell. If only one possible value is found, this must be the correct one. Once all cells have been checked, the process starts again until either (a) all cells are filled or (b) too many iteration have passed and the puzzle is deemed unsolvable with the current algorithm.
Try the Sudoku solver
Enter the provided numbers on your chosen puzzle and click “Solve”, alternatively, click “Load demo” to load one of the few demonstration puzzles.
Please note: improvements are required to the solving algorithm, not all valid puzzles can be solved at present
Data structures
Internal handling of data
When a puzzle is loaded, the following arrays are created and populated:
- y[y][x] – y contains an array of rows, each containing an array of columns as cells
- x[x][y] – x contains an array of columns, each containing an array of rows as cells
- c[square][cell] – c contains an array of 3×3 squares, each containing an array of cells within the square
- p[y][x] – the puzzle that is to be solved, this array is not updated as the puzzle is solved and remains the same throughout
- s[y][x] – the solved version of the puzzle, this starts the same as p[y][x] and is filled in as numbers are calculated
Algorithm
The current algorithms have not yet been optimised and may be fairly inefficient.
Finding possible values
/**
* Find possible numbers for empty cells
*
* @return Array[][][]
*/
public function _get_possible() {
// Create an array to store possible values
$possible = array();
// Loop through the possible numbers
for ($n = 1; $n <= 9; $n++) {
// Loop through each cell [y,x]
for ($y = 1; $y <= 9; $y++) {
for ($x = 1; $x <= 9; $x++) {
// If a value is already set for this cell, skip to the next one
if ($this->s[$y][$x]) {
continue;
}
// Find which square this cell is in
$c = $this->_get_c_id($y, $x);
// Check if number is in row, column or square
if (
!in_array($n, $this->y[$y]) &&
!in_array($n, $this->x[$x]) &&
!in_array($n, $this->c[$c['cube']])
) {
// n is possible for this cell, add it to the possible array
$possible[$y][$x][] = $n;
}
}
}
}
// Return the possible array
return $possible;
}
Cells with one possible value
/**
* Check for any cells with a single possible value
*
* @param Array[][][] $possible Possible values
*/
public function _check_possible_single($possible) {
// Loop through cells in array [y][x]
foreach ($possible as $y => $ya) {
foreach ($ya as $x => $xa) {
// Check if there is only one possible answer for cell
if (count($xa) == 1) {
// Set value for this cell
$this->_set_s_cell($y, $x, $xa[0]);
// Remove keys from array
unset($possible[$y][$x]);
if (empty($possible[$y])) {
unset ($possible[$y]);
}
continue;
}
}
}
}
Searching rows
/**
* Check for rows containing a single possible location for n
*
* @param Array[][][] $possible Possible values
*/
public function _check_possible_y($possible) {
// Loop through rows
for ($y = 1; $y <= 9; $y++) {
if (!array_key_exists($y, $possible)) {
// If row doesn't exists in possible array, skip
continue;
}
// Loop through possible values
for ($n = 1; $n <= 9; $n++) {
// Set default found x, found y and counter
$fx = $fy = $count = 0;
// Loop through cells in row
foreach ($possible[$y] as $x => $xa) {
// Loop through possible values for each cell
foreach ($xa as $p) {
if ($p == $n) {
// If n is possible, set found x, found y and increment counter
$fx = $x;
$fy = $y;
$count++;
}
}
}
// Check if only one instance of n was found
if ($count == 1) {
// Set n as the cells value
$this->_set_s_cell($fy, $fx, $n);
// Remove array keys
unset($possible[$fy][$fx]);
if (empty($possible[$fy])) {
unset($possible[$fy]);
continue(2);
}
}
}
}
}
Searching columns
/**
* Check for columns containing a single possible location for n
*
* @param Array[][][] $possible Possible values
*/
public function _check_possible_x($possible)
{
// Create [x][y] array from [y][x] array
$possible_x = array();
foreach ($possible as $y => $ya) {
foreach ($ya as $x => $xa) {
$possible_x[$x][$y] = $xa;
}
}
// Loop through columns
for ($x = 1; $x <= 9; $x++) {
if (!array_key_exists($x, $possible_x)) {
// If column doesn't exists in possible array, skip
continue;
}
// Loop through possible values
for ($n = 1; $n <= 9; $n++) {
// Set default found x, found y and counter
$fx = $fy = $count = 0;
// Loop through cells in row
foreach ($possible_x[$x] as $y => $ya) {
// Loop through possible values for each cell
foreach ($ya as $p) {
if ($p == $n) {
// If n is possible, set found x, found y and increment counter
$fx = $x;
$fy = $y;
$count++;
}
}
}
// Check if only one instance of n was found
if ($count == 1) {
// Set n as the cells value
$this->_set_s_cell($fy, $fx, $n);
// Remove array keys
unset ($possible_x[$fx][$fy]);
if (empty($possible_x[$fx])) {
unset($possible_x[$fx]);
continue(2);
}
}
}
}
}
Searching boxes
/**
* Check for squares containing a single possible location for n
*
* @param Array[][][] $possible Possible values
*/
public function _check_possible_c($possible)
{
// Loop through possible values y axis
foreach ($possible as $y => $ya) {
// Loop through possible values x axis
foreach ($ya as $x => $xa) {
// Get the cells square value
$c = $this->_get_c_id($y, $x);
// Loop through possible numbers
for ($n = 1; $n <= 9; $n++) {
// Set default found y, found x and count
$fx = $fy = $count = 0;
// Loop through each cell in square array
foreach ($c['cells'] as $cell) {
if (array_key_exists($cell['y'], $possible) && array_key_exists($cell['x'], $possible[$cell['y']])) {
foreach ($possible[$cell['y']][$cell['x']] as $p) {
// If the possible number is found, set found y, found x and increment counter
if ($p == $n) {
$fx = $cell['x'];
$fy = $cell['y'];
$count++;
}
}
}
}
// If only one instance of n was found
if ($count == 1) {
// Set n for cell
$this->_set_s_cell($fy, $fx, $n);
// Remove array keys
unset ($possible[$fy][$fx]);
if (empty($possible[$fy])) {
unset($possible[$fy]);
continue(2);
}
}
}
}
}
}
Converting X Y coordinates to 3 x 3 squares
public function _get_c_id($y, $x)
{
switch ($y) {
case 1: case 2: case 3: $cy = 1; $cys = array(1, 2, 3); break;
case 4: case 5: case 6: $cy = 2; $cys = array(4, 5, 6); break;
case 7: case 8: case 9: $cy = 3; $cys = array(7, 8, 9); break;
}
switch ($x) {
case 1: case 2: case 3: $cx = 0; $cxs = array(1, 2, 3); break;
case 4: case 5: case 6: $cx = 3; $cxs = array(4, 5, 6); break;
case 7: case 8: case 9: $cx = 6; $cxs = array(7, 8, 9); break;
}
$cube = $cy+$cx;
switch ($y) {
case 1: case 4: case 7: $cy = 1; break;
case 2: case 5: case 8: $cy = 2; break;
case 3: case 6: case 9: $cy = 3; break;
}
switch ($x) {
case 1: case 4: case 7: $cx = 0; break;
case 2: case 5: case 8: $cx = 3; break;
case 3: case 6: case 9: $cx = 6; break;
}
$cell = $cy+$cx;
$cells = array();
foreach ($cys as $y) {
foreach ($cxs as $x) {
$cells[] = array(
'x' => $x,
'y' => $y,
);
}
}
return array(
'cube' => $cube,
'cell' => $cell,
'columns' => $cys,
'rows' => $cxs,
'cells' => $cells,
);
}
Future plans
The current algorithms implemented are suitable for completing most easy to medium puzzles. In future updates it would be useful to consider other factors such as a square which does not contain a number, yet all empty spaces are in the same row or column. In this case the number should be considered as being in this row or column when finding possible values
Occasionally puzzles surface where some guess work and back tracking is required to successfully complete the puzzle. To solve such puzzles some guesswork is required. A backup bruit force algorith would help to solve these puzzles at the cost of reduced optimisation.
GitHub
Last commit: June 18, 2022 - 10:58am
Forks: 0
Open issues: 0
Stars: 0
Watchers: 0
No comments on Using computers to solve Sudoku