Scripting Corner
PHP:
Sudoku Class
view demo
<?php
/* ---------------------------------------------------------
LX' Sudoku Class
(c) 2006 Alexander Schulze
---------------------------------------------------------
This program is free software; you can redistribute
it and/or modify it under the terms of the GNU General
Public License as published by the Free Software
Foundation; either version 2 of the License, or (at
your option) any later version.
This program is distributed in the hope that it will
be useful, but WITHOUT ANY WARRANTY; without even the
implied warranty of MERCHANTABILITY or FITNESS FOR A
PARTICULAR PURPOSE. See the GNU General Public License
for more details.
You should have received a copy of the GNU General Public
License along with this program; if not, write to the
Free Software Foundation, Inc., 51 Franklin Street, Fifth
Floor, Boston, MA 02110-1301, USA.
---------------------------------------------------------
Authors: Alexander Schulze
Contact: http://www.lxhome.de/
---------------------------------------------------------
Changelog:
v1.0 2006-04-17: first version publically available
--------------------------------------------------------- */
class Sudoku
{
var $zeichensatz; // used characters in sudoku (1-9)
var $groesse; // size of board (9)
var $kl_groesse; // size of a small square (3)
var $matrix; // sudoku data structure
var $changed; // if a solver iteration changed anything
var $col_cache, $row_cache, $box_cache;
// constructor
function Sudoku ( &$sudokustring, &$zeichenstring )
{
// define charset and therefore size of the board
$this -> zeichensatz = explode ( ' ', $zeichenstring );
$this -> groesse = count ( $this -> zeichensatz );
$this -> kl_groesse = floor ( sqrt ( $this -> groesse ) );
// initialize caches
$this -> col_cache = array();
$this -> row_cache = array();
$this -> box_cache = array();
// create and fill data structure
$this -> createMatrix ( $sudokustring );
$this -> firstFill();
}
// convert string into sudoku matrix
function createMatrix ( &$string )
{
// linebreaks
$nl = array ( "\r\n", "\n\r", "\n", "\r" );
// split string into its elements
if ( !strpos ( $string, ' ' ) )
$temp = preg_split ( '//', str_replace ( $nl, '', $string ), -1, PREG_SPLIT_NO_EMPTY );
else
$temp = explode ( ' ', str_replace ( $nl, ' ', $string ) );
for ( $zeile = 0; $zeile < $this -> groesse; $zeile++ )
{
$row = $zeile % $this -> kl_groesse;
// split into small squares
for ( $spalte = 0; $spalte < $this -> groesse; $spalte++ )
{
$kasten = floor ( $zeile / $this -> kl_groesse ) * $this -> kl_groesse +
floor ( $spalte / $this -> kl_groesse );
$col = $spalte % $this -> kl_groesse;
$this -> matrix [ $kasten ]
[ $row ]
[ $col ] = $temp [ ( $zeile * $this -> groesse + $spalte ) ] ;
}
}
}
// fill empty fields with possibilities
function firstFill()
{
for ( $i = 0; $i < $this -> groesse; $i++ )
{
$box = $this -> getBox ( $i );
// every non-used symbol is added as possibility
foreach ( $this -> zeichensatz as $zeichen )
{
if ( !in_array ( $zeichen, $box ) )
{
for ( $j = 0; $j < $this -> groesse; $j++ )
{
if ( $box [ $j ] == 0 )
$box [ $j ] = array ( $zeichen );
elseif (is_array ( $box [ $j ] ) )
$box [ $j ][] = $zeichen;
}
}
}
}
}
// output sudoku as HTML table
function showSudoku_Matrix ( $kommentar = '' )
{
$ret = '<table cellspacing="0" cellpadding="0" title="' . $kommentar . '">';
// small squares
foreach ( $this -> matrix as $key => $kasten )
{
if ( $key % $this -> kl_groesse == 0 ) $ret .= '<tr>';
$ret .= "<td>\n\n<table>\n";
// columns inside a square
foreach ( $kasten as $spalte )
{
$ret .= '<tr>';
// cells in each column
foreach ( $spalte as $werte )
{
if ( is_array ( $werte ) )
{
if ( count ( $werte ) == 1 )
{
foreach ( $werte as $val ) $ret .= '<td class="solved">' . htmlspecialchars ( $val );
}
elseif ( count ( $werte ) == 0 )
{
$ret .= '<td class="error">';
}
else
{
sort ( $werte );
$ret .= '<td class="possibilities" title="'.implode ( ' ', $werte ).'">'.htmlspecialchars ( implode ( ' ', $werte ) );
}
}
else
{
$ret .= '<td class="start">';
$ret .= ( $werte ) ? htmlspecialchars ( $werte ) : ' ';
}
$ret .= '</td>';
}
$ret .= "</tr>\n";
}
$ret .= "</table>\n\n</td>";
if ( $key % $this -> kl_groesse == $this -> kl_groesse - 1 ) $ret .= '</tr>';
}
$ret .= '</table>';
return $ret;
}
// the solver
function solve ( $step )
{
$this -> changed = true;
// true if not the first iteration
// used to speed up search because after the first iteration you don't
// have to check against fields that were already known at the beginning
$notfirst = false;
while ( !$this -> checkWin() && $this -> changed )
{
$this -> changed = false;
if ( $step [ 0 ] )
{
for ( $i = 0; $i < $this -> groesse; $i++ )
{
// filter values that are already known from the combinations of possibilities
$this -> kill ( $this -> getRow ( $i ), $notfirst );
$this -> kill ( $this -> getCol ( $i ), $notfirst );
$this -> kill ( $this -> getBox ( $i ), $notfirst );
}
$notfirst = true;
if ( $this -> changed ) continue;
}
if ( $step [ 1 ] )
{
for ( $i = 0; $i < $this -> groesse; $i++ )
{
// sets fields that are the only one in one set to allow a certain value
$this -> setUnique ( $this -> getRow ( $i ) );
if ( $this -> changed ) continue 2;
$this -> setUnique ( $this -> getCol ( $i ) );
if ( $this -> changed ) continue 2;
$this -> setUnique ( $this -> getBox ( $i ) );
if ( $this -> changed ) continue 2;
}
}
if ( $step [ 2 ] )
{
for ( $i = 0; $i < $this -> groesse; $i++ )
{
// checks for identical combinations of possibilities which would exclude
// the elements of those combinations in all the other ones
$this -> checkIdentical ( $this -> getRow ( $i ) );
if ( $this -> changed ) continue 2;
$this -> checkIdentical ( $this -> getCol ( $i ) );
if ( $this -> changed ) continue 2;
$this -> checkIdentical ( $this -> getBox ( $i ) );
if ( $this -> changed ) continue 2;
}
}
if ( $step [ 3 ] )
{
for ( $i = 0; $i < $this -> groesse; $i++ )
{
// checks for subsets of combinations that are identical and would exclude those elements
// that are not part of that subset
$this -> checkCombination ( $this -> getRow ( $i ) );
if ( $this -> changed ) continue 2;
$this -> checkCombination ( $this -> getCol ( $i ) );
if ( $this -> changed ) continue 2;
$this -> checkCombination ( $this -> getBox ( $i ) );
if ( $this -> changed ) continue 2;
}
}
if ( $step [ 4 ] )
{
for ( $i = 0; $i < $this -> groesse; $i++ )
{
if ( $this -> guess ( $i, $step ) === true ) continue 2;
}
}
}
return $this -> checkWin();
}
//////
// helper functions to get access to the parts of the sudoku more easily
//////
// returns a reference to a row of the sudoku
function &getRow ( $zeile )
{
if ( !isset ( $this -> row_cache [ $zeile ] ) )
{
$row = $zeile % $this -> kl_groesse;
for ( $spalte = 0; $spalte < $this -> groesse; $spalte++ )
{
$kasten = floor ( $zeile / $this -> kl_groesse ) * $this -> kl_groesse +
floor ( $spalte / $this -> kl_groesse );
$col = $spalte % $this -> kl_groesse;
$temp[] =& $this -> matrix [ $kasten ]
[ $row ]
[ $col ];
}
$this -> row_cache [ $zeile ] =& $temp;
}
return $this -> row_cache [ $zeile ];
}
// returns a reference to a column of the sudoku
function &getCol ( $spalte )
{
if ( !isset ( $this -> col_cache [ $spalte ] ) )
{
$col = $spalte % $this -> kl_groesse;
for ( $zeile = 0; $zeile < $this -> groesse; $zeile++ )
{
$kasten = floor ( $zeile / $this -> kl_groesse ) * $this -> kl_groesse +
floor ( $spalte / $this -> kl_groesse );
$row = $zeile % $this -> kl_groesse;
$temp[] =& $this -> matrix [ $kasten ]
[ $row ]
[ $col ];
}
$this -> col_cache [ $spalte ] =& $temp;
}
return $this -> col_cache [ $spalte ];
}
// returns a reference to a small square of the sudoku
function &getBox ( $box )
{
if ( !isset ( $this -> box_cache [ $box ] ) )
{
foreach ( $this -> matrix [ $box ] as $x => $row )
foreach ( $row as $y => $col )
$temp[] =& $this -> matrix [ $box ][ $x ][ $y ];
$this -> box_cache [ $box ] =& $temp;
}
return $this -> box_cache [ $box ];
}
// checks if the sudoku is already solved
// TODO: not only check if every field is filled but also if the fillings are correct :)
function checkWin()
{
for ( $i = 0; $i < $this -> groesse; $i++ )
{
$box = $this -> getBox ( $i );
for ( $j = 0; $j < $this -> groesse; $j++ )
{
if ( ( is_array ( $box [ $j ] ) && count ( $box [ $j ] ) > 1 ) ||
( is_array ( $box [ $j ] ) && count ( $box [ $j ] ) == 0 ) ) return false;
}
}
return true;
}
//////
// solving algorithms
//////
// filter values that are already known from the combinations of possibilities
function kill ( &$data, $notfirst )
{
foreach ( $data as $key => $val )
{
// compare against the known elements from the beginning
if ( /*!$notfirst && */!is_array ( $val ) )
{
for ( $i = 0; $i < $this -> groesse; $i++ )
{
if ( !is_array ( $data [ $i ] ) ) continue;
$d = array_search ( $val, $data [ $i ] );
if ( $d !== false )
{
unset ( $data [ $i ][ $d ] );
$this -> changed = true;
}
}
}
// compare against elements already found out
elseif ( is_array ( $val ) && count ( $val ) == 1 )
{
$val = array_pop ( $val );
for ( $i = 0; $i < $this -> groesse; $i++ )
{
if ( $i == $key || !is_array ( $data [ $i ] ) ) continue;
$d = array_search ( $val, $data [ $i ] );
if ( $d !== false )
{
unset ( $data [ $i ][ $d ] );
$this -> changed = true;
}
}
}
}
}
// sets fields that are the only one in one set to allow a certain value
function setUnique ( &$data )
{
foreach ( $this -> zeichensatz as $zeichen )
{
$temp = array();
for ( $i = 0; $i < $this -> groesse; $i++ )
{
if ( !is_array ( $data [ $i ] ) || count ( $data [ $i ] ) == 1 ) continue;
if ( array_search ( $zeichen, $data [ $i ] ) !== false )
{
if ( count ( $temp ) < 1 )
$temp [ 0 ] = $i;
else
continue 2;
}
}
if ( !isset ( $temp [ 0 ] ) ) continue;
$data [ $temp [ 0 ] ][ 0 ] = $zeichen;
for ( $i = 1; $i < $this -> groesse; $i++ ) unset ( $data [ $temp [ 0 ] ][ $i ] );
$this -> changed = true;
}
}
// if x combinations exist that include the same x possibilities
// then those possibilities can be excluded from all other combinations of the same set
function checkIdentical ( &$data )
{
foreach ( $data as $key => $val )
{
if ( !is_array ( $val ) ) continue;
$valcount = count ( $val );
if ( $valcount == 1 ) continue;
$temp = array ( $key );
for ( $i = 0; $i < $this -> groesse; $i++ )
{
$datacount = count ( $data [ $i ] );
if ( !is_array ( $data [ $i ] ) || $datacount == 1 || $key == $i ) continue;
if ( $valcount == $datacount )
{
$schnittmenge = array_intersect ( $val, $data [$i ] );
if ( $val == $schnittmenge )
$temp[] = $i;
}
}
if ( count ( $temp ) == $valcount )
{
// remove elements from all combinations but $temp
foreach ( $val as $wert )
{
for ( $i = 0; $i < $this -> groesse; $i++ )
{
if ( !is_array ( $data [ $i ] ) || in_array ( $i , $temp ) ) continue;
$d = array_search ( $wert, $data [ $i ] );
if ( $d !== false )
{
$this -> changed = true;
unset ( $data [ $i ][ $d ] );
}
}
}
}
}
}
// similar to the method above, only this time subsets of combinations are checked
// if subsets are identical then all other possibilities that are not part of the subset
// can be excluded from those combinations
function checkCombination ( &$data )
{
foreach ( $this -> zeichensatz as $zeichen )
{
$schnittmenge = array ( $zeichen );
$elements = array();
// find all combinations that contain this symbol
for ( $i = 0; $i < $this -> groesse; $i++ )
{
if ( !is_array ( $data [ $i ] ) || count ( $data [ $i ] ) == 1 ) continue;
if ( in_array ( $zeichen, $data [ $i ] ) ) $elements[] = $i;
}
// find common intersections of those combinations
if ( count ( $elements ) >= 2 )
{
$schnittmenge = array_intersect ( $data [ $elements [ 0 ] ], $data [ $elements [ 1 ] ] );
if ( count ( $schnittmenge ) < count ( $elements ) ) continue;
for ( $i = 2; $i < count ( $elements ); $i++ )
{
$schnittmenge = array_intersect ( $schnittmenge, $data [ $elements [ $i ] ] );
if ( count ( $schnittmenge ) < count ( $elements ) ) continue 2;
}
// check if other combinations contain elements of that intersection
for ( $i = 0; $i < $this -> groesse; $i++ )
{
if ( in_array ( $i, $elements ) || !is_array ( $data [ $i ] ) ) continue;
$schnittmenge = array_diff ( $schnittmenge, $data [ $i ] );
if ( count ( $schnittmenge ) < count ( $elements ) ) continue 2;
}
if ( count ( $schnittmenge ) == count ( $elements ) )
{
foreach ( $elements as $el )
{
$data [ $el ] = array_intersect ( $data [ $el ], $schnittmenge );
}
}
}
}
}
// the most stupid (and resource eating) algorithm: trial and error
// just guesses one value and then checks if the sudoku can be solved this way or if
// it runs into inconsistencies
function guess ( $box, $step )
{
// make a copy of the current state
$kopie = unserialize ( serialize ( $this ) );
$kopie -> col_cache = array();
$kopie -> row_cache = array();
$kopie -> box_cache = array();
foreach ( $this -> matrix [ $box ] as $x => $col )
foreach ( $col as $y => $val )
{
if ( is_array ( $val ) && count ( $val ) > 1 )
{
foreach ( $val as $guess )
{
$kopie -> matrix [ $box ][ $x ][ $y ] = array ( $guess );
if ( $kopie -> solve ( $step ) === true )
{
$this -> matrix [ $box ][ $x ][ $y ] = array ( $guess );
$this -> changed = true;
return true;
}
}
}
}
return false;
}
}
?>