Press 'New' to choose a new puzzle from the database. Press 'Clear' if you want to erase the board and enter values from another puzzle. Press 'Solve' to figure out the puzzle and fill in the remaining squares.

#!/usr/bin/perl -w
use strict;

our $move_ctr;

# +-----------------------------------------------------------+
# | M A I N program.                                          |
# |                                                           |
# +-----------------------------------------------------------+

my $board;
my $solution;
my $guesses;
my $answer;
my $state;


print_time("Start time");
    
# Gather new board from STDIN

$board = $ARGV[0];

$answer = $board;
$move_ctr = 0;

($solution,$guesses,$state) = solve($answer,0,0);
if ($state == 0) {
    die("Could not solve the board!\n");
}
    
print "Solved after $guesses guesses and $move_ctr moves:\n\n";
print_board("Before",$board);
print_board("After",$solution);

print_time("Stop time");

# +-------------------------------------------------------------+
# | Subroutine solve                                            |
# |                                                             |
# +-------------------------------------------------------------+
sub solve
{
    my $board     = $_[0];
    my $level     = $_[1];
    my $guess_ctr = $_[2];
    my $nextrow;
    my $nextcol;
    my $score;
    my @legal;
    my $nlegal;
    my $val;
    my $i;
    my $c;
    my $newstr;
    my $solution;
    my $guesses;
    my $state;
    
    ($score, $nextrow, $nextcol, @legal) = score_board($board);
    
    if ($score == 0) {
        return($board,$guess_ctr,0);
    }
    
    # If $score is still 10, then all of the spaces are filled!
    # This should be a winning board. "state" returned is 1.
    
    if ($score == 10) {
        return($board,$guess_ctr,1);
    }
    
    # Otherwise, we take our best alternative and push ahead ...
    $nlegal = @legal;
    
    $move_ctr++;
    
    # If we have a cell with only one valid response, fill it in
    # and go on ...

    if ($nlegal == 1) {

        $val = $legal[0];
        substr($board,($nextrow * 9) + $nextcol,1) = $val;
        
        return(solve($board,$level + 1,$guess_ctr));
    }
    
    # Otherwise, we will try a set of alternatives until we find
    # success (or  run out of alternatives!)
    
    $guess_ctr++;
    
    # The following is an optional diagnostic for looking at
    # recursion depth.

    print STDERR "Guess $guess_ctr, checking $nlegal possibilities.\n";
    
    for ($i = 0;$i < $nlegal;$i++) {
        
     $val = $legal[$i];
     substr($board,($nextrow * 9) + $nextcol,1) = $val;
        
     ($solution,$guesses,$state) = solve($board,$level + 1,$guess_ctr);
        
     # See if that path led to a solution
     if ($state == 1) {
         return($solution,$guesses,$state);
     }
    }
    
    # We only get here if all of our alternatives failed.  Return
    # the last failure.

    return($solution,$guesses,$state);
}

# +-------------------------------------------------------------+
# | Subroutine score_board                                      |
# |                                                             |
# +-------------------------------------------------------------+
sub score_board
{
    my $str = $_[0];
    my @board;
    my @scores;
    my $i;
    my $j;
    my $cell;
    my @legal;
    my $nlegal;
    my $lowscore = 10;
    my $lowi     =  0;
    my $lowj     =  0;
    my @lowlegal = ();
    
    # The @scores array is a 9x9 grid representing the board $str.
    
    # If a cell has an @scores value of -1, then it already has an
    # assigned value on @board.
    
    # Otherwise the cell value is the number of unused numbers that
    # could be assigned at that row and column.  If this value is
    # zero (0), then we are at a dead-end.  Otherwise, we want to 
    # return the row and column of the cell with the lowest number
    # of alternatives, and the list of those alternatives, to try
    # in order.
    
    for ($i = 0;$i < 9;$i++) {
        for ($j = 0;$j < 9;$j++) {
            $board[$i][$j] = substr($str,($i * 9) + $j,1);
        }
    }
    
    for ($i = 0;$i < 9;$i++) {
        for ($j = 0;$j < 9;$j++) {
            
            $cell = $board[$i][$j];
            if ($cell != 0) {
                $scores[$i][$j] = -1;
                next;
            }
            
            @legal  = legal_values($str,$i,$j);
            $nlegal = @legal;
            
            $scores[$i][$j] = $nlegal;
            if ($nlegal < $lowscore) {
                $lowscore = $nlegal;
                $lowi     = $i;
                $lowj     = $j;
                
                @lowlegal = @legal;
            }
        }
    }
    
    return ($lowscore, $lowi, $lowj, @lowlegal);

}

$str          = "000004050000003700208006000540000000100000003";
$str         .= "000000028000200106003700000070500000";
$original     = $str;
$nctr         = 0;       // Counts steps in solution
$solution_ctr = 0;       // Counts number of solutions found
$solutions    = Array(); // Array of solutions found.

function score_board($str) {
    
    global $nctr;
    
    $lowscore = 10;
    $lowi     =  0;
    $lowj     =  0;
    $lowalts  = "0123456789";
    
    $nctr++;
    
    # The $scores array is the same 9x9 grid as the $board array.  If
    #a cell has an $scores value of -1, then it already has an assigned
    # value on $board.  Otherwise, the cell value is the number of 
    # unused numbers that could be assigned at that row and column.  
    # If this value is zero (0), then we are at a dead-end.  Otherwise,
    # we want to return the row and column of the cell with the lowest
    # number of alternatives, and the list of those alternatives, to
    # try in order.
    
    for ($i = 0;$i < 9;$i++) {
        for ($j = 0;$j < 9;$j++) {
            $board[$i][$j] = substr($str,($i * 9) + $j,1);
        }
    }
    
    // Initialize $alts to allocate some space to it.
    $alts  = "0123456789";
    
    for ($i = 0;$i < 9;$i++) {
        
        for ($j = 0;$j < 9;$j++) {
            
            $cell = $board[$i][$j];
            if ($cell != 0) {
                $scores[$i][$j] = -1;
                continue;
            }
            
            # Prep array to keep track of numbers that can and can't
            # be played in this particular location.  Note that '0'
            # denotes an unused cell ... the numbers 'in play' are 1
            # through 9.
            
            for ($k = 0;$k <= 9;$k++) {
                $ctr[$k] = 0;
            }
            
            
            # Define the row and column of the top left element of
            # the 'local' 3x3 grid.
            
            $localr = $i - ($i % 3);
            $localc = $j - ($j % 3);
            
            # Mark all numbers already used in the 'local' 3x3 grid.
            for ($ii = $localr;$ii < ($localr + 3);$ii++) {
                for ($jj = $localc;$jj < ($localc + 3);$jj++) {
                    $value = $board[$ii][$jj];
                    if ($value != 0) {
                        $ctr[$value] = 1;
                    }
                }
            }
            
            # Mark all numbers already used in the current row.
            for ($jj = 0;$jj < 9;$jj++) {
                $value = $board[$i][$jj];
                if ($value != 0) {
                    $ctr[$value] = 1;
                }
            }
            
            # Mark all numbers already used in the current column.
            for ($ii = 0;$ii < 9;$ii++) {
                $value = $board[$ii][$j];
                if ($value != 0) {
                    $ctr[$value] = 1;
                }
            }
            
            # Now count up possible moves and record the score.  A
            # number is available to play in a current space if there
            # is a zero in its place in the @ctr array.
            #
            # If this is the current Low Score, keep track of it!
            
            $moves = 0;
            for ($k = 1;$k < 10;$k++) {
                if ($ctr[$k] == 0) {
                    $alts[$moves] = $k;
                    $moves++;
                }
            }
            
            $scores[$i][$j] = $moves;
            if ($moves < $lowscore) {
                $lowscore = $moves;
                
                $lowi     = $i;
                
                $lowj     = $j;
                
                
                $lowalts = substr($alts,0,$moves);
                
            }
        }
    }
    
    $results[0] = $lowscore;
    $results[1] = $lowi;
    $results[2] = $lowj;
    $results[3] = substr($lowalts,0,$lowscore);
    
    return $results;
}

function solve_sudoku($str,$level) {
    global $solution_ctr;
    global $solutions;
    global $nctr;
    
    $results = score_board($str);
    
    $score   = $results[0];
    $nextrow = $results[1];
    $nextcol = $results[2];
    $alts    = $results[3];
    
    if ($score == 10) {
        
        $solution_ctr++;
        $solutions[] = $str;
        
        return;
    }
    
    for ($i = 0;$i < $score;$i++) {
        
        $c = substr($alts,$i,1);
        
        $newstr = $str;
        $newstr[($nextrow * 9) + $nextcol] = $c;
        
        solve_sudoku($newstr,$level + 1);
    }
}

function PushSolveButton($request_page,$request_ip) {
    global $nctr;
    global $solution_ctr;
    global $solutions;
    global $original;
    
    $before = gather_board($_POST["grid"]);
    $original = $before;
    
    //      Database stuff removed.  The final application checks a
    //      database of 'known' puzzles to see if has already solved
    //      the board and if so just retrieves and displays the
    //      solution.
    //
    //      Otherwise, assume $ctr resolves to 0 (board not found
    //      in the database, so solve). 'gather_board' is just a
    //      function that gets the data from a grid.  I think the
    //      other functions are pretty clear about what that array
    // looks like!
    
    if ($ctr == 0) { 
        // The board was not found in the database.  Run the solver.
        
        $nctr         = 0;       // Counts steps in solution
        $solution_ctr = 0;       // Counts number of solutions found
        $solutions    = Array(); // Array of solutions found.
        
        solve_sudoku($before,0);
        
        if ($solution_ctr > 0) {
            $after = $solutions[0];
            
            // Check the database, and add this board/solution if it
            // is new.

            update_database($original,$after,$nctr);
            
            showboardform($after,$before);
        }
        else {
            showboardform($before,$before);
        }
    }
    else {
        showboardform($after,$before);
    }
    
}