Sudoku Generator Source PHP Code
<?php
// Sudoku Generator Class by Glenn J. Schworak
//
// This software is shared under GPLv3 license.
// Please credit me if you use it in your product
// or as a model for a derivative work.
//
// This class is used to generate a Sudoku game
// board that includes a puzzle, solution and
// some other key values.
//
// This can be included from another PHP file
// to make a game or access the game data as
// and array, or in a stand alone mode to
// output JSON data.
//
// To use this as a class, you can create the object
// with or without parameters (with is recommended)
// where $board is any integer 0 or higher (zero = random)
// and $level is 0-4 to indicate the numerical level
//
// $sudoku = new Sudoku($board, $level);
//
//
// To generate a new game without creating a new instance
// of the Sudoku object, call the initialize function
//
// $sudoku->initialize($board, $level);
//
//
// Access the entire game object as an array
//
// $game = $sudoku->game();
//
//
// You can also access any of the exposed elements individually
//
// $variable = $sudoku->{element_name};
//
// status always "ok" unless there was an error
// board the board number used to generate the solution
// level the level number used to generate the puzzle
// levels an array of level names
// jitter data about how the solution was generated
// timing how lont it took to generate the solution in seconds
// puzzle the puzzle array
// solution the solution array
//
//
class Sudoku
{
private $levels = ["Easy", "Medium", "Hard", "Expert", "Evil"];
private $levelStart = [35, 40, 45, 50, 55];
private $emptyGrid = [
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
];
private $level = 0;
private $board = 0;
private $jitter = 0;
private $redo = 0;
private $status = '';
private $timing = 0;
private $solution = [];
private $puzzle = [];
private $solutionSteps = [];
private $rand = 0;
private $randCount = 0;
private $usedPattern = false;
// call the initialization when constructed
public function __construct($board = 0, $level = 1)
{
$this->initialize($board, $level);
}
// return the individual game elements
public function __get($key)
{
switch ($key)
{
case 'status':
return $this->status;
break;
case 'board':
return $this->board;
break;
case 'level':
return $this->level;
break;
case 'levels':
return $this->levels;
break;
case 'levelStart':
return $this->levelStart;
break;
case 'jitter':
return $this->jitter;
break;
case 'redo':
return $this->redo;
break;
case 'timing':
return $this->timing;
break;
case 'puzzle':
return $this->puzzle;
break;
case 'solution':
return $this->solution;
break;
case 'solutionSteps':
return $this->solutionSteps;
break;
case 'randCount':
return $this->randCount;
break;
case "usedPattern":
return $this->usedPattern;
default:
throw new ErrorException("Unknown parameter");
}
}
// alias for the game function
public function __serialize()
{
return $this->game();
}
// initialize the class
public function initialize($board = 0, $level = 1)
{
$start = hrtime(true);
$this->level = max(0, min(count($this->levels), intval($level)));
$this->board = max(0, intval($board));
$this->board = ($board == 0 ? rand(10000000, 99999999) : $board); // pick a fully random board if zero
$this->randSeed($this->board);
$this->jitter = 0;
$this->redo = 0;
$this->solution = $this->emptyGrid;
$this->puzzle = $this->emptyGrid;
$this->fillSolution();
$this->makePuzzle();
$this->status = ($this->jitter >= 0 ? 'ok' : 'too complex');
$this->timing = (hrtime(true) - $start) / 1e+9; // nanoseconds to seconds
}
// return the entire game object
public function game()
{
return [
'status' => $this->status,
'board' => $this->board,
'level' => $this->level,
'levels' => $this->levels,
'levelStart' => $this->levelStart,
'jitter' => $this->jitter,
'redo' => $this->redo,
'timing' => $this->timing,
'puzzle' => $this->puzzle,
'solution' => $this->solution,
'solutionSteps' => $this->solutionSteps,
];
}
// initialize the grid and fill the cells
// to create a solution
private function fillSolution()
{
$start = time();
$steps = 0;
$goBack = 0;
$this->jitter = 0;
// move through each cell from 0 to 80
// filling them as we go and backing up
// when we get stuck
for ($x = 0; $x < 81; ++$x)
{
if (time() - $start > 5)
{
// took more than 5 seconds so exit
// with a negative jitter to indicate
// the error.
return 0 - (1 + $this->jitter);
}
$row = floor($x / 9);
$col = $x % 9;
$safe = $this->safeDigit($this->solution, $row, $col);
if ($safe > 0)
{
// we have a safe digit so write it to the
// grid and reduce the amount we go back
// the next time we get stuck
++$steps;
$this->solution[$row][$col] = $safe;
$goBack = max(0, $goBack - 1);
}
else
{
// hit a bad cell so we need to go back
// several cells setting them to ZERO
// so we can try them again
++$this->jitter;
$goBack += 3;
$y = max(0, $x - $this->randRange(1, $goBack));
for ($i = $y; $i <= $x; ++$i)
{
$row = intval($i / 9);
$col = $i % 9;
$this->solution[$row][$col] = 0;
}
$x = $y - 1;
}
}
$this->jitter = floatval($this->jitter . "." . $steps);
}
private function removeOne($mirror, &$removedDigits, $r, $c, $rotation = 0)
{
switch ($rotation)
{
case 1:
$row = $c;
$col = 8 - $r;
break;
case 2:
$row = 8 - $r;
$col = 8 - $c;
break;
case 3:
$row = 8 - $c;
$col = $r;
break;
default:
$row = $r;
$col = $c;
}
$removed = 1;
$removedDigits[] = $this->puzzle[$row][$col];
$this->puzzle[$row][$col] = 0;
if ($mirror && $this->puzzle[8 - $row][8 - $col] > 0)
{
++$removed;
$removedDigits[] = $this->puzzle[8 - $row][8 - $col];
$this->puzzle[8 - $row][8 - $col] = 0;
}
return $removed;
}
// remove cells to make the solution
// into a puzzle based on the level
private function makePuzzle()
{
$start = time();
$removedDigits = [0];
$remove = $this->levelStart[$this->level];
$mirror = ($this->randRange(0, 8 - $this->level) == 2);
$rotation = $this->randRange(0, 3);
$this->usedPattern = false;
if ($this->jitter < 0)
{
return; // the solution couldn't be created so exit now
}
$this->puzzle = $this->solution;
$r = $this->randRange(0, [7, 5, 2][$this->level]);
if ($r == 0)
{
// some special layouts exist
$g = $this->emptyGrid;
switch ($this->level)
{
case 0:
$this->usedPattern = 1 + $this->randRange(0, 1);
switch ($this->usedPattern)
{
case 1:
for ($i = 0; $i < 3; ++$i)
{
for ($j = 0; $j < 3; ++$j)
{
$xo = $this->randRange(0, 1);
$yo = $this->randRange(0, 1);
for ($x = 0; $x < 2; ++$x)
{
for ($y = 0; $y < 2; ++$y)
{
$r = $i * 3 + $y + $yo;
$c = $j * 3 + $x + $xo;
if (count($removedDigits) <= $this->levelStart[$this->level])
{
$g[$r][$c] = 1;
}
}
}
}
}
break;
case 2:
for ($i = 0; $i < 3; ++$i)
{
for ($j = 0; $j < 3; ++$j)
{
$r = $i * 3;
$c = $j * 3;
$g[$r][$c] = 1;
$g[$r + 1][$c] = 1;
$g[$r][$c + 1] = 1;
if (count($removedDigits) <= $this->levelStart[$this->level])
{
$g[$r + 2][$c + 2] = 1;
}
}
}
break;
}
for ($r = 0; $r < 9; ++$r)
{
for ($c = 0; $c < 9; ++$c)
{
if ($g[$r][$c] == 1)
{
$this->removeOne(false, $removedDigits, $r, $c, $rotation);
}
}
}
break;
case 1:
$this->usedPattern = 1 + $this->randRange(0, 1);
switch ($this->usedPattern)
{
case 1:
$odd = ($this->randRange(0, 1) == 1);
for ($i = 0; $i < 3; ++$i)
{
for ($j = 0; $j < 3; ++$j)
{
$odd = !$odd;
for ($x = 0; $x < 3; ++$x)
{
for ($y = 0; $y < 3; ++$y)
{
$r = $i * 3 + $y;
$c = $j * 3 + $x;
if ((($x + $y) / 2 == intval(($x + $y) / 2) ? 0 : 1) == $odd)
{
$g[$r][$c] = 1;
}
}
}
}
}
break;
case 2:
$odd = false;
$offset = $this->randRange(0, 4);
for ($i = 0; $i < 9; ++$i)
{
for ($j = 0; $j < ($odd ? 5 : 4); ++$j)
{
$r = $i;
$c = ($odd ? 8 - $j : $j);
$g[$r][($offset + $c) % 9] = 1;
}
$odd = !$odd;
}
break;
}
for ($r = 0; $r < 9; ++$r)
{
for ($c = 0; $c < 9; ++$c)
{
if ($g[$r][$c] == 1)
{
$this->removeOne(false, $removedDigits, $r, $c, $rotation);
}
}
}
break;
case 2:
$t = 0;
$s = 0;
$p = $this->randRange(0, 9);
while ($s == 0 && $t < 3)
{
++$t;
++$p;
$this->puzzle = $this->solution;
$this->usedPattern = 1 + ($p % 3);
switch ($this->usedPattern)
{
case 1:
$x = $this->randRange(8, 15);
for ($r = 0; $r < 9; ++$r)
{
for ($c = 8 - $r; $c < 9; ++$c)
{
if ($r + $c > $x)
{
$g[$r][$c] = 1;
}
else
{
$g[8 - $r][8 - $c] = 1;
}
}
}
break;
case 2:
for ($r = 0; $r < 9; ++$r)
{
$g[$r][0] = 1;
$g[$r][8] = 1;
if ($r > 1 && $r < 7)
{
$g[$r][2] = 1;
$g[$r][6] = 1;
}
if ($r > 2 && $r < 6)
{
$g[$r][4] = 1;
}
}
for ($c = 1; $c < 8; ++$c)
{
$g[0][$c] = 1;
$g[8][$c] = 1;
}
break;
case 3:
$g = [
[0, 0, 1, 1, 1, 1, 1, 0, 0],
[0, 1, 1, 1, 0, 1, 1, 1, 0],
[1, 1, 1, 0, 0, 0, 1, 1, 1],
[1, 1, 0, 0, 0, 0, 0, 1, 1],
[1, 0, 0, 0, 1, 0, 0, 0, 1],
[1, 1, 0, 0, 0, 0, 0, 1, 1],
[1, 1, 1, 0, 0, 0, 1, 1, 1],
[0, 1, 1, 1, 0, 1, 1, 1, 0],
[0, 0, 1, 1, 1, 1, 1, 0, 0],
];
break;
}
for ($r = 0; $r < 9; ++$r)
{
for ($c = 0; $c < 9; ++$c)
{
if ($g[$r][$c] == 1)
{
$this->removeOne(false, $removedDigits, $r, $c, $rotation);
}
}
}
$s = count($this->getSolution($this->puzzle));
}
break;
}
$remove = $this->levelStart[$this->level] + 1 - count($removedDigits);
while ($remove > 0)
{
// remove random blocks as needed
$r = $this->randRange(0, 8);
$c = $this->randRange(0, 8);
$dig = $this->puzzle[$r][$c];
if ($dig > 0)
{
$remove -= $this->removeOne(false, $removedDigits, $r, $c, 0);
}
}
if (count($this->getSolution($this->puzzle)) > 0)
{
// can be solved so we are done
return;
}
}
// can't be solved without guessing so reset
$this->usedPattern = false;
$this->puzzle = $this->solution;
$removedDigits = [0];
$remove = $this->levelStart[$this->level];
// make sure one entire nonet (3x3 box) is empty
if ($this->level > 2 && $this->randRange(0, 6) == 3)
{
$r = $this->randRange(0, 2);
$c = $this->randRange(0, 2);
for ($i = 0; $i < 3; ++$i)
{
for ($j = 0; $j < 3; ++$j)
{
$row = 3 * $r + $j;
$col = 3 * $c + $i;
$remove -= $this->removeOne($mirror, $removedDigits, $row, $col);
}
}
}
// make sure one item is missing from each row
for ($row = 0; $row < 9 && $this->level < 3; ++$row)
{
$col = $this->randRange(0, 8);
$remove -= $this->removeOne($mirror, $removedDigits, $row, $col);
}
// make sure one item is missing from each column
for ($col = 0; $col < 9 && $this->level < 3; ++$col)
{
$full = true;
for ($row = 0; $row < 9 && $full; ++$row)
{
if ($this->puzzle[$row][$col] == 0)
{
$full = false;
}
}
if ($full)
{
$row = $this->randRange(0, 8);
$remove -= $this->removeOne($mirror, $removedDigits, $row, $col);
}
}
// make sure one item is missing from each nonet (box of 3x3)
for ($r = 0; $r < 3 && $this->level < 3; ++$r)
{
for ($c = 0; $c < 3; ++$c)
{
$full = true;
for ($i = 0; $i < 3 && $full; ++$i)
{
for ($j = 0; $j < 3 && $full; ++$j)
{
$row = 3 * $r + $i;
$col = 3 * $c + $j;
if ($this->puzzle[$row][$col] == 0)
{
$full = false;
}
}
}
if ($full)
{
$row = 3 * $r + $this->randRange(0, 2);
$col = 3 * $c + $this->randRange(0, 2);
$remove -= $this->removeOne($mirror, $removedDigits, $row, $col);
}
}
}
// make sure one of each digit are missing
$removedDigits = array_unique($removedDigits);
while (count($removedDigits) < 10)
{
$row = $this->randRange(0, 8);
$col = $this->randRange(0, 8);
if (!in_array($this->puzzle[$row][$col], $removedDigits))
{
$remove -= $this->removeOne($mirror, $removedDigits, $row, $col);
}
}
// remove the rest randomly
$fail = 0;
while ($remove > 0)
{
if (time() - $start > 5)
{
// took more than 5 seconds so exit
// with a negative jitter to indicate
// the error.
return 0 - (1 + $this->jitter);
}
$row = $this->randRange(0, 8);
$col = $this->randRange(0, 8);
$dig = $this->puzzle[$row][$col];
if ($dig > 0)
{
$this->puzzle[$row][$col] = 0;
$possible = $this->safeDigit($this->puzzle, $row, $col, true);
if (count($possible) == 1)
{
// this cell can be removed
--$remove;
$fail = 0;
}
elseif (!$this->canBeElsewhere($this->puzzle, $row, $col, $dig))
{
// this cell can be removed
--$remove;
$fail = 0;
}
elseif (count($this->getSolution($this->puzzle)) > 0)
{
// this cell can be removed
--$remove;
$fail = 0;
}
else
{
// this cell cannot be removed
++$fail;
$oldRow = $row;
$oldCol = $col;
$this->puzzle[$row][$col] = $dig;
if ($fail > 5)
{
$found = false;
for ($row = 0; !$found && $row < 9; ++$row)
{
for ($col = 0; !$found && $col < 9; ++$col)
{
if ($this->puzzle[$row][$col] > 0)
{
$dig = $this->puzzle[$row][$col];
$this->puzzle[$row][$col] = 0;
if (count($this->getSolution($this->puzzle)) > 0)
{
// this cell can be removed
--$remove;
$fail = 0;
$found = true;
}
else
{
// put it back
$this->puzzle[$row][$col] = $dig;
}
}
}
}
if (!$found && $this->level >= 3)
{
// clear the cell anyway on high levels
$this->puzzle[$oldRow][$oldCol] = 0;
--$remove;
$fail = 0;
}
}
}
}
}
}
// return a safe digit for the specified cell
// and -1 if no safe digits exist
public function safeDigit(&$grid, $row, $col, $returnAll = false)
{
$digits = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
$used = [];
$usedPos = [];
// copy the row
for ($c = 0; $c < 9; ++$c)
{
$used[] = $grid[$row][$c];
$usedPos[] = ["row" => $row, "col" => $c, "dig" => $grid[$row][$c]];
}
$used = $grid[$row];
// copy the column
for ($r = 0; $r < 9; ++$r)
{
$used[] = $grid[$r][$col];
$usedPos[] = ["row" => $r, "col" => $col, "dig" => $grid[$r][$col]];
}
// copy the nonet
$r = intval($row / 3) * 3;
$c = intval($col / 3) * 3;
for ($i = 0; $i < 3; ++$i)
{
for ($j = 0; $j < 3; ++$j)
{
$used[] = $grid[$r + $i][$c + $j];
$usedPos[] = ["row" => $r, "col" => $c, "dig" => $grid[$r][$c]];
}
}
// zero any digits that have been used
foreach ($used as $u)
{
$digits[$u] = 0;
}
// copy the non-zero digits to a safe list
$safe = [];
for ($c = 0; $c < count($digits); ++$c)
{
if ($digits[$c] > 0)
{
$safe[] = $digits[$c];
}
}
// if returning all, just return the array
if ($returnAll)
{
return $safe;
}
// shuffle and return the first safe digit (if any)
$this->arrayShuffle($safe);
return count($safe) > 0 ? $safe[0] : -1;
}
public function randSeed($seed)
{
$this->rand = $seed % 23752890;
$this->randCount = 0;
}
public function randRange($low, $high)
{
if ($low > $high)
{
$t = $low;
$low = $high;
$high = $t;
}
++$this->randCount;
$rnd = $this->rand / 23752890;
$r = $low + floor(($high - $low + 1) * $rnd);
$this->rand = ($this->rand * 938301 + 493297) % 23752890; // set the next random ticker
return $r;
}
private function arrayShuffle(&$array)
{
$arrayMax = count($array) - 1;
// While there remain elements to shuffle.
for ($currentIndex = 0; $currentIndex <= $arrayMax; ++$currentIndex)
{
// Pick a remaining element.
$randomIndex = $this->randRange(0, $arrayMax);
[$array[$currentIndex], $array[$randomIndex]] = [$array[$randomIndex], $array[$currentIndex]];
}
}
public function getSolution($grid, $ret = "solution", $depth = 0, $bruitForce = false)
{
// solve the puzzle and return an array of solution steps
$solution = [];
$filled = 1;
$openCell = $this->getOpenCells($grid);
// fill all the easy ones first
while ($filled > 0)
{
$filled = 0;
for ($i = 0; $i < count($openCell); ++$i)
{
$row = $openCell[$i][0];
$col = $openCell[$i][1];
for ($p = 0; $p < count($openCell[$i][2]); ++$p)
{
$dig = $openCell[$i][2][$p];
if (count($openCell[$i][2]) == 1 || !$this->canBeElsewhere($grid, $row, $col, $dig))
{
++$filled;
$grid[$row][$col] = $dig;
$solution[] = ['row' => $row, 'col' => $col, 'digit' => $dig];
break;
}
}
}
$openCell = $this->getOpenCells($grid);
}
for ($i = 0; $filled == 0 && $bruitForce && $depth < 3 && $i < count($openCell); ++$i)
{
// we still have open cells so now we need to
// try each option in every cell to see if
// one will complete the puzzle but we stop
// on the first one we fill to reduce the cost
$row = $openCell[$i][0];
$col = $openCell[$i][1];
for ($p = 0; $p < count($openCell[$i][2]); ++$p)
{
$dig = $openCell[$i][2][$p];
$grid[$row][$col] = $dig;
$newSolution = $this->getSolution($grid, "solution", $depth + 1);
if (count($newSolution) > 0)
{
++$filled;
$solution = $newSolution;
$openCell = [];
break;
}
$grid[$row][$col] = 0;
}
}
switch ($ret)
{
case "grid":
return $grid;
case "open":
return $openCell;
default:
return count($openCell) > 0 ? [] : $solution;
}
}
private function canBeElsewhere(&$grid, $row, $col, $dig)
{
// can the specified digit be used in any other location
// besides the specified row/column
// check the row
for ($c = 0; $c < 9; ++$c)
{
if ($c != $col)
{
if ($grid[$row][$c] == $dig)
{
return true;
}
elseif ($grid[$row][$c] == 0 && in_array($dig, $this->safeDigit($grid, $row, $c, true)))
{
return true;
}
}
}
// check the column
for ($r = 0; $r < 9; ++$r)
{
if ($r != $row)
{
if ($grid[$r][$col] == $dig)
{
return true;
}
elseif ($grid[$r][$col] == 0 && in_array($dig, $this->safeDigit($grid, $r, $col, true)))
{
return true;
}
}
}
// check the nonet
$x = floor($row / 3) * 3;
$y = floor($col / 3) * 3;
for ($i = 0; $i < 3; ++$i)
{
for ($j = 0; $j < 3; ++$j)
{
$r = $x + $i;
$c = $y + $j;
if ($r != $row || $c != $col)
{
if ($grid[$r][$c] == $dig)
{
return true;
}
elseif ($grid[$r][$c] == 0 && in_array($dig, $this->safeDigit($grid, $r, $c, true)))
{
return true;
}
}
}
}
return false;
}
public function getOpenCells(&$grid)
{
// find all the possible digits that can go into each
// of the open cells (if any)
$openCell = [];
for ($r = 0; $r < 9; ++$r)
{
for ($c = 0; $c < 9; ++$c)
{
if ($grid[$r][$c] == 0)
{
$openCell[] = [$r, $c, $this->safeDigit($grid, $r, $c, true)];
}
}
}
// sort the list based on the number of possibilities
$last = count($openCell) - 1;
$sorted = false;
while (!$sorted)
{
$sorted = true;
for ($i = 0; $i < $last; ++$i)
{
$j = $i + 1;
if (count($openCell[$i][2]) > count($openCell[$j][2]))
{
$sorted = false;
[$openCell[$i], $openCell[$j]] = [$openCell[$j], $openCell[$i]];
}
}
--$last; // we know the last one is sorted
}
return $openCell;
}
public function countBlank(&$grid)
{
// count the number of blank cells (zero) in the grid
$blank = 0;
for ($a = 0; $a < 9; ++$a)
{
for ($b = 0; $b < 9; ++$b)
{
if ($grid[$a][$b] == 0)
{
++$blank;
}
}
}
return $blank;
}
private function dumpGrid(&$grid, $row = 9, $col = 9)
{
$out = "";
for ($r = 0; $r < 9; ++$r)
{
$out .= ($r == 3 || $r == 6 ? '-------+-------+-------<br>' : '') . ' ';
for ($c = 0; $c < 9; ++$c)
{
$color = "";
if (floor($r / 3) == floor($row / 3) && floor($c / 3) == floor($col / 3))
{
$color = "background:yellow; color:black";
}
if ($r == $row || $c == $col)
{
$color = "background:yellow; color:black";
}
if ($r == $row && $c == $col)
{
$color = "background:blue; color:white";
}
$out .= ($c == 3 || $c == 6 ? '| ' : '') . "<span style='" . $color . "'>" . ($grid[$r][$c] == 0 ? '-' : $grid[$r][$c]) . '</span> ';
}
$out .= "<br>";
}
return "<pre>" . $out . "</pre>";
}
}
// if this file is called directly, dump the game array
// as a JSON string for use by other applications, otherwise
// the page that is including this file will need to generate
// a game by calling the sudoku function
if (basename(__FILE__) == basename($_SERVER["SCRIPT_NAME"]))
{
if (ob_get_level())
{
ob_clean();
}
if (!headers_sent())
{
header("Content-Type: application/json");
}
$sudoku = new Sudoku($board ?? ($_REQUEST["board"] ?? 0), $level ?? ($_REQUEST["level"] ?? 1));
echo json_encode($sudoku->game(), JSON_PRETTY_PRINT);
exit;
}
