Code Samples

Code Samples

Sudoku Source Code

Code Samples

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]

Sudoku Layout

Code Samples

Here is a brief description of the program and how it works.

if this if first run,
    setupBoard()
else
    get the values of the cells from what was submitted
    calculatePossibles()
    attemptToSolve()
    checkBoard()
        if no solution solution possible give message "Unable to solve as this Sudoku has no solution"
        if solved give message "Successfully Solved!"
        if we haven't been able to solve give message "Unable to solve using smart logic."
    displayBoard()
exit program

function attemptToSolve()
{
    displayBoard()
    if not yet solved, test1()
    if not yet solved, test2r()
    if not yet solved, test2c()
    if not yet solved, test2s()
    if not yet solved, test3r()
    if not yet solved, test3c()
    if not yet solved, test4r()
    if not yet solved, test4c()
}

function checkBoard()
{
    if all cells are filled, return "finished"
    loop through all cells
        if cell is empty and possible is empty return "UNABLE TO PROCEED: Found that unsolved cell has no POSSIBLES"
    return "not finished, and we can continue working"
}

function setupBoard()
{
    if the size of the board is not valid (ie. it is not a square of a smaller number)
        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
        Draw the grid and allow the user to enter some numbers
        displayBoard()
}

function displayBoard()
{
    loop through all the rows
        loop through all the columns
            draw a square and put in the value of that cell
}

function countArray($arrayToCount)
{
    loop through all the rows
        loop through all the columns
            if cell is not empty, count it
    return count;
}

function calculatePossibles()
{
    Initially a cell can be any number, we build a string of all the possible values that looks like this "123456789" for a 9x9 puzzle, or "123456789abcdefg" for a 16x16 puzzle
    create an array called 'possibles' and put the string in each cell
    Now we start looking through the grid and if there is a number filled in, we remove it from the possibles
    loop through all the rows
        loop through all the columns
            if cells has a value
                possibles for this cell is emptied
                removePossible()
}

function removePossible()
{
    remove this number from the rest of the possibles in this COLUMN
    remove this number from the rest of the possibles in this ROW
    remove this number from the rest of the possibles in this SQUARE
    first we figure out which square we are in.
}

function setCell()
{
    check for a match in this column
    check for a match in this row
    check for a match in this square
    if no matches were found
        set cell value
        removePossible()
}

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.
    loop through all the rows
        loop through all the columns
            if possibles is only 1 digit
                setCell()
                recursively attemptToSolve()
}

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
    loop through all the rows
        loop through all the numbers (1 to 9)
            if there's only one place it can be
                setCell()
                recursively attemptToSolve()
}

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
    loop through all the columns
        loop through all the numbers (1 to 9)
            if there's only one place it can be
                setCell()
                recursively attemptToSolve()
}

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
}

function test3r()
{
    // Looks for sets of two possibles in a row
    // then will remove those digits from other possibles along the same row
}

function test3c()
{
    // Looks for sets of two possibles in a column,
    // then will remove those digits from other possibles along the same column
}

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
}

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
}

Sudoku

Code Samples

Smart Sudoku Solver

Smart Mode

It has 4 smart methods for finding individual numbers.

  1. It looks for cells that have only one possible value. That must then be the value for that cell.
  2. It looks in a row for the only place that can take a certain value. That value must then go in that cell. (this is repeated for columns, and squares)
  3. Looks for sets of two possibles in a row and removes those from being possible in the rest of the row (this is repeated for columns)
  4. 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. ex. "156", "15", "156" would be a match and remove 1, 5, & 6 from the other possibles on that row. (repeated for columns)

As long as it has found some new numbers to fill in, then calls itself recursively and repeats the process.
This will solve almost all Sudoku puzzles. For those that do not complete, you must use brute force mode.

Brute Force Mode

In brute force mode the program will look for the cell that has the least number of possibles.

It takes the first possible, tries to solve the puzzle. If it fails it will roll back and try the next possible number. It will repeat ths until it solves the puzzle or determines that the puzzle is unsolvable.

It currently has a limit of 500 recursions so that it runs quickly. It could be allowed to recurse every number of every cell which would solve every solvable Sudoku, but it would take quite a while. And remember that the purpose of this program is to use smart solving.

Enter a puzzle

You are presented with a blank sudoku grid. You can enter your own puzzle, or click on one of the three buttons to quickly fill with a solvable puzzle. The first two puzzles come from Will Shortz's Sudoku, February 2016, puzzle number 196 and 197 (if you love Sudoku, I recommend this book).

The third puzzle is a very difficult one that must use brute force to solve it.

If you want to see the code's layout, click here.

If you want to see the source code, click here.

 

Sudoku Solver

Navigation Lights

Code Samples

Navigation Lights Quiz

This quiz will help you study your ship navigation lights.

This is version 1, and does not record your score.

You will be presented with a randow ship light pattern, seen from either the bow, port or starboard (currently I need to make a change before I can show the stern view).

You will then be given 6 possible choices. If you answer incorrectly it will show you the correct description of the pattern chosen, plus show you the correct answer for the pattern shown.

Navigation Lights