[PHP] StateSolver

Programs which generate, solve, and analyze Sudoku puzzles

[PHP] StateSolver

Postby Guest » Mon Feb 06, 2006 12:28 am

Hello all..

I recently finished the PHP version of my StateSolving algorithm. It's probably not as fast as DLX but it's still really fast!

There are two PHP scripts i provide, the solver class itself, and a small example script on how to use the class.

A short explanation:
It works with 27 candidatelists (represented by a 9 bit integer). A single candidatelist (bitset if you like) for each row, column and region (3*9=27).

It works recursive and tries for every position, all the number that occurs on the corresponding row, column and region bitsets. If a number passes this test (occurs in the lists), it will be added at that position and excluded from the bitsets. Then it will try the next position by recursion.
If no suitable candidates are found, it will backtrack to the previous position and try the next suitable candidate.

(note: it is able to find ALL solutions but since a proper sudoku has only one solution, it has been disabled. If you disable the ready-flag checks (see code) you can put your multiple sudoku code at the line where the ready flag is set to true)

Thanks for reading and have fun with it:)

The example script - Sudoku.php
Code: Select all
<?php
    // Include the class
    include 'StateSolver.class.php';

    // This is what a given sudoku should look like (solution on the right)
    $sudoku = array(
    0,2,0,4,0,9,5,0,6,  // 321   489   576
    0,4,5,0,7,0,8,0,9,  // 645   173   829
    0,7,0,0,2,6,0,0,0,  // 879   526   413
    0,0,0,0,3,0,6,0,1,  // 587   234   691
    9,0,2,0,6,0,0,0,0,  // 912   865   347
    0,0,0,7,0,1,0,5,0,  // 436   791   258
    0,0,0,3,1,0,0,0,4,  // 258   317   964
    7,0,0,0,0,0,1,0,0,  // 794   658   132
    0,0,3,9,0,2,7,8,0); // 163   942   785

    // Instantiate the solver class
    $stateSolver = new StateSolver($sudoku);

    // Display the current sudoku
    DisplaySudoku($sudoku);

    // Obtain start time
    $beginTime = microtime();

    // Call the solver
    $stateSolver->findSolution();

    // Obtain end time
    $endTime = microtime();

    // Calculate the total time
    $totalTime = $endTime - $beginTime;

    echo 'Elapsed time: '.$totalTime.'ms<br />';

    // Display the solved sudoku
    DisplaySudoku($stateSolver->sudoku);

    function displaySudoku($sudoku) {
        for ($i = 0; $i < 81; $i++) {
            echo ' ' . $sudoku[$i] . ' ';

            if (($i + 1) % 9 == 0) {
                echo '<br />';
            }
        }
    }

?>


The solver class itself - StateSolver.class.php
Code: Select all
<?php

    /*  Sudoku State Solver v0.1 [04-feb-2006]
        --------------------------------------
            All code by Mark Jelsma
    */

    class StateSolver {

        /////////////////////////
        /// PUBLIC ATTRIBUTES ///
        /////////////////////////

        // Holds the sudoku puzzel as an array
        public $sudoku;

        //////////////////////////
        /// PRIVATE ATTRIBUTES ///
        //////////////////////////

        // Holds the 27 candidatelists as an array
        private $_candidates;

        // Holds the list of empty cells as an array
        private $_emptyCells;

        // Determines whether or not the algorithm has found a solution
        private $_ready;

        ////////////////////
        /// CONSTRUCTORS ///
        ////////////////////

        public function __construct($sudoku) {
            $this->sudoku = $sudoku;
        }

        //////////////////////
        /// PUBLIC METHODS ///
        //////////////////////

        // Initialize the solving algorithm
        public function findSolution() {
            $column = 0;
            $row = 0;
            $region = 0;
            $eIndex = 0;

            // Fill the candidatelists with all 9 bits set
            for ($i = 0; $i < 27; $i++) {
                $this->_candidates[$i] = 511;
            }

            // Exclude invalid candidates and get empty cells
            for ($i = 0; $i < 81; $i++) {
                if ($this->sudoku[$i] == 0) {
                    // Add this empty cell to the list
                    $this->_emptyCells[$eIndex++] = $i;
                } else {
                    // Exclude this number from the candidatelists
                    $this->_getCandidateLists($i, $column, $row, $region);

                    $this->_exclude($this->_candidates[$column], $this->sudoku[$i]);
                    $this->_exclude($this->_candidates[$row], $this->sudoku[$i]);
                    $this->_exclude($this->_candidates[$region], $this->sudoku[$i]);
                }
            }

            // Set the ready flag to false
            $this->_ready = false;

            // Run the recursive backtracking algorithm
            $this->_solve(0);
        }

        ///////////////////////
        /// PRIVATE METHODS ///
        ///////////////////////

        // Recursive backtracking solver
        private function _solve($eIndex) {
            $column = 0;
            $row = 0;
            $region = 0;

            // See if haven't reached the end of the pattern
            if ($eIndex < count($this->_emptyCells)) {

                // Get the corresponding candidatelists
                $this->_getCandidateLists($this->_emptyCells[$eIndex], $column, $row, $region);

                // Check if $i occurs in all three candidatelists
                for ($i = 1; $i < 10; $i++) {
                    if ($this->_isCandidate($this->_candidates[$column], $i) &&
                        $this->_isCandidate($this->_candidates[$row], $i) &&
                        $this->_isCandidate($this->_candidates[$region], $i)) {

                        // Suitable candidate found, use it!
                        $this->sudoku[$this->_emptyCells[$eIndex]] = $i;

                        // Exclude this number from the candidatelists
                        $this->_exclude($this->_candidates[$column], $i);
                        $this->_exclude($this->_candidates[$row], $i);
                        $this->_exclude($this->_candidates[$region], $i);

                        // Don't advance if a solution has been found
                        if ($this->_ready) return;

                        // Advance to the next cell
                        $this->_solve($eIndex + 1);

                        // Don't revert if a solution has been found
                        if ($this->_ready) return;

                        // Reset the cell
                        $this->sudoku[$this->_emptyCells[$eIndex]] = 0;

                        // Put the candidates back in the lists
                        $this->_include($this->_candidates[$column], $i);
                        $this->_include($this->_candidates[$row], $i);
                        $this->_include($this->_candidates[$region], $i);

                    }
                }
            } else {
                // A solution has been found, get out of recursion
                $this->_ready = true;
            }
        }

        // Obtains the corresponding candidatelist indices
        private function _getCandidateLists($position, &$column, &$row, &$region) {
            $column = $position % 9;
            $row = floor(9 + $position / 9);
            $region = floor(18 + floor($column / 3) + 3 * floor(($row - 9) / 3));
        }

        // Excludes a number from the list of candidates
        private function _exclude(&$bitSet, $bit) {
            $bitSet &= ~(1 << $bit -1);
        }

        // Includes a number into the list of candidates
        private function _include(&$bitSet, $bit) {
            $bitSet |= (1 << $bit - 1);
        }

        // Determines if number occurs in the specified list of candidates
        private function _isCandidate($bitSet, $bit) {
            return (($bitSet & (1 << $bit - 1)) == 0) ? false : true;
        }

    }

?>
Guest
 

Return to Software

cron