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 ); $sudoku2 = new SudokuSolver($sudoku->OutputString()); $sudoku2->Solve(); print $sudoku2->OutputString();
based on 5Z6BL
Output for 7.3.5
675348921428516370003020000000001700201030645034000102000000400016003200002100003
Output for 7.3.4
451672893723851640000000001610030254204510030030000006145200300302000010000000400
Output for 7.3.3
624513789718469235395782461851647392967231548230005006040320010000000000000100000
Output for 7.3.2
173245896654789123829163457561437980400510032300026541015002000200001004030000010
Output for 7.3.1
367124589548673020012000000106007003230001040405032100020005030050000012001000000
Output for 7.3.0
645789132123456789789201006210000003400120005506030014052010000304000021001002000
Output for 7.2.18
567438192314562780020010030000000320130000000000250010600320041070040050001005200
Output for 7.2.17
128645790504002031000013002041530000006024015007000000005060003013000004002100000
Output for 7.2.16
185742639627538140043010000200000310000000000431000200000051020000460000010320000
Output for 7.2.15
431567892652841703000032100103000200000300015000100400000010340310205600500400021
Output for 7.2.14
678329510001400003403105620032516400000000001100000000010000034000034102000200000
Output for 7.2.13
146725893782316450350400001473501002600230000200000000530002014001000300000103205
Output for 7.2.12
581249637362780510400351020000000000010430000000002003200100300003000201100020450
Output for 7.2.11
456781923178253604023400051000000302000100000200304160030000000012030540000012000
Output for 7.2.10
156372890304000200200000140040201035000403000000005000000540601410020300000130020
Output for 7.2.9
425678901300200006000431500002164300030500000100003400000005004540002130000010200
Output for 7.2.8
625874319378162450000000020000000200001000003054723061030050142100000000200010030
Output for 7.2.7
142756890000040031000300200000100000030400120000023450024010003001032504300000010
Output for 7.2.6
476518932812643750053002100040200000000100000260030000000000200030004010120305040
Output for 7.2.5
763485129215769438894123576678540213030600000000012040020301064000200051000000000
Output for 7.2.4
426153789573246100000000020040010032050320014132000500000000051300000000201030040
Output for 7.2.3
647582913123674580500301420051000000000000100400010230010003000000000040230045001
Output for 7.2.2
623471589154628703000030240010043000300205106200000000040050020530002014002010000
Output for 7.2.1
672354189548271630000000000105000000034060520006000040003010000201030050400502310
Output for 7.2.0
342576189567841302010302054000000200000005431000210560430000010200100000100003020
Output for 7.1.28
436712895785693412219845637357961284162574903000020000000100026020000001000000000
Output for 7.1.27
647318529581792463329546178436857900002104030010020000000200315105403200000000040
Output for 7.1.26
251678349467351820300402510100000002000000000002000100016243050030000201524010030
Output for 7.1.25
673215894281467300045000126000004000020000010000001000300100200002003451010002630