3v4l.org

run code in 200+ php & hhvm versions
Bugs & Features
<?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();
based on mb11i
Output for 7.3.5
435617892162589437789203001000300054043002010250140603310020000000000020020000000
Output for 7.3.4
157389426362574189849126573574263810003010200210000000400002001000405307000001602
Output for 7.3.3
453678921672391485819245367341567892726483100500120043000030050030010200204000010
Output for 7.3.2
467183590120040030000000102010625403245000000030000200000004050050010020000002010
Output for 7.3.1
753168942246739815891245360004023001030050000000400003010000027000010004020300106
Output for 7.3.0
215647839768132400400005026000200051000053204020014003600020005300000012100000340
Output for 7.2.18
264357189785416230010002400130004002050020000000035000000200001521003000040501023
Output for 7.2.17
657348192843512760000000500000034200000000000020005301000001000200003415531420670
Output for 7.2.16
685724913147638502200510040014000000002000000030200001461302005503000000020000004
Output for 7.2.15
534671829276348510000200004100000002350000100462035700005403060010000200600512003
Output for 7.2.14
617253489325768100000400002103004000204300001000000020002135040000640200040002003
Output for 7.2.13
637452819812679340500301002004003005025006001300120000401500200203000100000004003
Output for 7.2.12
678413295423578610510002400000007000002106000301000000000205100200001354135064002
Output for 7.2.11
346721859789654310251300040013500002000000000500000130000200000405130200000405000
Output for 7.2.10
742356819813729645569148723475260301000000500301000002250003100004501000130002400
Output for 7.2.9
234576819516248370000001002100000000302004100005602030000000050003165247000000601
Output for 7.2.8
612754839453216700000030012000100300100000205200003040300060124001020000000040503
Output for 7.2.7
438256791159748326027310004200001000000000100016432000341065200005020010602000000
Output for 7.2.6
356748912124693758879521346513267489247385601000000205000002103732154060001000024
Output for 7.2.5
452671839678532001301400002010023040200154300000000100020005403103040000000010020
Output for 7.2.4
238745916154382700000061030000020100000000403000003020021030004400200300003100200
Output for 7.2.3
257136890000042005013000400346025107500000002872061000004210000000000001100000203
Output for 7.2.2
653714829728356140041002003160000002300201004002003010030000201410020000200030000
Output for 7.2.1
451627893273458106000100420010300004300240501002000600100060305530010042000000000
Output for 7.2.0
352147869467328150000650020005010604200000305000080012000060000140030000023070001
Output for 7.1.28
275461890460502130003000000040000300321004000000130204002040013100000000004305020
Output for 7.1.27
125376480004500720000024100030000650002150849001000370000060210203401000000030000
Output for 7.1.26
357624891126357000000000423035412760000000000614000200041000000500203010200001300
Output for 7.1.25
645723891178546230230100400300201000000400123400635007000000000003002010500300002