@ 2019-05-15T23:03:27Z <?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();
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.3.12 0.011 0.007 14.89 7.3.11 0.007 0.010 14.81 7.3.10 0.008 0.003 15.18 7.3.9 0.009 0.009 15.09 7.3.8 0.000 0.018 15.02 7.3.7 0.000 0.016 14.87 7.3.6 0.009 0.006 14.80 7.3.5 0.005 0.014 14.86 7.3.4 0.012 0.006 14.94 7.3.3 0.007 0.010 14.92 7.3.2 0.012 0.007 15.83 7.3.1 0.015 0.005 15.99 7.3.0 0.009 0.014 15.62 7.2.24 0.007 0.013 15.29 7.2.23 0.010 0.003 15.11 7.2.22 0.003 0.007 15.00 7.2.21 0.009 0.006 15.04 7.2.20 0.003 0.015 15.24 7.2.19 0.007 0.010 15.20 7.2.18 0.008 0.006 15.23 7.2.17 0.003 0.014 15.07 7.2.16 0.003 0.013 15.27 7.2.15 0.026 0.009 16.01 7.2.14 0.034 0.013 15.96 7.2.13 0.010 0.008 16.15 7.2.12 0.015 0.008 16.08 7.2.11 0.009 0.013 16.08 7.2.10 0.009 0.010 16.03 7.2.9 0.003 0.014 15.87 7.2.8 0.017 0.005 15.98 7.2.7 0.016 0.005 15.97 7.2.6 0.007 0.011 16.25 7.2.5 0.011 0.007 16.09 7.2.4 0.010 0.014 16.23 7.2.3 0.009 0.010 16.07 7.2.2 0.009 0.009 15.82 7.2.1 0.010 0.009 16.14 7.2.0 0.007 0.010 16.11 7.1.33 0.006 0.010 15.95 7.1.32 0.007 0.007 15.85 7.1.31 0.003 0.013 15.83 7.1.30 0.007 0.003 15.91 7.1.29 0.010 0.003 15.69 7.1.28 0.007 0.012 15.04 7.1.27 0.014 0.007 14.94 7.1.26 0.012 0.009 14.94 7.1.25 0.008 0.008 15.10
preferences:dark mode live preview
38.48 ms | 401 KiB | 5 Q