Here is the source code for my Smart Sudoku Solver.
[code]
//*************************************************//
// Written by David L G Crawford, January 25, 2019 //
//*************************************************//
global $possibles,$showSteps,$attemptCounter,$maxAttempts;
// Get the number of digits
$digits = 9;
$square = sqrt($digits);
$cells = array(); // Set up grid as a 2 dimensional array
if(! isset($_REQUEST['solve']) && ! isset($_REQUEST['brute']))
{
echo "<form action='sudoku.php' method='post'>";
setupBoard();
echo "<input type='submit' name='solve' value='Show Each Step'><input type='submit' name='solve' value='Just Solve It'>";
} else {
// get the values of the cells from what was submitted
for ($row=0; $row<$digits; $row++)
{
for ($column=0; $column<$digits; $column++)
{
$cells[$row][$column] = ( isset($_REQUEST["cell".dechex($row).dechex($column)]) ? $_REQUEST["cell".dechex($row).dechex($column)] : "");
}
}
$possibles = calculatePossibles($cells); // The possible numbers that a cell can be.
echo "Before trying anything, here's the board with ".countArray($cells)." out of ".($digits*$digits)." cells filled.";
if(isset($_REQUEST['solve']) && $_REQUEST['solve'] == "Show Each Step")
{
$showSteps = TRUE;
} else {
$showSteps = FALSE;
}
if(isset($_REQUEST['brute']))
{
$showSteps = TRUE;
}
if (! $showSteps) displayBoard($cells,$possibles);
$attemptCounter = 0;
$maxAttempts = 500;
attemptToSolve($cells);
switch (checkBoard())
{
case -1:
echo "<h2>Unable to solve as this Sudoku has no solution</h2>";
echo "<form action='sudoku.php' method='post'>";
displayBoard($cells);
break;
case 0:
echo "<h2>Successfully Solved after $attemptCounter attempts!</h2>";
echo "<form action='sudoku.php' method='post'>";
displayBoard($cells);
break;
case 1:
if(isset($_REQUEST['brute']))
{
bruteForce();
} else {
echo "<h2>Unable to solve using smart logic. Time for Brute Force!</h2>";
echo "<form action='sudoku.php' method='post'>";
displayBoard($cells,$possibles);
echo "<input type='submit' name='brute' value='BRUTE FORCE'>";
}
break;
}
}
echo "<input type='submit' name='reset' value='reset'>";
echo "</form>";
function bruteForce($attemptNum = 1)
{
global $cells, $digits, $possibles;
for($length=2; $length<=$digits; $length++) // we will look for possibles with a length of 2, then 3, etc.
{
for ($row=0; $row<$digits; $row++)
{
for ($column=0; $column<$digits; $column++)
{
if(strlen($possibles[$row][$column]) == $length)
{
// save the current status so we can roll back if this fails
$savedCells = $cells;
$savedPossibles = $possibles;
// pick one of the values and test it
$values = str_split($possibles[$row][$column]);
foreach($values as $value)
{
echo "<h3>Brute Force Level $attemptNum: Going to try with $value in cell [$row,$column]</h3>";
if(setCell($row,$column,$value))
{
attemptToSolve($cells,$row,$column);
switch (checkBoard())
{
case -1:
echo "<h2>This attempt failed, let's roll back to level $attemptNum and try again with the next possible</h2>";
$cells = $savedCells;
//$possibles = calculatePossibles($cells);
$possibles = $savedPossibles;
displayBoard($cells,$possibles);
break;
case 0:
echo "<h2>Brute force worked!</h2>";
echo "<form action='sudoku.php' method='post'>";
displayBoard($cells);
break;
case 1:
echo "<h2>We're going to recursively try another brute force on a different cell</h2>";
bruteForce($attemptNum+1);
break;
}
}
}
}
}
}
}
}
function attemptToSolve($cells,$row = FALSE,$column = FALSE)
{
global $digits, $cells, $possibles, $showSteps,$attemptCounter,$maxAttempts;
if($attemptCounter++ > $maxAttempts)
{
echo "<h2>We've tried $maxAttempts times and are going to stop here and exit.</h2>";
displayBoard($cells,$possibles);
exit;
}
if ($showSteps) displayBoard($cells,$possibles,$row,$column);
if(checkBoard()>0) test1();
if(checkBoard()>0) test2r();
if(checkBoard()>0) test2c();
if(checkBoard()>0) test2s();
if(checkBoard()>0) test3r();
if(checkBoard()>0) test3c();
if(checkBoard()>0) test4r();
if(checkBoard()>0) test4c();
}
function checkBoard()
{
// Checks the board to see if we are finished and returns:
// -1 board has failed and can't be solved
// 0 board is finished successfully
// 1 board is not finsihed, and we can continue working
global $digits, $cells, $possibles;
if(countArray($cells) == ($digits*$digits))
{
return 0;
}
for ($row=0; $row<$digits; $row++)
{
for ($column=0; $column<$digits; $column++)
{
if($cells[$row][$column] == "" && $possibles[$row][$column] == "")
{
//echo "UNABLE TO PROCEED: Found that unsolved cell [$row,$column] has no POSSIBLES<br>";
return -1;
}
}
}
return 1;
}
function setupBoard()
{
global $digits, $cells, $square;
// Check that this is a valid number that will make a square sudoku board. ie. it is a square of a smaller number
if((int) $square != $square )
{
echo "<p>The number of digits must be a square of a smaller number. Valid selections are 4 (the square of 2), 9 (the square of 3), 16 (the square of 4), etcetera.</p>";
} else {
// setup the grid
$cells = array_fill ( 0 , $digits , array_fill ( 0 , $digits , "" ) );
// Draw the grid and allow the user to enter some numbers
displayBoard($cells);
echo "<button type='button' onclick='fillPuzzle(1)'>Load game #1</button> puzzle from Will Shortz's Sudoku, February 2016, number 197<br>";
echo "<button type='button' onclick='fillPuzzle(2)'>Load game #2</button> puzzle from Will Shortz's Sudoku, February 2016, number 196<br>";
echo "<button type='button' onclick='fillPuzzle(3)'>Load game #3</button> an extremely hard Sudoku that must use Brute Force to determine that cell [0,0] must be 3<br>";
}
}
function displayBoard($cells,$possibles = FALSE,$highlightRow = FALSE,$highlightColumn = FALSE)
{
global $digits, $square;
$message = "";
echo "<table>\n";
echo "<tr><th colspan='".$digits."'>The Puzzle</th>";
if(is_array($possibles))
{
echo "<td></td><th colspan='".$digits."'>The Possibles</th>";
}
echo "</tr>\n";
$bottom = "border-bottom-style: none;";
for ($row=0; $row<$digits; $row++)
{
echo "<tr>";
if($row % $square == 0)
{
$top = "border-top-style: solid;";
} else {
$top = "border-top-style: none;";
}
if($row == $digits-1)
{
$bottom = "border-bottom-style: solid;";
}
$right = "border-right-style: none;";
for ($column=0; $column<$digits; $column++)
{
if($column % $square == 0)
{
$left = "border-left-style: solid;";
} else {
$left = "border-left-style: none;";
}
if($column == $digits-1)
{
$right = "border-right-style: solid;";
}
$cellname = "cell".dechex($row).dechex($column);
if($highlightRow !== FALSE && $highlightRow == $row && $highlightColumn == $column)
{
$highlight = "background-color: yellow;";
} else {
$highlight = "";
}
if($possibles && $cells[$row][$column] == "" && $possibles[$row][$column] == "")
{
$message = "UNABLE TO PROCEED: Found that unsolved cell [$row,$column] has no POSSIBLES<br>";
$highlight = "background-color: red;";
} else {
$highlight = "";
}
echo "<td style='".$top.$right.$bottom.$left."'><input size='1' id='".$cellname."' name='".$cellname."' type='text' style='".$highlight."' value='".$cells[$row][$column]."'></td>";
}
if(is_array($possibles))
{
// display the possibles
echo "<td width='50'> </td>";
for ($column=0; $column<$digits; $column++)
{
if($column % $square == 0)
{
$left = "border-left-style: solid;";
} else {
$left = "border-left-style: none;";
}
if($column == $digits-1)
{
$right = "border-right-style: solid;";
}
$cellname = "cell".dechex($row).dechex($column);
if($cells[$row][$column] == "" && $possibles[$row][$column] == "")
{
$highlight = "background-color: red;";
} else {
$highlight = "";
}
echo "<td style='".$top.$right.$bottom.$left."'><input size='9' type='text' value='".$possibles[$row][$column]."' disabled='disabled' style='".$highlight."font-size: 0.5em;'></td>";
}
}
echo "</tr>\n";
}
echo "</table>\n";
echo $message;
}
function countArray($arrayToCount)
{
global $digits;
$count=0;
for ($column=0; $column<$digits; $column++)
{
for ($row=0; $row<$digits; $row++)
{
if($arrayToCount[$row][$column] != "") $count++;
}
}
return $count;
}
function calculatePossibles($cells)
{
global $digits;
// Initially a cell can be any number
// we build a string of all the possible values
$string = "";
for($i=1; $i<=$digits; $i++)
{
$string .= dechex($i);
}
$possibles = array_fill ( 0 , $digits , array_fill ( 0 , $digits , $string ) );
// Now we start looking through the grid and if there is a number filled in, we remove it from the possibles
for ($column=0; $column<$digits; $column++)
{
for ($row=0; $row<$digits; $row++)
{
if($cells[$row][$column] != "")
{
$possibles[$row][$column] = "";
$numberToRemove = $cells[$row][$column];
$possibles = removePossible($possibles,$numberToRemove,$row,$column);
}
}
}
return $possibles;
}
function removePossible($possibles,$numberToRemove,$row,$column)
{
global $digits,$square;
// remove this number from the rest of the cells in this COLUMN (note, the column remains the same, we change which row we are looking at)
for ($rowWork=0; $rowWork<$digits; $rowWork++)
{
$possibles[$rowWork][$column] = str_replace($numberToRemove,"",$possibles[$rowWork][$column]);
}
// remove this number from the rest of the cells in this ROW
for ($columnWork=0; $columnWork<$digits; $columnWork++)
{
$possibles[$row][$columnWork] = str_replace($numberToRemove,"",$possibles[$row][$columnWork]);
}
// remove this number from the rest of the cells in this SQUARE
// first we figure out which square we are in.
// Example, cell 2,4 in a 9 digit game (square is 3x3), would be in the square 0,1
$squareRow = (int) ($row/$square); // 2/3 = 0
$squareColumn = (int) ($column/$square); // 4/3 = 1
for ($rowWork=0; $rowWork<$square; $rowWork++) // runs from row 0 to 2
{
for ($columnWork=0; $columnWork<$square; $columnWork++) // runs from column 0 to 2
{
$thisRow = ($squareRow*$square)+$rowWork; // (0x3)+$rowWork gives numbers 0 to 2 for the row
$thisColumn = ($squareColumn*$square)+$columnWork; // (1x3)+$rowcolumn gives numbers 3 to 5 for the column
$possibles[$thisRow][$thisColumn] = str_replace($numberToRemove,"",$possibles[$thisRow][$thisColumn]);
}
}
return $possibles;
}
function setCell($row,$column,$value)
{
global $cells, $possibles, $square, $digits;
$safe = TRUE;
// check for a mtach in this column
for ($rowWork=0; $rowWork<$digits; $rowWork++)
{
if($row != $rowWork && $cells[$rowWork][$column] == $value)
{
$safe = FALSE;
echo "<h2>ERROR: Can't add $value to cell [$row,$column] because it's in cell [$rowWork,$column].</h2>";
break;
}
}
// check for a match in this row
for ($columnWork=0; $columnWork<$digits; $columnWork++)
{
if($column != $columnWork && $cells[$row][$columnWork] == $value)
{
$safe = FALSE;
echo "<h2>ERROR: Can't add $value to cell [$row,$column] because it's in cell [$row][$columnWork].</h2>";
break;
}
}
// check for a match in this square
// first we figure out which square we are in.
// Example, cell 2,4 in a 9 digit game (square is 3x3), would be in the square 0,1
$squareRow = (int) ($row/$square); // 2/3 = 0
$squareColumn = (int) ($column/$square); // 4/3 = 1
for ($rowWork=0; $rowWork<$square; $rowWork++) // runs from row 0 to 2
{
for ($columnWork=0; $columnWork<$square; $columnWork++) // runs from column 0 to 2
{
$thisRow = ($squareRow*$square)+$rowWork; // (0x3)+$rowWork gives numbers 0 to 2 for the row
$thisColumn = ($squareColumn*$square)+$columnWork; // (1x3)+$rowcolumn gives numbers 3 to 5 for the column
if(!($row == $thisRow && $column == $thisColumn) && ($cells[$thisRow][$thisColumn] == $value))
{
$safe = FALSE;
echo "<h2>ERROR: Can't add $value to cell [$row,$column] because it's in cell [$thisRow][$thisColumn].</h2>";
break 2;
}
}
}
if($safe)
{
$cells[$row][$column] = $value;
$possibles[$row][$column] = "";
$possibles = removePossible($possibles,$value,$row,$column); // remove that number from the possibles in that row/column/square
} else {
exit;
}
return $safe;
}
function test1()
{
// Finds cells that have only a single possible answer. If that's the only possible number for that cell, then it must be the number for that cell.
global $digits,$cells,$possibles, $showSteps;
for ($row=0; $row<$digits; $row++)
{
for ($column=0; $column<$digits; $column++)
{
if(strlen($possibles[$row][$column]) == 1)
{
if ($showSteps) echo "Test #1 found that cell [$row,$column] has only one POSSIBLE ".$possibles[$row][$column]."<br>";
if(setCell($row,$column,$possibles[$row][$column]))
{
attemptToSolve($cells,$row,$column);
}
break 2;
}
}
}
}
function test2r()
{
// finds where a number is only possible once in a ROW
// if that's the only place in the column it COULD go, then that's where it MUST go
global $digits,$cells,$possibles, $showSteps;
for ($row=0; $row<$digits; $row++)
{
$values = implode($possibles[$row]); // put all the values into one string
for($i=1; $i<=$digits; $i++) // we'll run through each possible digit
{
if (substr_count($values, dechex($i)) == 1) // if there's only one place it can be
{
for ($column=0; $column<$digits; $column++) // we need to look through each cell in this row to find the cell that has that value
{
if (substr_count($possibles[$row][$column],dechex($i))) // this is the cell with that number
{
if ($showSteps) echo "Test #2-ROW found that ".dechex($i)." is only one place in ROW $row, cell [$row,$column]<br>";
if(setCell($row,$column,$i))
{
attemptToSolve($cells,$row,$column);
}
break 3;
}
}
}
}
}
}
function test2c()
{
// finds where a number is only possible once in a COLUMN
// if that's the only place in the column it COULD go, then that's where it MUST go
global $digits,$cells,$possibles, $showSteps;
for ($column=0; $column<$digits; $column++)
{
$values = implode(array_column($possibles,$column)); // put all the values into one string
for($i=1; $i<=$digits; $i++) // we'll run through each possible digit
{
if (substr_count($values, dechex($i)) == 1) // if there's only one place it can be
{
for ($row=0; $row<$digits; $row++) // we need to look through each cell in this column to find the cell that has that value
{
if (substr_count($possibles[$row][$column],dechex($i))) // this is the cell with that number
{
if ($showSteps) echo "Test #2-COLUMN found that ".dechex($i)." is only one place in COLUMN $column, cell [$row,$column]<br>";
if(setCell($row,$column,$i))
{
attemptToSolve($cells,$row,$column);
}
break 3;
}
}
}
}
}
}
function test2s()
{
// finds where a number is only possible once in a SQUARE
// if that's the only place in the square it COULD go, then that's where it MUST go
global $digits,$cells,$possibles,$square, $showSteps;
// the outer two loops cycle through the squares
for ($squareRow=0; $squareRow<$square; $squareRow++)
{
for ($squareColumn=0; $squareColumn<$square; $squareColumn++)
{
$values = ""; // set (or reset) this to empty
// within each square we test each cell
for ($row=0; $row<$square; $row++)
{
for ($column=0; $column<$square; $column++)
{
$values .= $possibles[($squareRow*$square)+$row][($squareColumn*$square)+$column]; // put all the values into one string
}
}
for($i=1; $i<=$digits; $i++) // we'll run through each possible digit
{
if (substr_count($values, dechex($i)) == 1) // if there's only one place it can be
{
for ($row=0; $row<$square; $row++)
{
for ($column=0; $column<$square; $column++) // we need to look through each cell in this row to find the cell that has that value
{
if (substr_count($possibles[($squareRow*$square)+$row][($squareColumn*$square)+$column],dechex($i))) // this is the cell with that number
{
if ($showSteps) echo "Test #2-SQUARE found that ".dechex($i)." is only one place in a SQUARE, cell [$row,$column]<br>";
if(setCell(($squareRow*$square)+$row,($squareColumn*$square)+$column,$i))
{
attemptToSolve($cells,$row,$column);
}
break 5;
}
}
}
}
}
}
}
}
function test3r()
{
// Looks for sets of two possibles in a row (then column),
// then will remove those digits from other possibles along the same row (column)
global $digits,$cells,$possibles,$square,$showSteps;
$success = FALSE;
for ($row=0; $row<$square; $row++)
{
for ($column=0; $column<$square; $column++)
{
if(strlen($possibles[$row][$column]) == 2)
{
for($i=$column+1;$i<$digits;$i++) // we only need to look to the right of the current position
{
if ($possibles[$row][$column]==$possibles[$row][$i])
{
// We found a matching pair
$success = TRUE;
$message = "Test #3-ROW found MATCHING POSSIBLES in cell [$row,$column] and cell [$row,$i] and cleared ".$possibles[$row][$column]." from cells";
for ($columnWork=0; $columnWork<$digits; $columnWork++)
{
if($columnWork != $column && $columnWork != $i) // skip the two cells that have the matching pair
{
//remove from all the other cells in this row
$message .= " [$row,$columnWork]";
$numbersToRemove = str_split($possibles[$row][$column]);
$possibles[$row][$columnWork] = str_replace($numbersToRemove,"",$possibles[$row][$columnWork]);
}
}
if ($showSteps) echo $message."<br>";
attemptToSolve($cells,$row,$column);
break 3;
}
}
}
}
}
}
function test3c()
{
// Looks for sets of two possibles in a column,
// then will remove those digits from other possibles along the same column
global $digits,$cells,$possibles,$square,$showSteps;
for ($column=0; $column<$square; $column++)
{
for ($row=0; $row<$square; $row++)
{
if(strlen($possibles[$row][$column]) == 2)
{
for($i=$row+1;$i<$digits;$i++) // we only need to look down from the current position
{
if ($possibles[$row][$column]==$possibles[$i][$column])
{
// We found a matching pair
$success = TRUE;
$message = "Test #3-COLUMN found MATCHING POSSIBLES ".$possibles[$row][$column]." in cell [$row,$column] and cell [$i,$column] and cleared from cells";
for ($rowWork=0; $rowWork<$digits; $rowWork++)
{
if($rowWork != $row && $rowWork != $i) // skip the two cells that have the matching pair
{
//remove from all the other cells in this row
$message .= " [$rowWork,$column]";
$numbersToRemove = str_split($possibles[$row][$column]);
$possibles[$rowWork][$column] = str_replace($numbersToRemove,"",$possibles[$rowWork][$column]);
}
}
if ($showSteps) echo $message."<br>";
attemptToSolve($cells,$row,$column);
break 3;
}
}
}
}
}
}
function test4r()
{
// Looks for sets of 3 possibles that match in a row,
// then will remove possibles along the same row
// Will also match a set of 3, set of 3 and set of 2
// eg. "156", "15", "156 would be a match and remove 1, 5, & 6 from the other possibles
global $digits,$cells,$possibles,$showSteps;
$success = FALSE;
for ($row=0; $row<$digits; $row++)
{
for ($column=0; $column<$digits; $column++)
{
$matches = array($row);
if(strlen($possibles[$row][$column]) == 3)
{
for($i=0;$i<$digits;$i++)
{
if ($i != $column && strlen($possibles[$row][$i]) > 1)
{
$searches = str_split($possibles[$row][$i]);
$match = TRUE;
foreach($searches as $search)
{
if(strpos($possibles[$row][$column],$search) === FALSE)
{
$match = FALSE;
}
}
if($match) $matches[] = $i;
}
}
}
if(count($matches) == 3)
{
// We found three matching sets
sort($matches);
for ($columnWork=0; $columnWork<$digits; $columnWork++)
{
if($columnWork != $matches[0] && $columnWork != $matches[1] && $columnWork != $matches[2]) // skip the three cells that have the match
{
//remove from all the other cells in this column
$numbersToRemove = str_split($possibles[$row][$column]);
$beforeChange = $possibles[$row][$columnWork];
$possibles[$row][$columnWork] = str_replace($numbersToRemove,"",$possibles[$row][$columnWork]);
if($beforeChange != $possibles[$row][$columnWork])
{
$success = TRUE;
}
}
}
if($success)
{
if ($showSteps) echo "Test #4-ROW found 3-WAY MATCHING POSSIBLES in cells [".$matches[0].",$column], [".$matches[1].",$column] and [".$matches[2].",$column] and cleared ".$possibles[$row][$column]." from the other cells in row $row.<br>";
attemptToSolve($cells,$row,$column);
break 2;
}
}
}
}
}
function test4c()
{
// Looks for sets of 3 possibles that match in a column,
// then will remove possibles along the same column
// Will also match a set of 3, set of 3 and set of 2
// eg. "156", "15", "156 would be a match and remove 1, 5, & 6 from the other possibles
global $digits,$cells,$possibles;
$success = FALSE;
for ($column=0; $column<$digits; $column++)
{
for ($row=0; $row<$digits; $row++)
{
$matches = array($row);
if(strlen($possibles[$row][$column]) == 3)
{
for($i=0;$i<$digits;$i++)
{
if ($i != $row && strlen($possibles[$i][$column]) > 1)
{
$searches = str_split($possibles[$i][$column]);
$match = TRUE;
foreach($searches as $search)
{
if(strpos($possibles[$row][$column],$search) === FALSE)
{
$match = FALSE;
}
}
if($match) $matches[] = $i;
}
}
}
if(count($matches) == 3)
{
// We found three matching sets
sort($matches);
for ($rowWork=0; $rowWork<$digits; $rowWork++)
{
if($rowWork != $matches[0] && $rowWork != $matches[1] && $rowWork != $matches[2]) // skip the three cells that have the match
{
//remove from all the other cells in this column
$numbersToRemove = str_split($possibles[$row][$column]);
$beforeChange = $possibles[$rowWork][$column];
$possibles[$rowWork][$column] = str_replace($numbersToRemove,"",$possibles[$rowWork][$column]);
if($beforeChange != $possibles[$rowWork][$column])
{
$success = TRUE; // just finding a set is not success, only if we actually have removed digits from another cell
}
}
}
if($success)
{
if ($showSteps) echo "Test #4-COLUMN found 3-WAY MATCHING POSSIBLES in cells [".$matches[0].",$column], [".$matches[1].",$column] and [".$matches[2].",$column] and cleared ".$possibles[$row][$column]." from the other cells in column $column.<br>";
attemptToSolve($cells,$row,$column);
break 2;
}
}
}
}
}
[/code]