<?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 );
print $sudoku->OutputString();
- Output for 7.3.5
- 742135689361782450005400000200003000000000210000001534020010300103200040054000020
- Output for 7.3.4
- 524367891768412300001000420040031002100004000673200154300100200410003000002000000
- Output for 7.3.3
- 752894361863127954419635782945316827637248195281579436174953200520000010300000000
- Output for 7.3.2
- 476315289538627401201400300302001000000032000000540100023000004100054020000203010
- Output for 7.3.1
- 526734189174628300003150062000000210000040030000210050410000003030401020200003041
- Output for 7.3.0
- 457362189268159347913847562172684935546723801030500000000001203000235000001000400
- Output for 7.2.18
- 467518329315247860002030010100000000003120040240050001000000100021300000000001253
- Output for 7.2.17
- 136789000000230100020145006000001000200060000001050243004026531015300402000010000
- Output for 7.2.16
- 672531489348679510051020000206315040000000052000000001024100030010450200000260100
- Output for 7.2.15
- 167428539543769281829513647435271860002030000001000000300100405010300002204000100
- Output for 7.2.14
- 176528493428367501053010200360204010040051300001030020000003000010002000002000030
- Output for 7.2.13
- 631784925527316480004002003000150230000020001000000000000040000015203006200001304
- Output for 7.2.12
- 163578924425369718789124356346715289817692435592843671654231897931456002000000043
- Output for 7.2.11
- 356784291478126530012305000020030010000200350000501040000402000000010023030000004
- Output for 7.2.10
- 523678491167490503400201067030010240200000010601000050010025030000000100350104002
- Output for 7.2.9
- 563742189781359426492618357614275830000400012230100000020503001040001200005006040
- Output for 7.2.8
- 562347189734126500100000002000410230300200004020000000013002000000054021005031400
- Output for 7.2.7
- 678245910023000600145000230360000002001050403002031500000003020034020001050100000
- Output for 7.2.6
- 256849137813756942479213568362974851587132694140005023020000010001020000000301200
- Output for 7.2.5
- 163728945457369128289541673634152789571483000000000230300010000020030510000200304
- Output for 7.2.4
- 368729154257184639419356728571238460020000000040510002130000240004000000002001000
- Output for 7.2.3
- 461782359728635410503140200010000002004021000002073001305210000140060000000050100
- Output for 7.2.2
- 752386910630041000000050000406005000513002604020130000001003400000024100040000020
- Output for 7.2.1
- 467813259523679148189425673632584710001000002000201060000040030215000400304106520
- Output for 7.2.0
- 132467589467895213589201000045672130000000050710003062000000370000134020320050041
- Output for 7.1.28
- 842651397690073001305040602001020000003000010200100430120000003400000000000012004
- Output for 7.1.27
- 523678491416529378789410000304100250002000100100300040240053006035001002001240000
- Output for 7.1.26
- 543178269172946538689352741764523810020001000310000400001000300450037102230400000
- Output for 7.1.25
- 137825964458736001020100530000018000000002003510003420000004310000001000001307200
preferences:
79.54 ms | 401 KiB | 34 Q