- Details
- Category: Code Samples
- Hits: 4776
Here is the source code for my Smart Sudoku Solver.
//*************************************************// // 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; } } } } }
© 2023 The Crawford Family
