Sudoku - How the Puzzle Solver was Made

What is Sudoku?

Sudoku is a Number Puzzle that requires no mathematical knowledge. (no adding or multiplication). It is based upon Japanese style crosswords where you are required to use logic to place numbers onto a 9x9 grid.

Rules

To solve the puzzle you must make sure that every column, row and 3x3 box contains the numbers 1 through to 9.
Almost all of the puzzles can be solved using logic alone and there is no need to guess. A puzzle can take from 20 minutes to 2 hours to complete depending on its level and your experience.
People have developed a range of methods and tactics in order to solve the puzzles.

How the Sudoku Puzzle Solver Works

There are literally hundreds of puzzle solvers on the web. The methods for completing this task is numerous. Some use JavaScript, VB, C++ and many many more. Some of the puzzle solvers use only logic and other use brute force to test every single combination.

On this site I use a server side scripting language called PHP to calcualte the answer from the numbers submitted by the user. It works by performing the following steps: First it checks each blank square indivdually. It knows that each square can only contain the numbers 1 to 9. It will check in the column and row of the square and thus reduce the number of possibilities that the square could be. It reduces the possibilities further by checking what numbers are in the same larger square as the square and thus remove more possibilities. If at the end of this there is only one possibility left then the value of that square has been found. This step is repeated for each square. Once it has gone round all the squares it will go around again and again as more squares has been filled in it will mean that it will help solve other squares. The solver will also check each larger square for any numbers where it can only go in one place as this will also lead to another answer.

Although my puzzle solver can solve many sudoku puzzles it can not solve them all. This is because my puzzle will only use logic to solve puzzles. I have not programmed it to make 'guesses' for when it is impossible to use logic.

I started this project after a suggestion by my 'Old Man' and also my Sudoku crazed family who complete at least 3 or 4 puzzles a day. I orignally started with the 6x6 Sudoku to try and understand the best ways of developing the puzzle. Much inspiration came from other websites that I visited where people stated tactics and techniques of solving puzzles. I have simply turned them into programming logic so that a computer can solve the puzzles.

Below I have included some code snippets of the PHP code used to make the Puzzle Solver 9x9. (The 6x6 puzzle solver uses almost identical code as is not shown here)

Search the Web for more on Sudoku

Sudoku Books

Please support this site by clicking this link to keep this site in the top 50 Sudoku sites.


<?PHP
$allowed_numbers = array(1,2,3,4,5,6,7,8,9);
$allowed_letters = array('a','b','c','d','e','f','g','h','i');
$submitted_numbers = array();

$box1 = array('a1','a2','a3','b1','b2','b3','c1','c2','c3');
$box2 = array('a4','a5','a6','b4','b5','b6','c4','c5','c6');
$box3 = array('a7','a8','a9','b7','b8','b9','c7','c8','c9');

$box4 = array('d1','d2','d3','e1','e2','e3','f1','f2','f3');
$box5 = array('d4','d5','d6','e4','e5','e6','f4','f5','f6');
$box6 = array('d7','d8','d9','e7','e8','e9','f7','f8','f9');

$box7 = array('g1','g2','g3','h1','h2','h3','i1','i2','i3');
$box8 = array('g4','g5','g6','h4','h5','h6','i4','i5','i6');
$box9 = array('g7','g8','g9','h7','h8','h9','i7','i8','i9');
?>

This section above simply describes the model of the Sudoku Puzzle. It defines that the puzzle only has the numbers 1 to 9. It also describes the grid as being 1 - 9 accross with a - i down. Lastly it defines the larger squares and what squares make up that larger square.


<?PHP
function allowed_column($allowed_numbers,$grid_reference_row,$number){
    $checking=0;
    foreach($allowed_numbers as $column) { // Find values in the same row
        $grid_reference2="$grid_reference_row$column";
        global ${$grid_reference2};
        if(${$grid_reference2}==$number){
            $checking=1;                        
        }
    }
    if($checking==1){
        return FALSE;
    }
    return TRUE;
}

function allowed_row($allowed_letters,$grid_reference_column,$number){
    $checking=0;
    foreach($allowed_letters as $row) { // Find values in the same column
        $grid_reference2="$row$grid_reference_column";
        global ${$grid_reference2};
        if(${$grid_reference2}==$number){
            $checking=1;                        
        }
    }
    if($checking==1){
        return FALSE;
    }
    return TRUE;
}
?>

The section above defines a couple of functions that will be used later in this script in order to find out if there are any squares in each larger square where there is only one place a particular number can go.


<?PHP
foreach($_POST as $varName => $value)
{
    ${$varName}=$value;
    if(!empty($value)) {
        if(count($value) == 1 AND is_numeric($value)) {
            array_push($submitted_numbers, "$varName");
            if(!in_array($value, $allowed_numbers)){
            echo "Invalid Number!";
            }
        }
    }
}
?>

The section above simply gets the input from the user so that the script knows which numbers it has been given. These numbers are certain and will never change. These numbers are placed in the virtual grid that the computer uses to find and deduce the other numbers.


<?PHP
$times=1;
$finished=FALSE;
while ($finished == FALSE) {
    $finished=TRUE;
?>

The while loop is used to repeat the cycle of steps needed to find the answers continually until a cycle finds no more answers which would mean that either the puzzle is complete and thus no more answers left or the cycle is unable to find all the answers for the puzzle using logic allone.


<?PHP
    foreach($allowed_letters as $grid_reference_row) {
        foreach($allowed_numbers as $grid_reference_column) {
            $grid_reference="$grid_reference_row$grid_reference_column";

            if(${$grid_reference} =='') {
                // Unknown Digit
                $possibilities = array(1,2,3,4,5,6,7,8,9);

                    foreach($allowed_numbers as $column) { // Find values in the same row
                        $grid_reference2="$grid_reference_row$column";
                        if($grid_reference2<>$grid_reference) {
                        
                            if(${$grid_reference2}<>''){
                                $remove=${$grid_reference2}-1;
                                unset ($possibilities[$remove]);

                            }
                        }
                    }
?>

The above section calculates each other square that is on the same row as the square we are testing. For each square on the same row it checks to see if it has a value. If it does the value can be removed from the possibilities for the square.


<?PHP
                    foreach($allowed_letters as $row) { // find values in the same column
                        $grid_reference2="$row$grid_reference_column";
                        if($grid_reference2<>$grid_reference) {
                        
                            if(${$grid_reference2}<>''){
                                $remove=${$grid_reference2}-1;
                                unset ($possibilities[$remove]);
                            }
                        }
                    }
?>

The above section continues the testing on the square. Except it checks each square on the same coulumn to see if it has a value. If it does the value can also be removed from the possibilities for the square.


<?PHP
                    $i = 1;
                    while ($i <= 9) {
                        $box_check="box$i";
                        if(in_array($grid_reference,${$box_check})) {
                            $box = "$box_check";
                        }
                        $i++;
                    }
                    foreach (${$box} as $square) {
                        $grid_reference2 = "$square";
                        if($grid_reference2<>$grid_reference) {
                            if(${$grid_reference2}<>''){
                                $remove=${$grid_reference2}-1;
                                unset ($possibilities[$remove]);
                            }
                        }
                    }
?>

The above section continues the testing on the square. Except it checks each square in the same larger square to see if they have a value. If they do have a value then that number can also be removed from the possibilities for the square.


<?PHP
                    $i=0;
                    foreach ($possibilities as $answer) {
                        $i++;
                    }

                    if($i==1) {
                        //One Correct Answer
                        ${$grid_reference}="$answer";
                        $finished=FALSE;
                    } elseif($i==0) {
                        echo "An error has occured! The puzzle may be unsoveable or you have entered the numbers incoccrectly.";
                        $finished=TRUE;
                    }
?>

The number of possibilities for the square is counted. If it equals 1 then a correct solution has been found for that square. If it equals zero then an error has occured as the numbers have been entered in incorrectly by the user and thus the puzzle has no legal solution.


<?PHP
                }
            }
        }
        $i = 1; // The Square
        while ($i <= 9) {
            $box_check="box$i";
            $number = 1; // Searching Number
            while ($number <= 9) {        
                $count=0; // Occurence of number
                foreach (${$box_check} as $square) {
                    if(${$square}==$number){    
                        $count=50;
                    } else {
                        if(${$square}==''){            
                            $grid_reference_row=substr($square, 0, 1);
                            $grid_reference_column=substr($square, -1, 1);
                            if(allowed_column($allowed_numbers,$grid_reference_row,$number)<>FALSE){
                                
                                if(allowed_row($allowed_letters,$grid_reference_column,$number)<>FALSE){
                                    $count++;
                                    $square2=$square;
                                }
                            }            
                        }
                    }
                }
                if($count==1) { //unique number has been identified
                    ${$square2}=$number;
                    $finished=FALSE;
                }
                $number++;
                $count=0;
            }
            $i++;
?>

The above section now checks for numbers in the larger square that can only go in one place as that will also be a solution to the square.


<?PHP
        }
        $times++;
    }
$times=$times-1;
echo "<strong>$times</strong> Cycles made";
?>

Finally the number of times that the program has checked each square is displayed. Along with the actually result below.


<?PHP
$i=1;
foreach($allowed_letters as $row) {
    foreach($allowed_numbers as $column) {
        $coords="$row$column";
        $value=${$coords};
        if(in_array($coords,$submitted_numbers)){
            $value='<strong>' . ${$coords} . '</strong>';
        }
        if($i<10) {
            echo '<td width="20" height="20"><div align="center">' . $value . '&nbsp;</div></td>';
            $i++;
        } else {
            echo '</tr><tr><td width="20" height="20"><div align="center">' . $value . '&nbsp;</div></td>';
            $i=2;
        }
    }
}
?>

The last stage above is to generate the 9x9 grid and display the values with the orignal values given by the user shown in bold.

For those who are interested in the code or more information about it please contact me.

I have also been contacted by Anders Giversen who has created his own sudoku puzzle solver. This can be found here along with the source code for those PHP programmers who are interested. Thanks again to Anders Giversen who took the time to contact me.

6 Comments

1)	Where do I fine hints as to how to do the puzzle. I start by looking for pairs but what is next? Comment by: bob. Made on the 02nd Aug 2005.

2)	Congratulations for your superb site. I would like to know how many different arrangements of sudokus 9x9 could be constructed. -Is it possible to calculate this mathematically ? Comment by: Leonardo Bitran. Made on the 12th Dec 2005.

3)	Just thought you might like to know that with a 9 X 9 grid there are 6,670,903,752,021,072,936,960 arrangements. Could take a while to see them all I think?!! :) Best wishes & Merry Christmas everyone. Mark Comment by: Mark Bowen. Made on the 22nd Dec 2005.

4)	exuse me. can you send me on my mail box, a script php and html of solver 9*9 ? becease it's dificul for me to creat it whith your php page web Comment by: xorban. Made on the 23rd Jan 2006.

Equally interesting to how to solve a puzzle is the whole set of questions about what rules are used to *create* a solvable puzzle with a unique solution. Do each of the digits 1-9 need to be represented at least once? Can any "quadrant" be completely empty? What is the minimum number of entries necessary and still have a unique solveable problem specified? How would you prove it? How would you approach writing a program to generate the puzzles?
Probably explored on some related sites these days. Good computability theory stuff...

Comment by: Scott Ritchie. Made on the 14th Feb 2006.

6)	hi ,im currently studying a c++ languauge,im looking for a complete code for sudoku to link on how i must generate the randomn numbers Comment by: mpho. Made on the 30th Apr 2006.

Please Help Support this site by making a Donation.

Sudoku - 9x9, 6x6 and Killer Samurai Sudoku

What is Sudoku?

Rules

How the Sudoku Puzzle Solver Works

Search the Web for more on Sudoku

6 Comments

Leave a Comment on this Page