The Schworak Site | Log In | Up One Level

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;

	// 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;
			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);

		if ($this->jitter < 0)
		{
			return; // the solution couldn't be created so exit now
		}
		$this->puzzle = $this->solution;

		if ($this->randRange(0, 7) == 3)
		{
			// some special layouts exist
			switch ($this->level)
			{
				case 0:
					switch ($this->randRange(0, 1))
					{
						case 0:
							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])
											{
												$this->removeOne(false, $removedDigits, $r, $c, $rotation);
											}
										}
									}
								}
							}
							break;
						case 1:
							for ($i = 0; $i < 3; ++$i)
							{
								for ($j = 0; $j < 3; ++$j)
								{
									$r = $i * 3;
									$c = $j * 3;
									$this->removeOne(false, $removedDigits, $r, $c, $rotation);
									$this->removeOne(false, $removedDigits, $r + 1, $c, $rotation);
									$this->removeOne(false, $removedDigits, $r, $c + 1, $rotation);
								}
							}
							break;
					}
					break;
				case 1:
					switch ($this->randRange(0, 0))
					{
						case 0:
							$odd = $this->randRange(0, 1);
							for ($i = 0; $i < 3; ++$i)
							{
								for ($j = 0; $j < 3; ++$j)
								{
									$odd = 1 - $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)
											{
												$this->removeOne(false, $removedDigits, $r, $c, $rotation);
											}
										}
									}
								}
							}
							break;
					}
					break;
				case 2:
					switch ($this->randRange(0, 0))
					{
						case 0:
							$x = $this->randRange(8, 15);
							for ($r = 0; $r < 9; ++$r)
							{
								for ($c = 8 - $r; $c < 9; ++$c)
								{
									if ($r + $c > $x)
									{
										$this->removeOne(false, $removedDigits, $r, $c, $rotation);
									}
									else
									{
										$this->removeOne(false, $removedDigits, $r, $c, ($rotation + 2) % 4);
									}
								}
							}
							break;
					}

					return;
			}

			$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->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-2022 and is not to be reproduced without prior permission.