Creating a Sudoku Solver (Sudoku Part II)
This is the second article of a growing obsession with sudoku programming. Below is the code for my sudoku puzzle solver. The code is well documented and easy to understand, as long as you are comfortable with recursion (the recursion is limited and the comments explain pretty well what is going on). Again, since the code is OO, PHP 5 is required to run it. This solver uses brute force to get through the puzzle.
The next phase of articles will combine the solver and the creator to create a more advanced sudoku program that can solve faster and rate puzzles by difficulty.
<?php
###########################################################
# Written by Adam Risser 10/24/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. This new cell class
# remembers what row it belongs to and its position in that
# row. Each cell also have a "given" flag to tell if the
# value was given as a clue at the beginning of the puzzle.
class Cell {
public $given = false;
public $c = array(1,2,3,4,5,6,7,8,9);
public $rowIndex;
public $cellIndex;
public function __construct($r, $c) {
$this->rowIndex = $r;
$this->cellIndex = $c;
}
#______________________________________________________
# Reset the current cell.
public function resetCell() {
$this->c = array(1,2,3,4,5,6,7,8,9);
return $this->c;
}
#______________________________________________________
#Set given (an original clue to the puzzle)
public function setGiven($v) {
$this->given = $v;
}
#______________________________________________________
#Set a Cell to a single number
public function setCandidate($v) {
$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.
class Row {
public $cells = array();
public function __construct($r="") {
for ($i=0;$i<9;$i++)
$this->cells[$i] = new Cell($r, $i);
}
}
###########################################################
# 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
{
public $rows = array();
#______________________________________________________
# Create the rows & fill in default values. Uses
# Gets index of puzzle ($p) string by converting from
# base 9 to base 10. Ie [row 1, column 1] = 9th position
# in string.
public function __construct ($p)
{
#create rows & fill in values
for ($r=0; $r<9; $r++)
$this->rows[$r] = new Row($r);
for ($r=0; $r<9; $r++) {
for ($c=0; $c<9; $c++)
{
$cellValue = $p[base_convert($r . $c, 9, 10)];
#All cells default to array(1..9) so only check if we find a value
if($cellValue != "0") {
$this->rows[$r]->cells[$c]->setCandidate($cellValue);
$this->rows[$r]->cells[$c]->setGiven(true);
}
}
}
}
#______________________________________________________
#check if cell is valid
public function isCellValid($cell)
{
$r = $cell->rowIndex;
$c = $cell->cellIndex;
#check row & column-----------------------------
for($i=0; $i < 9; $i++){
if($cell->c == $this->rows[$r]->cells[$i]->c && $c != $i)
return false;
if($cell->c == $this->rows[$i]->cells[$c]->c && $r != $i)
return false;
}
#check box--------------------------------------
#array of starting locations
$snum = array(0, 0, 0, 3, 3, 3, 6, 6, 6);
$rs = $snum[$r]; #row start
$cs = $snum[$c]; #column start
$re = $rs + 3; #row end
$ce = $cs + 3; #column end
for($i=$rs; $i < $re; $i++)
for($ii=$cs; $ii < $ce; $ii++)
if($cell->c == $this->rows[$i]->cells[$ii]->c && ($i != $r && $ii != $c))
return false; #not valid
#cell is valid!
return true;
}
#______________________________________________________
#Get next cell
public function nextCell ($cell)
{
if ($cell->cellIndex==8) #end of row
return $this->rows[$cell->rowIndex+1]->cells[0];
else
return $this->rows[$cell->rowIndex]->cells[$cell->cellIndex+1];
}
#______________________________________________________
#Solve the puzzle
public function solve ($cell = "")
{
if($cell == "") #start with first cell
$cell = $this->rows[0]->cells[0];
if($cell->rowIndex==8 && $cell->cellIndex == 8)
return true; #done solving puzzle
#already know its value
if($cell->given)
return $this->solve($this->nextCell($cell));
shuffle($cell->c); #randomize candidates
#loop through potential candidates
foreach($cell->c as $candidate)
{
$cell->setCandidate($candidate);
if ($this->isCellValid($cell))
{
if($cell->rowIndex==8 && $cell->cellIndex == 8)
return true; #done solving puzzle
#not last cell, move to next cell
if($this->solve($this->nextCell($cell)))
return true; #done solving for value
}
}
#no possible values for this cell
#reset and return false, telling previous cell that its value is no good
$cell->resetCell();
return false;
}
#______________________________________________________
# Prints out the sudoku game in HTML
public function printout ()
{
echo "<div style='color:red;'>* red numbers are givens</div>
<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)) ? ($cell->given ? "<span style='color:red;'>$i</span>" : $i) : " ";
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; }
</style>
</head>
<body>
<?
###########################################################
$puzzle = new Sudoku("076000008000010400410000375063005007000020000800100940521000084008040000700000560");
#$puzzle = new Sudoku("000050906000680020760004050003008002100000009800400600020700095050042000907030000");
#$puzzle = new Sudoku("000200090001060200030001007700800040009010700060007005600400030007090800020008000");
if($puzzle->solve())
$puzzle->printout();
else
echo "<p>Not a valid Sudoku</p>";
###########################################################
?>
</body>
</html>
