# Using computers to solve Sudoku

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

## 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 co-ordinates to 3×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