Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

[PHP] StateSolver

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Software
View previous topic :: View next topic  
Author Message
/\/\-ark/17

Joined: 05 Feb 2006
Posts: 1
:
Location: netherlands

Items
PostPosted: Sun Feb 05, 2006 11:28 pm    Post subject: [PHP] StateSolver Reply with quote

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 Smile

The example script - Sudoku.php
Code:

<?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:

<?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;
        }

    }

?>

_________________
highmode=on
Back to top
View user's profile Send private message Visit poster's website
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Software All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron