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