# 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 (\$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);
// Remove keys from array
unset(\$possible[\$y][\$x]);
if (empty(\$possible[\$y])) {
unset (\$possible[\$y]);
}
continue;
}
}
}
}```
```/**
* 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);
}
}
}
}
}```
```/**
* 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);
}
}
}
}
}```
```/**
* 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

GitHub repository: f13dev/f13-sudoku-solver
Created: June 18, 2022 - 10:58am
Last commit: June 18, 2022 - 10:58am
Forks: 0
Open issues: 0
Stars: 0
Watchers: 0
Description: N/A
git clone https://github.com/f13dev/f13-sudoku-solver

This site uses Akismet to reduce spam. Learn how your comment data is processed.