<?php
class SudokuGenerator extends SudokuSolver
{
public $EleArray = NULL;
const METRIC_EASY = 27;
const METRIC_MEDIUM = 22;
const METRIC_HARD = 17;
public function __construct()
{
$this->EleArray();
parent::__construct();
}
/*
Creates an array of possible (row, col) combinations. So that uniquely a random elemnt can be selected
*/
public function EleArray()
{
$EleArray = array();
foreach(range(0, 8) as $i )
foreach(range(0, 8) as $j )
$EleArray[] = array($i, $j);
$this->EleArray = $EleArray;
}
public function FillRandomValue()
{
if( $this->EleArray === NULL )
throw new Exception('$this->EleArray() must be called before FillRandomValue', 1);
$ele = array_rand( $this->EleArray );
$randCol = $this->EleArray[$ele][0];
$randRow = $this->EleArray[$ele][1];
unset($this->EleArray[$ele]);
for ( $i = 1; $i <= 9; $i++ )
{
if( $this->checkValid($randRow, $randCol, $i) )
{
$this->_oSudoku[$randRow][$randCol] = $i;
break;
}
}
}
public function GenerateSudoku( $difficulty )
{
$this->EleArray();
for( $i = 0; $i < $difficulty; $i++ )
$this->FillRandomValue();
do {
$this->FillRandomValue();
$this->Solve();
} while( $this->HasUnique() === self::NOT_UNIQUE );
}
}
class SudokuSolver {
protected $_iSudoku = array();
protected $_oSudoku = array();
protected $_stack;
protected $_blocks;
protected $_oSudoku90;
protected $_compare;
const NOT_SOLVABLE = 10;
const NOT_UNIQUE = 11;
public function __construct( $sudoku = NULL, $stack = NULL, $seedVal = 0 ) {
$this->seedVal = $seedVal;
if ( $stack === NULL )
$this->_stack = new Stack();
else
$this->_stack = $stack;
if ( $sudoku === NULL )
$sudoku = str_repeat( "0", 81 );
/** Creates an sudoku array from the supplied string or empty string */
if ( is_string( $sudoku ) ):
$sudoku = str_split( $sudoku, 9 );
array_walk( $sudoku, function( &$arg ) {
$arg = str_split( $arg );
} );
endif;
$this->_iSudoku = $this->_oSudoku = $sudoku;
$this->_compare = range(1, 9);
$this->_constuctBlock();
}
// Constructs block of 3 x 3 array, and row wise block that can later be used for direct
// finding of possibles instead of looping
protected function _constuctBlock() {
for ( $x = 0; $x < 9; $x++ ) {
$this->_oSudoku90[$x] = array();
for ( $y = 0; $y < 9; $y++ ) {
$this->_oSudoku90[$x][$y] = &$this->_oSudoku[$y][$x];
}
}
// create '_blocks'
for ( $blockX = 0; $blockX < 3; $blockX++ ) {
$this->_blocks[$blockX] = array();
for ( $blockY = 0; $blockY < 3; $blockY++ ) {
$this->_blocks[$blockX][$blockY] = array();
$gridX = $blockX * 3;
for ( $cellX = 0; $cellX < 3; $cellX++ ) {
$gridY = $blockY * 3;
for ( $cellY = 0; $cellY <3; $cellY++ ) {
$this->_blocks[$blockX][$blockY][] = &$this->_oSudoku[$gridX][$gridY++];
}
$gridX++;
}
}
}
}
/** The following functions find the possibles for column, row and 3 x 3 block */
public function missingColumn($m) {
return array_diff($this->_compare, $this->_oSudoku[$m]);
}
public function missingRow($n) {
return array_diff($this->_compare, $this->_oSudoku90[$n]);
}
public function missingBlock($m,$n) {
return array_diff($this->_compare, $this->_blocks[$m][$n]);
}
/* An intersect of all the possibles finds the possibles obeying rules of sudoku */
public function possibles( $m, $n ) {
return array_intersect(
$this->missingBlock((int)$m / 3, (int)$n / 3),
$this->missingColumn($m),
$this->missingRow($n)
);
}
public function checkValid( $m, $n, $val ) {
return in_array( $val, array_intersect(
$this->missingBlock((int)$m / 3, (int)$n / 3),
$this->missingColumn($m),
$this->missingRow($n)
));
}
/**
* Function checks if the sudoku has a unique solution
*/
public function HasUnique() {
while ( !$this->_stack->isEmpty() ) {
$stack = new Stack();
$oldSudoku = &$this->_oSudoku;
list( $m, $n ) = $this->_stack->pop();
$val = $oldSudoku[$m][$n];
$oldSudoku[$m][$n] = 0;
$sudoku = new SudokuSolver( $oldSudoku, $stack, $val );
if ( $sudoku->Solve() !== self::NOT_SOLVABLE )
return self::NOT_UNIQUE;
}
return TRUE;
}
public function Solve() {
$m = $n = 0;
fx: while ( $m !== 9 ): //Loop till 9 x 9 sudoku processed
if ( ( (int)( $cell = &$this->_oSudoku[$m][$n] ) === 0 ) ) {
foreach ( $this->possibles($m, $n) as $val) {
$this->seedVal = 0;
//If cell's value was less than value of $val means insertion
//must be done otherwise it means it has returned from backtracking
if( $cell < $val )
$cell = $val;
else
continue;
$this->_stack->push( $m, $n ); //Record the insertion
if ( $n === 8 ):
$m += 1;
$n = 0;
else:
$n += 1;
endif;
goto fx; ///if insertion was valid continue while
}
$this->_oSudoku[$m][$n] = 0;
if ( $this->_stack->isEmpty() ) //If backtracked till begining return NOT SOLVABLE
return self::NOT_SOLVABLE;
else
list( $m, $n ) = $this->_stack->pop(); //backtrack
} else {
if ( $n === 8 ):
$m += 1;
$n = 0;
else:
$n += 1;
endif;
}
endwhile;
}
public function OutputArray() {
return $this->_oSudoku;
}
public function OutputString() {
array_walk( $this->_oSudoku, function( &$ele ) { $ele = implode( "", $ele ); } );
return implode( "", $this->_oSudoku );
}
public function __toString() {
return print_r( $this->_oSudoku, true );
}
}
class Stack {
private $stk = array();
public function push($m, $n) {
array_push( $this->stk, array($m, $n) );
}
public function pop() {
return array_pop($this->stk);
}
public function isEmpty()
{
return count($this->stk) === 0;
}
public function stackHeight()
{
return count( $this->stk );
}
public function emptyStack()
{
while( !$this->isEmpty() )
$this->pop();
}
}
$sudoku = new SudokuGenerator();
$sudoku->GenerateSudoku( SudokuGenerator::METRIC_EASY );
$sudoku = new SudokuSolver($sudoku->OutputString());
$sudoku->Solve();
print $sudoku->OutputString();
preferences:
34.1 ms | 402 KiB | 5 Q