Using computers to solve Sudoku

18 June 2022 by jim

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