## 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

**Created**: June 18, 2022 - 10:58am

**Last commit**: June 18, 2022 - 10:58am

**Forks**: 0

**Open issues**: 0

**Stars**: 0

**Watchers**: 0

## No comments on Using computers to solve Sudoku