Creating a Sudoku Generator
Coding this took a little longer than I expected, but it was well worth it. I suggest trying this challenge to anyone who is interested in learning about object oriented programming. This is a very simple version, which I intend to upgrade over time. The code requires PHP 5.0 and is pretty much self explanatory. Leave any questions about it in the comments!
<?php
###########################################################
# Written by Adam Risser 10/10/2006
# email arisser@gmail.com for more information or permission
# to use certain sections of this code (it took me awhile
# to do, so let me know if you want to use it! I will gladly
# let you!)
###########################################################
# The cell Class represents one cell of the sudoku board.
# Each cell starts with $c which contains all the potential
# values that can be placed in the cell. Each cell starts
# out with 1...9 in the beginning
class Cell {
public $c = array(1,2,3,4,5,6,7,8,9);
#______________________________________________________
#Return all potential candidates for a cell
public function getCandidates() {
return $this->c;
}
#______________________________________________________
#Set a Cell to a single number
public function setCandidate($v) {
$this->c = array($v);
}
#______________________________________________________
#Get a random candidate from all potential candidates in cell
public function pickRandomCandidate() {
return $this->c[rand() % count($this->c)];
}
#______________________________________________________
#Delete a candidate from a single cell
public function removeCandidateFromCell($v) {
$this->c = array_values(array_diff($this->c,array($v)));
}
}
###########################################################
# The row class represents one row of the sudoku game. Each
# sudoku game has 9 rows. Each row contains 9 cells. The
# row also stores the initial state of the row. The initial
# state is the state of a row before the program attempts to
# fill values in it. The program keeps track of it in case
# it needs to revert the row to an earlier time.
class Row {
public $cells = array();
public $initialState = array();
#______________________________________________________
public function __construct() {
for ($i=0;$i<9;$i++)
$this->cells[$i] = new Cell();
}
#______________________________________________________
# Return the initial state of the row.
public function getInitialState() {
return $this->initialState;
}
#______________________________________________________
# Return the current state of a row
public function getCurrentState() {
return $this->cells;
}
#______________________________________________________
# Sets the initial State of a row from the current state of
# a row. Must use clone to get a copies of the cells, otherwise
# only a references are copied in initialState.
public function setInitialState() {
$this->initialState = array();
foreach ($this->getCurrentState() as $cell)
$this->initialState[] = clone $cell;
}
#______________________________________________________
# Reset the row to the initial state.
public function resetRow($rowNum = "") {
$this->cells = array();
foreach ($this->getInitialState() as $cell)
$this->cells[] = clone $cell;
}
#______________________________________________________
# Remove a candiate from each cell of a row
public function removeCandidateFromRow($v) {
foreach($this->cells as $c => $val) {
$val->removeCandidateFromCell($v);
}
}
#______________________________________________________
# Print out a row. Used for debugging
public function printRow() {
echo "<strong>Printing Row State</strong>
<table border=1 cellpadding=4><tr>";
foreach($this->cells as $cell) {
echo "<td align='center'>";
for($i=1; $i <= 9; $i++) {
echo (in_array($i, $cell->c)) ? $i : "<span style='color: #ddd'>$i</span>";
echo $i==3 || $i==6 ? "<br />" : "";
}
echo "</td>";
}
echo "</tr></table>";
}
#______________________________________________________
# Print out the initial state. Used for debugging
public function printInitialState($rowNum = "") {
echo "<strong>Initial State of $rowNum</strong>
<table border=1 cellpadding=4><tr>";
foreach($this->initialState as $cell) {
echo "<td align='center'>";
for($i=1; $i <= 9; $i++) {
echo (in_array($i, $cell->c)) ? $i : "<span style='color: #ddd'>$i</span>";
echo $i==3 || $i==6 ? "<br />" : "";
}
echo "</td>";
}
echo "</tr></table>";
}
}
###########################################################
# The Sudoku class is the sudoku game. It contains the
# 9 rows of the game which each contain 9 cells which each
# have 9 potential values.
class Sudoku {
private $rows = array();
#______________________________________________________
# Create the rows
public function __construct() {
for ($i=0;$i< 9;$i++)
$this->rows[$i] = new Row();
}
#______________________________________________________
# Get a single row
public function getRow($rowNum) {
return $this->rows[$rowNum];
}
#______________________________________________________
# Remove a candidate from a single column
public function removeCandidateFromColumn($column, $v) {
foreach($this->rows as $r => $row)
$row->cells[$column]->removeCandidateFromCell($v);
}
#______________________________________________________
# Remove Candidate from a single box. A box is the 3x3 squares
# that are used in the game. There are 9 boxes in a sudoku game
public function removeCandidateFromBox($rowNum, $column, $v) {
#get correct starting row
switch(TRUE) {
case ($rowNum <= 2): $rowNum=0; break;
case ($rowNum <= 5): $rowNum=3; break;
default: $rowNum=6;
}
#get correct starting column
switch(TRUE) {
case ($column <= 2): $column=0; break;
case ($column <= 5): $column=3; break;
default: $column=6;
}
for($i=$rowNum; $i < $rowNum+3; $i++) {
for($ii= $column; $ii < $column + 3; $ii++)
$this->rows[$i]->cells[$ii]->removeCandidateFromCell($v);
}
}
#______________________________________________________
# This function does all of the work. Starts with a cell and then
# moves through the grid until it hits the end of the board.
public function resort($rowNum, $colNum, $count = "")
{
$row = $this->getRow($rowNum);
$cell = $row->cells[$colNum];
#Check to make sure this cell has potenial candidates and is not empty
if(count($this->rows[$rowNum]->cells[$colNum]->getCandidates()) < 1)
{
# Since this cell cannot be filled in. Reset the entire row
# and all of the rows below it.
for($i=$rowNum; $i < 9; $i++)
$this->rows[$i]->resetRow($i);
# This is just a server saver. Just incase something goes on
# infinately. If we havent been going on that long, keep going
# by starting at the beginning of the row again.
if($count >= 2000)
die("Save the server: Hit refresh");
else
$this->resort($rowNum, 0, ++$count);
}
else
{
# The new number for the cell.
$candidate = $this->rows[$rowNum]->cells[$colNum]->pickRandomCandidate();
# Since we have a good candidate, remove it from its row, column,
# and the box it is in
$row ->removeCandidateFromRow($candidate);
$this->removeCandidateFromColumn($colNum, $candidate);
$this->removeCandidateFromBox($rowNum, $colNum, $candidate);
$cell->setCandidate($candidate);
# When we reach the end of the row, go back to the first column
# of the next row.
if ($colNum == 8) {
$colNum = 0;
$rowNum++;
#Update all of the initial states of all rows now completed
for($i=$rowNum; $i < 9; $i++)
$this->rows[$i]->setInitialState();
}else
$colNum++;
if ($rowNum == 9)
return false; #Sudoku is complete.
else
$this->resort($rowNum, $colNum, $count); #start working on next cell
}
}
#______________________________________________________
# Prints out the sudoku game in HTML
public function printout() {
echo "<table border='1' cellpadding='4' cellspacing='0'>";
foreach($this->rows as $k => $row) {
echo "<tr " . ($k==2||$k==5 ? "class='r1'" : "" ) . ">";
foreach($row->cells as $k2 => $cell) {
echo "<td align='center' class='" . ($k2==2||$k2==5 ? "r2"
: "" ) . " c" . $cell->c[0] . "'>";
for($i=1; $i <= 9; $i++) {
#echo (in_array($i, $cell->c)) ? $i : "";
echo (in_array($i, $cell->c)) ? $i : "<span style='color: #ddd'> </span>";
echo $i==3 || $i==6 ? "<br />" : "";
}
echo "</td>";
}
echo "</tr>";
}
echo "</table>";
}
}
?>
<html>
<head>
<style type="text/css">
table { border: 2px solid #000; }
td { width: 50px; }
.r1 td { border-bottom: 2px solid #000; }
.r2 { border-right: 2px solid #000; }
.c1 { background-color: #3B0100; }
.c2 { background-color: #340275; }
.c3 { background-color: #0304FC; }
.c4 { background-color: #830101; }
.c5 { background-color: #9B74B5; }
.c6 { background-color: #77B7FE; }
.c7 { background-color: #72C0E4; }
.c8 { background-color: #FCF63E; }
.c9 { background-color: #ffffff; }
</style>
</head>
<body>
<?
###########################################################
$mygame = new Sudoku();
$mygame->resort(0, 0, 0);
$mygame->printout();
###########################################################
?>
</body>
</html>
