BSL Dictionary - Search and compare thousands of words and phrases in British Sign Language (BSL). The largest collection of sign videos online.

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 calculate 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)

			
<?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) == 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($square01);
                            
$grid_reference_column=substr($square, -11);
                            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.


7 Comments

Where do I fine hints as to how to do the puzzle.
I start by looking for pairs but what is next?
Comment 1 by bob. Made on the 02nd Aug 2005.
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 2 by Leonardo Bitran. Made on the 12th Dec 2005.
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 3 by Mark Bowen. Made on the 22nd Dec 2005.
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 4 by xorban. Made on the 23rd Jan 2006.
This one was fun. Very easy compared to the sarmuai star earlier. I think I may be getting the hang of seeing the chains and looking for the odd/even crossover.You know that when you shift back to 1-away consecutive sudoku it is going to mess us all up again. Now to get some work done before I start on that jigsaw sarmuai
Comment 5 by Mareike. Made on the 27th Sep 2012.
wow
Comment 6 by Michele Zampiccoli. Made on the 15th Oct 2012.
Hi, do you mind to send me a full php + html coding?

Comment 7 by XY. Made on the 10th Oct 2013.

Leave a Comment on this Page

Sorry, Commenting is now disabled