<?php
/* written by Tim Ward, June 2005
This solves sudoku puzzles.
It presents a 9x9 grid to the user which they fill in with the given
numbers. On the instruction to solve it gets as many numbers as it can
in one pass. These are then fed back into the input form. I've left it
so that the user has to press solve a few times before it finishes. This
could be changed so that the program completes the puzzle before finishing,
but to do that I'd need a trap for undoable puzzles - not a problem but
just not an immediate priority - it's pretty quick anyway.
TW 10/7 changed to be non size specific, defaults to 9x9
TW 10/8 added concept of maximum number of new numbers to find, so that people
can use it as a helper rather than a solver. Uses form field for user to define
this value. Also made showing of the working optional
TW 28/10 added guessing of each of a pair of possibles - one is then the
answer for that square if the other leads to a contradiction.
TW 22/11 expanded guessing to do a full solve when a possible is eliminated and
to keep guessing until the required number have been found. Also starts to
guess triples if necessary.
*/
class SudokuSolver
{ var $squares;
var $persquare;
var $sides;
var $maxSolve; // TW 10/8/05
var $found; // TW 10/8/05
var $startFound; // TW 10/8/05
function SudokuSolver($persquare = 3, $solve = true) // constructor
{ $this->persquare = $persquare;
$this->squares = array();
$this->found = 0; // TW 10/8/05
$this->startFound = 0; // TW 10/8/05
$this->sides = $this->persquare * $this->persquare;
$this->totalSquares = $this->sides * $this->sides;
$this->SetUp();
// TW 10/8/05
$this->maxSolve = $_POST["maxsolve"] ? $_POST["maxsolve"] + $this->found : $this->totalSquares;
if ($this->maxSolve > $this->totalSquares) $this->maxSolve = $this->totalSquares;
if ($solve && $_POST["square"])
{ $this->Solve();
if ($this->found == $this->startFound) $this->Solve();
}
} // end of fn SudokuSolver, constructor
function SetUp()
{ for ($i = 1; $i <= $this->sides; $i++)
{ for ($j = 1; $j <= $this->sides; $j++)
{ $this->squares[$i][$j] = array("value"=>0, "possible"=>array());
if ($_POST["square"][$i][$j] > 0)
{ $this->squares[$i][$j]["possible"][$_POST["square"][$i][$j]] = $_POST["square"][$i][$j];
$this->squares[$i][$j]["value"] = $_POST["square"][$i][$j];
$this->found++; // TW 10/8/05
$this->startFound++; // TW 10/8/05
$this->squares[$i][$j]["start"] = true;
} else
{ for ($k=1; $k <= $this->sides; $k++) $this->squares[$i][$j]["possible"][$k] = $k;
}
}
}
} // end of fn SetUp
function CheckOkay()
{ // Tim 28/10/05 check that puzzle is solved
// 1. check rows
for ($row = 1; $row <= $this->sides; $row++)
{ $checked = array();
for ($col = 1; $col <= $this->sides; $col++)
{ if ($this->squares[$row][$col]["value"])
{ if ($checked[$this->squares[$row][$col]["value"]])
{ return false;
} else
{ $checked[$this->squares[$row][$col]["value"]] = true;
}
}
}
}
// 2. check columns
for ($col = 1; $col <= $this->sides; $col++)
{ $checked = array();
for ($row = 1; $row <= $this->sides; $row++)
{ if ($this->squares[$row][$col]["value"])
{ if ($checked[$this->squares[$row][$col]["value"]])
{ return false;
} else
{ $checked[$this->squares[$row][$col]["value"]] = true;
}
}
}
}
// 3. now check small squares
for ($row = 1; $row <= $this->persquare; $row++)
{ for ($col = 1; $col <= $this->persquare; $col++)
{ $squares = $this->SmallSquare($row * $this->persquare, $col * $this->persquare, true);
// scan through small square
$checked = array();
foreach ($squares as $square)
{ if ($this->squares[$square["row"]][$square["col"]]["value"])
{ if ($checked[$this->squares[$square["row"]][$square["col"]]["value"]])
{ return false;
} else
{ $checked[$this->squares[$square["row"]][$square["col"]]["value"]] = true;
}
}
}
}
}
return true;
} // end of fn CheckOkay
function Form() // overrides parent
{ // first build input form
echo "<form method='POST' action='",
$_SERVER["REQUEST_URI"],
"'>\n";
$filled = $this->Table(true);
echo "found ", $filled, " out of ", $this->totalSquares,
", ", $this->totalSquares - $filled, " to go<br />\n",
"find next <input type='text' name='maxsolve' maxlength='",
strlen($this->totalSquares - $this->found), "' size='",
strlen($this->totalSquares - $this->found), "' value='";
if ($_POST["maxsolve"] && $_POST["maxsolve"] <= ($this->totalSquares - $this->found))
{ echo $_POST["maxsolve"];
} else
{ echo $this->totalSquares - $this->found;
}
echo "' /> squares, see working?",
"<input type='checkbox' name='working'",
$_POST["working"] ? " checked" : "", " /><br />\n",
"<input type='submit' value='solve' />\n</form>\n";
if (!$this->CheckOkay()) echo "** problem found **";
if ($_POST["working"]) $this->Table();
} // end of fn Form
function Solve($guess = true)
{ // TW 10/8/05 a true return from any of these functions indicates that the
// solving should continue rather than any particular level of success by that function.
if ($this->StraightCheck())
{ if ($this->CheckPairs())
{ if ($this->StraightCheck())
{ if ($this->CheckOnlyPossible())
{ if ($this->StraightCheck())
{ if ($this->CrossCheck())
{ if ($this->StraightCheck() && $guess)
{ if ($this->Guess())
{ $this->Guess(3);
}
}
}
}
}
}
}
}
} // end of fn Solve
function StraightCheck()
{ for ($i = 1; $i <= $this->sides; $i++)
{ for ($j = 1; $j <= $this->sides; $j++)
{ $this->CheckSquare($i, $j);
if ($this->found >= $this->maxSolve) return false;
}
}
return true;
} // end of fn StraightCheck
function Guess($guessLevel = 2)
{ // Tim 28/10/05 needed to check case where a particular choice between 2 numbers
// in a square leads to a contradiction. Does this by guessing each one in turn
// and testing guess on a copy of the current solution.
// check each square
for ($row = 1; $row <= $this->sides; $row++)
{ for ($col = 1; $col <= $this->sides; $col++)
{ // only look where this is a pair
$possCount = count($this->squares[$row][$col]["possible"]);
if ($possCount > 1 && $possCount <= $guessLevel)
{ // then guess each in turn
foreach ($this->squares[$row][$col]["possible"] as $guess)
{ if (!$this->CheckClone($row, $col, $guess))
{ unset($this->squares[$row][$col]["possible"][$guess]);
$this->SetSquare($row, $col);
// TW 22/11 do full solve, and keep going with guessing if necessary
$this->Solve(false);
if ($this->found >= $this->maxSolve) return false;
}
}
}
}
}
return true;
} // end of fn Guess
function CheckClone($row, $col, $guess)
{ $clone = new SudokuSolver($this->persquare, false);
// reset all squares to be same as current object
for ($i = 1; $i <= $clone->sides; $i++)
{ for ($j = 1; $j <= $clone->sides; $j++)
{ if ($i == $row && $j == $col)
{ $clone->squares[$i][$j] = array("value"=>$guess, "possible"=>array($guess=>$guess));
} else
{ $clone->squares[$i][$j] = array("value"=>$this->squares[$i][$j]["value"],
"possible"=>$this->squares[$i][$j]["possible"]);
}
}
}
$clone->maxSolve = $clone->totalSquares;
$clone->Solve(false); // don't guess
return $clone->CheckOkay();
} // end of fn CheckClone
function CrossCheck()
{ // TW 10/8/05 need to check for pairs in a row or col that
// are the only 2 that can be a number, then need to check
// if they are in the same small square - we can then eliminate
// these from possibles of others in that small square.
// first do rows
for ($row = 1; $row <= $this->sides; $row++)
{ // set up list for each number
$numbers = array();
for ($num = 1; $num <= $this->sides; $num++)
{ $numbers[$num] = array();
}
// check possibles of each cell
for ($col = 1; $col <= $this->sides; $col++)
{ foreach ($this->squares[$row][$col]["possible"] as $sqpossible)
{ $numbers[$sqpossible][] = $col;
}
}
// now check each number
for ($num = 1; $num <= $this->sides; $num++)
{ if (count($numbers[$num]) == 2)// only if 2 can be number
{ if (floor(($numbers[$num][0] - 1) / 3) === floor(($numbers[$num][1] - 1) / 3))
{ // then in same small square
$smSquare = $this->SmallSquare($row, $numbers[$num][0], true);
foreach ($smSquare as $sq)
{ if ($sq["row"] != $row) // excludes the 2 we know about
{ if (isset($this->squares[$sq["row"]][$sq["col"]]["possible"][$num]))
{ unset($this->squares[$sq["row"]][$sq["col"]]["possible"][$num]);
$this->SetSquare($sq["row"], $sq["col"]);
//echo $num, ": ";
//print_r($numbers[$num]);
//echo "<br />", $num, ":", $numbers[$num][0], "-", $numbers[$num][1], "<br />";
if ($this->found >= $this->maxSolve) return false;
}
}
}
}
}
}
}
// now do columns
for ($col = 1; $col <= $this->sides; $col++)
{ // set up list for each number
$numbers = array();
for ($num = 1; $num <= $this->sides; $num++)
{ $numbers[$num] = array();
}
// check possibles of each cell
for ($row = 1; $row <= $this->sides; $row++)
{ foreach ($this->squares[$row][$col]["possible"] as $sqpossible)
{ $numbers[$sqpossible][] = $row;
}
}
// now check each number
for ($num = 1; $num <= $this->sides; $num++)
{ if (count($numbers[$num]) == 2)// only if 2 can be number
{ if (floor(($numbers[$num][0] - 1) / 3) === floor(($numbers[$num][1] - 1) / 3))
{ // then in same small square
$smSquare = $this->SmallSquare($row, $numbers[$num][0], true);
foreach ($smSquare as $sq)
{ if ($sq["row"] != $col) // excludes the 2 we know about
{ if (isset($this->squares[$sq["row"]][$sq["col"]]["possible"][$num]))
{ unset($this->squares[$sq["row"]][$sq["col"]]["possible"][$num]);
$this->SetSquare($sq["row"], $sq["col"]);
if ($this->found >= $this->maxSolve) return false;
}
}
}
}
}
}
}
return true;
} // end of fn CrossCheck
function CheckOnlyPossible()
{ // I'm quite pleased with this algorithm, please take the time to work it out
for ($i = 1; $i <= $this->sides; $i++)
{ for ($j = 1; $j <= $this->sides; $j++)
{ // only check if not already got
if (!$this->squares[$i][$j]["value"])
{ // check all in row
$possible = $this->squares[$i][$j]["possible"]; // local copy to play with
for ($col = 1; $col <= $this->sides; $col++)
{ if ($col != $j) // don't check against self
{ foreach ($this->squares[$i][$col]["possible"] as $taken)
{ if (isset($possible[$taken])) unset($possible[$taken]);
}
}
}
//if there is one left then it must be that one
if (count($possible) == 1)
{ foreach($possible as $hit) // will only go once
{ $this->squares[$i][$j]["possible"] = array("$hit"=>"$hit");
$this->squares[$i][$j]["value"] = $hit;
$this->found++;
if ($this->found >= $this->maxSolve) return false;
}
}
if (!$this->squares[$i][$j]["value"])
{ // check all in column
$possible = $this->squares[$i][$j]["possible"]; // local copy to play with
for ($row = 1; $row <= $this->sides; $row++)
{ if ($row != $i) // don't check against self
{ foreach ($this->squares[$row][$j]["possible"] as $taken)
{ if (isset($possible[$taken])) unset($possible[$taken]);
}
}
}
//if there is one left then it must be that one
if (count($possible) == 1)
{ foreach($possible as $hit) // will only go once
{ $this->squares[$i][$j]["possible"] = array("$hit"=>"$hit");
$this->squares[$i][$j]["value"] = $hit;
$this->found++;
if ($this->found >= $this->maxSolve) return false;
}
}
if (!$this->squares[$i][$j]["value"])
{ // check all in small square
$smSquare = $this->SmallSquare($i, $j, true);
$possible = $this->squares[$i][$j]["possible"]; // local copy to play with
foreach ($smSquare as $smCell)
{ if ($smCell["row"] != $i || $smCell["col"] != $j)
{ foreach ($this->squares[$smCell["row"]][$smCell["col"]]["possible"] as $taken)
{ if (isset($possible[$taken])) unset($possible[$taken]);
}
}
}
//if there is one left then it must be that one
if (count($possible) == 1)
{ foreach($possible as $hit) // will only go once
{ $this->squares[$i][$j]["possible"] = array("$hit"=>"$hit");
$this->squares[$i][$j]["value"] = $hit;
$this->found++;
if ($this->found >= $this->maxSolve) return false;
}
}
}
}
}
}
}
return true;
} // end of fn CheckOnlyPossible
function CheckPairs()
{ // check each row
for ($row = 1; $row <= $this->sides; $row++)
{ // get pairs on row
$pairs = array();
for ($col = 1; $col <= $this->sides; $col++)
{ if (count($this->squares[$row][$col]["possible"]) == 2)
{ $pair = array();
foreach ($this->squares[$row][$col]["possible"] as $poss)
{ $pair[] = $poss;
}
sort($pair);
$pairs[count($pairs) + 1] = array("row"=>$row, "col"=>$col, "values"=>$pair);
}
}
if (count($pairs) > 1)
{ for ($i = 1; $i < count($pairs); $i++)
{ // check rest for any the same
for ($j = $i + 1; $j <= count($pairs); $j++)
{ if (($pairs[$i]["values"][0] == $pairs[$j]["values"][0])
&& ($pairs[$i]["values"][1] == $pairs[$j]["values"][1]))
{ // pair found!!!
// go through rest of row getting rid of any of these numbers
for ($k = 1; $k <= $this->sides; $k++)
{ if ($k != $pairs[$i]["col"] && $k != $pairs[$j]["col"] && !$this->squares[$row][$k]["value"])
{ if (isset($this->squares[$row][$k]["possible"][$pairs[$i]["values"][0]]))
{ unset($this->squares[$row][$k]["possible"][$pairs[$i]["values"][0]]);
}
if (isset($this->squares[$row][$k]["possible"][$pairs[$i]["values"][1]]))
{ unset($this->squares[$row][$k]["possible"][$pairs[$i]["values"][1]]);
}
if ($this->SetSquare($row, $k))
{ if ($this->found >= $this->maxSolve) return false;
}
}
}
}
}
}
}
}
// now check columns
for ($col = 1; $col <= $this->sides; $col++)
{ // get pairs on column
$pairs = array();
for ($row = 1; $row <= $this->sides; $row++)
{ if (count($this->squares[$row][$col]["possible"]) == 2)
{ $pair = array();
foreach ($this->squares[$row][$col]["possible"] as $poss)
{ $pair[] = $poss;
}
sort($pair);
$pairs[count($pairs) + 1] = array("row"=>$row, "col"=>$col, "values"=>$pair);
}
}
if (count($pairs) > 1)
{ for ($i = 1; $i < count($pairs); $i++)
{ // check rest for any the same
for ($j = $i + 1; $j <= count($pairs); $j++)
{ if (($pairs[$i]["values"][0] == $pairs[$j]["values"][0])
&& ($pairs[$i]["values"][1] == $pairs[$j]["values"][1]))
{ // pair found!!!
// go through rest of row getting rid of any of these numbers
for ($k = 1; $k <= $this->sides; $k++)
{ if ($k != $pairs[$i]["row"] && $k != $pairs[$j]["row"] && !$this->squares[$k][$col]["value"])
{ if (isset($this->squares[$k][$col]["possible"][$pairs[$i]["values"][0]]))
{ unset($this->squares[$k][$col]["possible"][$pairs[$i]["values"][0]]);
}
if (isset($this->squares[$k][$col]["possible"][$pairs[$i]["values"][1]]))
{ unset($this->squares[$k][$col]["possible"][$pairs[$i]["values"][1]]);
}
if ($this->SetSquare($k, $col))
{ if ($this->found >= $this->maxSolve) return false;
}
}
}
}
}
}
}
}
// check each small square
for ($trow = 1; $trow <= $this->persquare; $trow++)
{ for ($tcol = 1; $tcol <= $this->persquare; $tcol++)
{ $squares = $this->SmallSquare($trow * $this->persquare, $tcol * $this->persquare, true);
// build list of pairs
$pairs = array();
foreach ($squares as $square)
{ if (count($this->squares[$square["row"]][$square["col"]]["possible"]) == 2)
{ $pair = array();
foreach ($this->squares[$square["row"]][$square["col"]]["possible"] as $poss)
{ $pair[] = $poss;
}
sort($pair);
$pairs[count($pairs)+1] = array("row"=>$square["row"], "col"=>$square["col"],
"values"=>$pair);
}
}
if (count($pairs) > 1)
{ // check each for one the same
for ($i = 1; $i <= count($pairs); $i++)
{ for ($j = $i + 1; $j <= count($pairs); $j++)
{ if (($pairs[$i]["values"][0] == $pairs[$j]["values"][0])
&& ($pairs[$i]["values"][1] == $pairs[$j]["values"][1]))
{ // we have a pair!
// go through rest to find pairs
for ($k = 1; $k <= count($pairs); $k++)
{ if ($k != $i && $k != $j)
{ $row = $pairs[$k]["row"];
$col = $pairs[$k]["col"];
if (!$this->squares[$row][$col]["value"])
{ if (isset($this->squares[$row][$col]["possible"][$pairs[$i]["values"][0]]))
{ unset($this->squares[$row][$col]["possible"][$pairs[$i]["values"][0]]);
}
if (isset($this->squares[$row][$col]["possible"][$pairs[$i]["values"][1]]))
{ unset($this->squares[$row][$col]["possible"][$pairs[$i]["values"][1]]);
}
if ($this->SetSquare($row, $col))
{ if ($this->found >= $this->maxSolve) return false;
}
}
}
}
}
}
}
}
}
}
return true;
} // end of fn CheckPairs
function CheckSquare($row, $col)
{ if ($this->squares[$row][$col]["value"])
{ return true;
} else
{ // check along row
for ($k=1; $k <= $this->sides; $k++)
{ if ($value = $this->squares[$row][$k]["value"])
{ //echo "$row, $col : ", $value, "</ br>";
if (isset($this->squares[$row][$col]["possible"][$value]))
{ unset($this->squares[$row][$col]["possible"][$value]);
if ($this->SetSquare($row, $col)) return true;
}
}
}
// check along column
for ($k=1; $k <= $this->sides; $k++)
{ if ($value = $this->squares[$k][$col]["value"])
{ if (isset($this->squares[$row][$col]["possible"][$value]))
{ unset($this->squares[$row][$col]["possible"][$value]);
if ($this->SetSquare($row, $col)) return true;
}
}
}
// now check others in small square that aren't in same row or column
foreach ($this->SmallSquare($row, $col) as $toCheck)
{ if ($value = $this->squares[$toCheck["row"]][$toCheck["col"]]["value"])
{ if (isset($this->squares[$row][$col]["possible"][$value]))
{ unset($this->squares[$row][$col]["possible"][$value]);
if ($this->SetSquare($row, $col)) return true;
}
}
}
}
return false;
} // end of fn CheckSquare
function SmallSquare($row, $col, $getall = false)
{ // finds all in small square containing cell $row, $col
$sm = array();
$topRow = ((ceil($row / $this->persquare) - 1) * $this->persquare) + 1;
$topCol = ((ceil($col / $this->persquare) - 1) * $this->persquare) + 1;
for ($i = $topRow; $i < ($topRow + $this->persquare); $i++)
{ for ($j = $topCol; $j < ($topCol + $this->persquare); $j++)
{ if (($i != $row && $j != $col) || $getall)
{ $sm[] = array("row"=>$i, "col"=>$j);
}
}
}
return $sm;
} // end of fn SmallSquare
function SetSquare($row, $col)
{ if (count($this->squares[$row][$col]["possible"]) == 1 && $this->found < $this->maxSolve)
{ foreach ($this->squares[$row][$col]["possible"] as $value)
{ $this->squares[$row][$col]["value"] = $value;
}
$this->found++;
return true;
} else return false;
} // end of fn SetSquare
function Table($form = false)
{ $filled = 0;
echo "<table border='1' bordercolor='black'>\n";
for ($row = 1; $row <= $this->persquare; $row++)
{ echo "\t<tr>\n";
for ($col = 1; $col <= $this->persquare; $col++)
{ echo "\t\t<td>\n";
$filled += $this->SubTable($row, $col, $form);
echo "\t\t</td>\n";
}
echo "\t</tr>\n";
}
echo "</table>\n";
return $filled;
} // end of fn Table
function SubTable($trow, $tcol, $form = false)
{ $filled = 0;
echo "\t\t\t<table border='1' bordercolor='black'>\n";
$rowPlus = ($trow - 1) * $this->persquare;
$colPlus = ($tcol - 1) * $this->persquare;
for ($row = 1; $row <= $this->persquare; $row++)
{ echo "\t\t\t\t<tr>\n";
for ($col = 1; $col <= $this->persquare; $col++)
{ echo "\t\t\t\t\t<td",
$this->squares[$row + $rowPlus][$col + $colPlus]["start"] ? " bgcolor='red'" : "",
">";
$filled += $this->Square($row + $rowPlus, $col + $colPlus, $form);
echo "</td>\n";
}
echo "\t\t\t\t</tr>\n";
}
echo "\t\t\t</table>\n";
return $filled;
} // end of fn SubTable
function Square($row, $col, $form = false)
{ $filled = 0;
if ($form)
{ echo "<input type='text' maxlength='", strlen($this->sides),
"' name='square[", $row, "][", $col, "]' size='", strlen($this->sides),
"' value='";
if ($this->squares[$row][$col]["value"])
{ echo $this->squares[$row][$col]["value"];
$filled++;
}
echo "'/>";
} else
{ echo implode(",", $this->squares[$row][$col]["possible"]);
}
return $filled;
} // end of fn Square
} // end of defn SudokuSolver
?>