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; }
All content on this site is copyright ©2004-2023 and is not to be reproduced without prior permission.