SolveDoku Source Code
SolveDoku is written in PHP (for version 5+), and released under the MIT Licence. Please let me know of any bugs/errors/improvements. Have fun!
Download SolveDoku Source Code
LICENSE: This source file is subject to the MIT license that is available through the world-wide-web at the following URI: http://www.opensource.org/licenses/mit-license.html.
Copyright (c) 2006 Simon Greenhill, dev@simon.net.nz
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
<?php
/**
* SolveDoku - a sudoku solver for php
*
* PHP version 5
*
* LICENSE: This source file is subject to the MIT license
* that is available through the world-wide-web at the following URI:
* http://www.opensource.org/licenses/mit-license.html.
*
* Copyright (c) 2006 Simon Greenhill
*
* Permission is hereby granted, free of charge, to any person obtaining a
* copy of this software and associated documentation files (the "Software"),
* to deal in the Software without restriction, including without limitation
* the rights to use, copy, modify, merge, publish, distribute, sublicense,
* and/or sell copies of the Software, and to permit persons to whom the
* Software is furnished to do so, subject to the following conditions:
*
* The above copyright notice and this permission notice shall be included
* in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
* OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
* DEALINGS IN THE SOFTWARE.
*
*
* @package solvedoku
* @author Simon Greenhill <simon@simon.net.nz>
* @copyright 2006 Simon Greenhill
* @license http://www.opensource.org/licenses/mit-license.html MIT License
* @version 0.2
* @link http://solvedoku.simon.net.nz/source
*
*/
class SolveDoku
{
/**
TO DO:
1 - make it so that this can handle different sized boards
2 - compress the board id's ( hex? )
3 - enhance the global search to ignore numbers that have 9 solved cells
Terminology::
[ BLOCK ] [ BLOCK ] [ BLOCK ]
column -----------------------------------
/ r AA AB AC AD AE AF AG AH AI
BLOCK o BA BB BC BD BE BF BG BH BI
\ w CA CB CC CD CE CF CG CH CI
|
/ | DA DB DC DD DE DF DG DH DI
BLOCK | EA EB EC ED EE EF EG EH EI
\ | FA FB FC FD FE FF FG FH FI
|
/ | GA GB GC GD GE GF GG GH GI
BLOCK | HA HB HC HD HE HF HG HH HI
\ | IA IB IC ID IE IF IG IH II
*/
// how many cells we still have to solve
public $to_solve = 81; // = 9 cells * 9 cells
// row and column id's - gives us something to loop through.
public $rows = array( 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I' );
public $cols = array( 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I' );
// what values each cell can be
private $possible_values = array( 1, 2, 3, 4, 5, 6, 7, 8, 9 );
// debugging flag. If set to true, will dump status information;
public $debug = false;
// stores a list of cells that conflict
public $errors = array( );
// "solved status"
public $status = 0;
// block membership tables - which cells belong to each block of cells.
public $blocks = array(
1 => array( 'AA', 'AB', 'AC', 'BA', 'BB', 'BC', 'CA', 'CB', 'CC' ),
2 => array( 'AD', 'AE', 'AF', 'BD', 'BE', 'BF', 'CD', 'CE', 'CF' ),
3 => array( 'AG', 'AH', 'AI', 'BG', 'BH', 'BI', 'CG', 'CH', 'CI' ),
4 => array( 'DA', 'DB', 'DC', 'EA', 'EB', 'EC', 'FA', 'FB', 'FC' ),
5 => array( 'DD', 'DE', 'DF', 'ED', 'EE', 'EF', 'FD', 'FE', 'FF' ),
6 => array( 'DG', 'DH', 'DI', 'EG', 'EH', 'EI', 'FG', 'FH', 'FI' ),
7 => array( 'GA', 'GB', 'GC', 'HA', 'HB', 'HC', 'IA', 'IB', 'IC' ),
8 => array( 'GD', 'GE', 'GF', 'HD', 'HE', 'HF', 'ID', 'IE', 'IF' ),
9 => array( 'GG', 'GH', 'GI', 'HG', 'HH', 'HI', 'IG', 'IH', 'II' ),
);
// reverse map of the blocks to help lookups, generated at construct time
public $reverse_blocks = array( );
// a map of the blocks relationships -
// i.e. block x is horiz & vert. next to which other blocks
public $block_relationship = array(
1 => array( 2, 3, 4, 7 ),
2 => array( 1, 3, 5, 8 ),
3 => array( 1, 2, 6, 9 ),
4 => array( 1, 7, 5, 6 ),
5 => array( 2, 4, 6, 8 ),
6 => array( 3, 9, 4, 5 ),
7 => array( 1, 4, 8, 9 ),
8 => array( 2, 5, 7, 9 ),
9 => array( 3, 6, 7, 8 ),
);
// cell storage array
public $cells = array( );
// how many times have we been around the solve loop?
public $iteration_count = 0;
# ----------------------------------------------------------- #
/**
* Constructor
* @return void
*/
function __construct( )
{
// go through each row, and each column in each row and create a cell
// for each position, and fill it with all possible values.
foreach( $this->rows as $row )
{
foreach( $this->cols as $col )
{
// the key for each cell is their row location by their col
// location, i.e. AB is row A, column B
$key = $this->make_key( $row, $col );
$this->cells[ $key ] = $this->possible_values;
}
}
// build reverse map of blocks to speed up cell look ups:
foreach( $this->blocks as $blocknum=>$cells )
{
foreach( $cells as $cell )
{
$this->reverse_blocks[ $cell ] = $blocknum;
}
}
}
/**
* helper function to make a key for the given co-ordinates ( see map )
* @param string $row row value ( 'A' - 'I' )
* @param string $col column value ( 'A' - 'I' )
* @return string
*/
function make_key( $row, $col )
{
return $row.$col;
}
/**
* helper function to decompose a key for the given co-ordinates ( see map )
* @param string $key two character key value ( 'AA' - 'II' )
* @return array
*/
function break_key( $key )
{
return array( $key{ 0 }, $key{ 1 } );
}
/**
* works out which block this key is in
* @param string $key Cell key value ( 'AA' - 'II' )
* @param integer $block_id block id value
* @see blocks
* @see reverse_blocks
* @return integer
*/
function get_block_id( $key )
{
return $this->reverse_blocks[ $key ];
}
/**
* sets a cell to a given value
* @param string $row row value ( 'A' - 'I' )
* @param string $col column value ( 'A' - 'I' )
* @param integer $value value of cell ( 1 - 9 )
* @return void
*/
function set( $row, $col, $value )
{
$value = (int) $value;
// work out the key of this cell, and set it to the desired value
$key = $this->make_key( $row, $col );
$this->cells[ $key ] = $value;
// loop through all cells in this row/column/block and remove the
// value for the possible values lists for them ( since they CANNOT )
// be this value now.
foreach( $this->cells_in_rcb( $row, $col ) as $bkey )
{
$values = $this->cells[ $bkey ];
if( is_array( $values ) && in_array( $value, $values ) )
{
$this->cells[ $bkey ] = array_diff( $values, array( $value ) );
}
}
// update the still to be solved counter.
$this->to_solve--;
}
/**
* helper function to return all the cell keys in the given row
* @param string $row row value ( 'A' - 'I' )
* @see cells_in_col
* @see cells_in_block
* @see cells_in_rbc
* @return array
*/
function cells_in_row( $row )
{
$out = array();
foreach ( $this->cols as $col )
{
$out[] = $this->make_key( $row, $col );
}
return $out;
}
/**
* helper function to return all the cells in the given column
* @param string $col col value ( 'A' - 'I' )
* @see cells_in_row
* @see cells_in_block
* @see cells_in_rbc
* @return array
*/
function cells_in_col( $col )
{
$out = array();
foreach ( $this->rows as $row )
{
$out[] = $this->make_key( $row, $col );
}
return $out;
}
/**
* helper function to return all the cells in the given block
* @param string $row row value ( 'A' - 'I' )
* @param string $col col value ( 'A' - 'I' )
* @see cells_in_row
* @see cells_in_col
* @see cells_in_rbc
* @return array
*/
function cells_in_block( $row, $col )
{
$original_key = $this->make_key( $row, $col );
$block_id = $this->get_block_id( $original_key );
$out = array();
// loop through all cells in this block.
foreach( $this->blocks[ $block_id ] as $key )
{
$out[] = $key;
}
return $out;
}
/**
* combines all the other cells_in_* functions into one handy function
* which gets a list of all the cells in the same row, column, and block
* as this cell
* @param string $row row value ( 'A' - 'I' )
* @param string $col col value ( 'A' - 'I' )
* @see cells_in_row
* @see cells_in_col
* @see cells_in_block
* @return array
*/
function cells_in_rcb( $row, $col )
{
$out = array();
$out = array_merge( $out, $this->cells_in_row( $row ) );
$out = array_merge( $out, $this->cells_in_col( $col ) );
$out = array_merge( $out, $this->cells_in_block( $row, $col ) );
$out = array_unique( $out );
return $out;
}
/**
* the main solve function, performs one iteration calling the solve
* techniques.
* @see solve_singles
* @see global_search
* @return void
*/
function solve( )
{
// we'll probably have a few immediately ( hopefully! ) from the
// the setting of initial values.
$this->solve_singles();
// try a "global search" for each number-
// i.e. narrow down by numbers across entire board
foreach( $this->possible_values as $number )
{
$this->global_search( $number );
}
$this->iteration_count++;
}
/**
* Solves "singles" - i.e. entries in the cell list that have only
* one single possible value - these will occur either after initialisation
* or when a block / row / column is nearly filled, and we can exclude all
* other values.
* @see global_search
* @see set
* @return void
*/
function solve_singles( )
{
// go through each cell, and if it hasn't been solved ( i.e. is an array )
// and only has one value ( i.e. is a "single" ), then solve this cell
foreach( $this->cells as $key=>$values )
{
if ( is_array( $values ) && count( $values ) == 1 )
{
list( $row, $col ) = $this->break_key( $key );
$value = array_pop( $values );
$this->set( $row, $col, $value );
if ( $this->debug )
{
echo 'SS: Solved '.$key.'=>'.$value."\n";
}
} // end if ( is array ...
} // end foreach( ...
}
/**
* Main search function - trys to guess what cell should be what based on
* a global search i.e. given all occurances of $number, which other cells
* HAVE to be $number?
* @param integer $number - the number to solve for.
* @see solve_singles
* @see set
* @return void
*/
function global_search( $number )
{
$cells = $this->cells; // copy the current cell map
// loop through all the cells and work out where this number cannot be.
// all non-possible locations are replaced with an 'x',
// ( more to help me visualise & debug this, than for any other reason )
foreach( $cells as $key=>$values )
{
// if the current cell value is the same as the number we're
// looking for, then it's been solved, and we can write off all
// cells in this cells row, column, and block ( since they cannot
// be the same as the number )
if ( $values == $number )
{
list( $row, $col ) = $this->break_key( $key );
foreach( $this->cells_in_rcb( $row, $col ) as $ckey )
{
//echo $ckey.',';
$cells[ $ckey ] = 'x';
}
}
// otherwise, if the value has been solved, but isn't the number
// we're currently interested in, then just black out this cell.
else if ( is_numeric( $values ) )
{
$cells[ $key ] = 'x';
}
// if the cell is not solved, and we haven't already blocked it
// then we'll just set it to "." as a marker for "empty" cell
else if ( $cells[ $key ] != 'x' )
{
$cells[ $key ] = '.';
}
} // end foreach
// now go through each block and look for ones which ONLY have
// one free/empty entry - this has to be the position that $number fits
// into, so solve it.
for( $block_id = 1; $block_id <= 9; $block_id++ )
{
// hack: grab the first cell in the blocks array for this block id
// and use that to get a key for use in cells_in_block
$some_key = $this->blocks[ $block_id ][ 0 ];
list( $row, $col ) = $this->break_key( $some_key );
$locations = array( );
foreach( $this->cells_in_block( $row, $col ) as $key )
{
// if the local copy of this cell is ".", then add it to
// the possible locations array.
if( $cells[ $key ] == '.' )
{
$locations[] = $key;
}
}
// if we only have ONE location, then this MUST be where the
// current number slots in. Solve it.
if ( count( $locations ) == 1 )
{
if ( $this->debug )
{
echo 'GS: Solved '.$locations[ 0 ].'=>'.$number."\n";
}
list( $row, $col ) = $this->break_key( array_pop( $locations ) );
$this->set( $row, $col, $number );
}
} // end for ( $block_id = 1; $block_id <= 9; $block_id++ )
if ( $this->debug )
{
// plots a pretty table of where this value can't be for debugging:
echo "--------- $number ----------\n";
// row and column counters, used to work out when to space out the
// blocks in the output.
$rc = 0; // row counter
$cc = 0; // column counter
foreach( $this->rows as $row )
{
$rc++;
foreach( $this->cols as $col )
{
$cc++;
$key = $this->make_key( $row, $col );
echo $cells[ $key ].' ';
if( $cc % 3 == 0 ){ echo "\t"; }
} // end foreach this->cols
if ( $rc % 3 == 0 ){ echo "\n"; }
echo "\n";
} // end foreach this->rows..
} // end debug
}
/**
* solve to completion - repeatedly calls solve until the board has been
* solved (returns true), or is impossible to solve ( -1 ), or has taken
* too long to solve ( -2 ).
* @see solve
* @return true|-1|-2|-3 solved, impossible to solve, taking too long to solve, invalid input
*/
function solve_to_completion()
{
$counter = 1; // how many times around the loop.
// check for valid input, if it's not valid then we will fail
if ( ! $this->validate_input( ) )
{
$this->status = -3;
return $this->status;
}
// these two flags are here to prevent us from looping for ever
// on an unsolvable sudoku.
// if the number of entries to solve ( $this->to_solve ) stays the
// same as the previous time around the loop ( $to_solve_before )
// then we'll add to our fail_count. Once fail_count gets too large,
// say 5 fails, then we'll give up. We don't fail immediately on
// a fail, as we could still be cutting down the possible values for
// a few cycles.
$to_solve_before = $this->to_solve;
$fail_count = 0;
while( $this->to_solve > 0 )
{
$this->solve();
if ( $this->debug )
{
echo 'Iteration: '.$counter.' -> '.$this->to_solve."\n";
echo "================================================\n";
$this->dump_asciidoku( );
}
$counter++;
if ( $this->to_solve == $to_solve_before )
{
$fail_count++;
if ( $fail_count == 5 )
{
$this->status = -1;
return $this->status;
}
}
else
{
$fail_count = 0; // reset fail counter.
}
// holy crap this has gone on for far too long. I give up
if ( $counter > 100 )
{
$this->status = -2;
return $this->status;
}
// update the still to solve check.
$to_solve_before = $this->to_solve;
}
// solved!
$this->status = true;
return $this->status;
}
/**
* validate input
* makes sure a board has valid input
* @return true|false, valid input, invalid input
*/
function validate_input( )
{
// go through each cell in each row and column
// and if the cell has a set value, then check if there is the
// SAME number in the current row/column/block
foreach( $this->rows as $row )
{
foreach( $this->cols as $col )
{
$key = $this->make_key( $row, $col );
if ( in_array( $this->cells[ $key ], $this->possible_values ) )
{
$value = $this->cells[ $key ];
foreach( $this->cells_in_rcb( $row, $col ) as $current_cell )
{
if (
( $current_cell !== $key ) &&
( $this->cells[ $current_cell ] === $value )
)
{
$this->errors[ $key ] = $current_cell;
}
}
}
}
} // end foreach $this->rows as $row
if ( count( $this->errors ) > 0 )
{
return false;
}
else
{
return true;
}
}
/**
* debug function to dump the stored data as a table
* if passed a "map", it'll dump that instead ( i.e. for debugging )
* otherwise it'll dump this->cells
* @param array $map -
* @return void
*/
function dump_status( $map = false )
{
$cells = ( $map === false ) ? $this->cells : $map;
echo "\n\n";
// go through each row and column
foreach ( $this->rows as $row )
{
foreach( $this->cols as $col )
{
// if the cell has been "solved", then show what it is,
// if it hasn't then show what it could be ( i.e. possible_values )
$key = $this->make_key( $row, $col );
echo $key.":\t";
if ( is_array( $cells[ $key ] ) )
{
foreach( $cells[ $key ] as $n )
{
echo $n.' ';
}
}
else // solved value
{
echo '-'.$cells[ $key ].'-';
}
echo "\n";
}
echo "\n";
}
}
/**
* debug function to dump the array as a ascii formatted sudoku table
* if passed a "map", it'll dump that instead ( i.e. for debugging )
* otherwise it'll dump this->cells
* @param array $map -
* @return void
*/
function dump_asciidoku( $map = false )
{
$cells = ( $map === false ) ? $this->cells : $map;
// go through each row and column
$cc = 0; $rc = 0;
foreach ( $this->rows as $row )
{
$rc++;
foreach( $this->cols as $col )
{
$cc++;
// if the cell has been "solved", then show what it is,
// if it hasn't then show what it could be ( i.e. possible_values )
$key = $this->make_key( $row, $col );
if ( is_array( $cells[ $key ] ) )
{
echo ' _ ';
}
else // solved value
{
echo ' '.$cells[ $key ].' ';
}
if( $cc % 3 == 0 ) { echo "\t"; }
}
if( $rc % 3 == 0 ) { echo "\n"; }
echo "\n";
}
}
/**
* makes a unique id for this sudoku board - this is used to make a quick
* data entry format.
*
* returns a 81 character string where each position specifies a value
* from row A, col A ( position 0), to row I, position I ( pos 81 )
* if the value in that position is non-zero, then it's solved. If
* it is exactly zero, then it has not been solved.
*
* @return string $id - board id string
*/
function make_board_id( )
{
$out = '';
foreach ( $this->rows as $row )
{
$rowbuff = '';
foreach ( $this->cols as $col )
{
// get the value for this row:col
$value = $this->cells[ $this->make_key( $row, $col ) ];
// if the cell has been solved, then append the value
// if it hasn't, then append a 0
if ( is_numeric( $value ) && in_array( $value, $this->possible_values ) )
{
$rowbuff .= (string) $value;
}
else if( is_array( $value ) )
{
$rowbuff .= 0;
}
}
$out .= $rowbuff;
}
return $out;
}
/**
* bootstraps the internal cell structure from a board id string
*
* @see make_board_id
* @param string $id - board id string
* @return true|false success, invalid board id string.
*/
function load_board_id( $id )
{
// die immediately if it's not 81 characters
if ( strlen( $id ) !== 81 )
{
return false;
}
$pos = 0;
foreach ( $this->rows as $row )
{
foreach ( $this->cols as $col )
{
$key = $this->make_key( $row, $col );
$value = (int) $id{ $pos };
if ( in_array( $value, $this->possible_values ) )
{
$this->set( $row, $col, $value );
}
$pos++;
}
}
return true;
}
}
/*
EXAMPLE USAGE:
// Step one: Create a sudoku object
$b = new SolveDoku( );
//step 2, add some initial values
//e.g. given this board, set the values using 'set' which takes a row coordinate
//(A-I), a column coordinate (A-I), and a value ( 1-9 )
// ------------------ COLUMNS -----------------
//
// A B C D E F G H I
//
// | A _ 8 _ _ _ 6 2 _ 3
// | B 4 _ _ _ 5 _ _ _ 6
// | C _ 1 _ 7 3 _ _ _ _
// |
// | D 3 _ _ 8 _ _ _ _ _
// ROWS E _ 5 2 _ _ _ 8 4 _
// | F _ _ _ _ _ 4 _ _ 5
// |
// | G _ _ _ _ 7 1 _ 3 _
// | H 5 _ _ _ 4 _ _ _ 2
// | I 9 _ 4 5 _ _ _ 7 _
//
$b->set( 'A', 'B', 8 ); // i.e. row A, column B is 8
$b->set( 'A', 'F', 6 ); // etc...
$b->set( 'A', 'G', 2 );
$b->set( 'A', 'I', 3 );
$b->set( 'B', 'A', 4 );
$b->set( 'B', 'E', 5 );
$b->set( 'B', 'I', 6 );
$b->set( 'C', 'B', 1 );
$b->set( 'C', 'D', 7 );
$b->set( 'C', 'E', 3 );
$b->set( 'D', 'A', 3 );
$b->set( 'D', 'D', 8 );
$b->set( 'E', 'B', 5 );
$b->set( 'E', 'C', 2 );
$b->set( 'E', 'G', 8 );
$b->set( 'E', 'H', 4 );
$b->set( 'F', 'F', 4 );
$b->set( 'F', 'I', 5 );
$b->set( 'G', 'E', 7 );
$b->set( 'G', 'F', 1 );
$b->set( 'G', 'H', 3 );
$b->set( 'H', 'A', 5 );
$b->set( 'H', 'E', 4 );
$b->set( 'H', 'I', 2 );
$b->set( 'I', 'A', 9 );
$b->set( 'I', 'C', 4 );
$b->set( 'I', 'D', 5 );
$b->set( 'I', 'H', 7 );
// display table in handy ASCII format.
$b->dump_asciidoku();
// alternatively use the "quick" entry format which requires a string
// with each position a number from 0-9, e.g. row A, col A is position 0, and
// row I, col I is position 80.
// the the board_id representation of the above entered cells.
$id = $b->make_board_id( );
// will look something like;
//$id = '080006203400050006010730000300800000052000840000004005000071030500040002904500070';
echo $id."\n";
// reload data to show that the alternate format gives the same results
//unset( $b );
//$b = new Sudoku();
//$b->load_board_id( $id );
//$b->dump_asciidoku();
// show ascii sodoku table
//$b->dump_asciidoku();
//$b->dump_status();
// solve to completion
$retval = $b->solve_to_completion();
// there are four return values possible
// True => the board has been solved
// -1 => Error: impossible to save
// -2 => Error: taking to long to solve
// -3 => Error: invalid input ( i.e. conflicting cells )
if( $retval === true )
{
echo "Solved!\n";
// show ascii sodoku table
$b->dump_asciidoku();
}
else if ( $retval === -1 )
{
echo "Impossible to solve\n";
// show ascii sodoku table
$b->dump_asciidoku();
}
else if ( $retval === -2 )
{
echo "Taking too long, I give up\n";
// show ascii sodoku table
$b->dump_asciidoku();
}
*/
?>