@ 2019-05-15T23:03:07Z <?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();
Enable javascript to submit You have javascript disabled. You will not be able to edit any code.
Here you find the average performance (time & memory) of each version. A grayed out version indicates it didn't complete successfully (based on exit-code).
Version System time (s) User time (s) Memory (MiB) 7.4.1 0.007 0.011 14.88 7.4.0 0.007 0.010 15.31 7.3.13 0.014 0.007 14.76 7.3.12 0.007 0.007 14.63 7.3.11 0.011 0.007 14.77 7.3.10 0.009 0.006 15.10 7.3.9 0.004 0.011 14.98 7.3.8 0.006 0.009 15.13 7.3.7 0.008 0.011 14.90 7.3.6 0.007 0.003 15.02 7.3.5 0.009 0.005 14.90 7.3.4 0.006 0.012 14.82 7.3.3 0.005 0.015 14.89 7.3.2 0.010 0.008 15.72 7.3.1 0.014 0.006 15.76 7.3.0 0.013 0.005 15.65 7.2.26 0.014 0.007 14.79 7.2.25 0.010 0.005 15.16 7.2.24 0.013 0.006 15.02 7.2.23 0.007 0.010 15.22 7.2.22 0.011 0.007 15.33 7.2.21 0.010 0.010 15.42 7.2.20 0.007 0.010 14.95 7.2.19 0.007 0.007 14.97 7.2.18 0.008 0.008 15.11 7.2.17 0.003 0.013 15.18 7.2.16 0.012 0.003 15.29 7.2.15 0.012 0.009 16.00 7.2.14 0.009 0.010 16.12 7.2.13 0.008 0.012 15.93 7.2.12 0.011 0.008 16.14 7.2.11 0.003 0.017 16.23 7.2.10 0.013 0.007 15.95 7.2.9 0.013 0.005 16.01 7.2.8 0.008 0.010 15.95 7.2.7 0.008 0.008 15.89 7.2.6 0.016 0.007 15.88 7.2.5 0.013 0.007 15.93 7.2.4 0.012 0.011 16.08 7.2.3 0.007 0.009 15.99 7.2.2 0.013 0.006 16.04 7.2.1 0.013 0.015 16.17 7.2.0 0.016 0.003 16.00 7.1.33 0.004 0.011 15.93 7.1.32 0.000 0.011 15.72 7.1.31 0.004 0.014 15.59 7.1.30 0.000 0.015 15.62 7.1.29 0.010 0.009 15.32 7.1.28 0.008 0.012 14.79 7.1.27 0.010 0.007 14.91 7.1.26 0.009 0.011 15.01 7.1.25 0.011 0.011 14.73 7.1.24 0.004 0.011 15.69 7.1.23 0.006 0.009 15.65 7.1.22 0.007 0.010 15.57 7.1.21 0.003 0.014 15.42 7.1.20 0.000 0.014 15.71 7.1.19 0.009 0.006 15.67 7.1.18 0.000 0.012 15.75 7.1.17 0.006 0.013 15.68 7.1.16 0.004 0.011 15.33 7.1.15 0.006 0.009 15.71 7.1.14 0.000 0.012 15.56 7.1.13 0.009 0.006 15.88 7.1.12 0.010 0.003 15.24 7.1.11 0.007 0.007 15.43 7.1.10 0.014 0.004 15.78 7.1.9 0.003 0.012 15.83 7.1.8 0.009 0.003 15.71 7.1.7 0.007 0.010 15.34 7.1.6 0.007 0.007 15.73 7.1.5 0.000 0.013 15.71 7.1.4 0.004 0.011 15.59 7.1.3 0.003 0.013 15.94 7.1.2 0.003 0.007 15.59 7.1.1 0.011 0.007 15.56 7.1.0 0.006 0.009 15.61
preferences:dark mode live preview
35.37 ms | 400 KiB | 5 Q