SuDoku Solver and Generator

• Download source files - 379 Kb
• Download demo project - 50 Kb

Introduction

Well, SuDoku is not a new game and many software are already available on net for playing SuDoku. I tried my hand at devloping SuDoku one year before and after a long time sharing it with everyone.

Principle of Uniqueness

You must be knowing the rules of SuDoku. Let me put the rule into a precise definition which I will help you to understand the code :
In SuDoku There is a square grid with p⁴ squares where generally p=3.The larger square grid has p²xp² dimensions. Each larger square grid has p² boxes of pxp dimensions. The Larger grid is partially filled. The rule is that fill in the grid so that every horizontal row, every vertical column and every pxp box contains the digits from 1 to n (n=p²), without repeating the numbers in the same row, column or box. I have named this rule as the principle of uniqueness.

Design of the code

The design includes basically three parts

1.Solve the problem
2.Genearte the problem
3.Graphics (An important part to make the interface attractive)

Solving Algorithm

The simplest method of solving SuDoku is to mark all the possible values (1- n) a square can have. Then on the basis of ‘principle of uniqueness’ discard the numbers that cannot be filled in that square. When a square is remained with only one number or a number is such that it cannot be in other squares of the row or column or box corresponding to the square, fill the number and remove the possibility of the number from squares of the row, column and box belonging to the recently filled square. Proceeding in this manner a unique number can be found for all squares.

The algorithm implemented just follows the procedure described above. In the symbolic form the algorithm can be stated as

Mark all candidate numbers


Cansolve=true; 



While 
(not all squares are filled and cansolve=true ) {


Cansolve=false;


  For(each row in rows)


  For(each col in columns) {


   If (only one candidate number){ 


    Fill the square with the candidate number;


    Cansolve=true;


    Update candidate numbers of all squares in that row, column and box}


   Else if (a number exists which is not illegible for any other square in that row,
        column and box) {


   
      Fill the square with the candidate number;


        
Cansolve=true; 


}//end 

for loops


}//end 

while loop

Problem Generating Algorithm

The most difficult aspect of SuDoku is how to generate a problem which has a unique solution. I applied an algorithm based upon Branch and Bound technique:

In this algorithm we follow a two step procedure to generate the problem grid. In the first step we fill the grid completely at random under constraints. This means while filling a square mind the principle of uniqueness. After the first step is completed remove the numbers one by one at random. If after removing a number the problem is having unique solution generate other child otherwise kill the node (replace the number in its original position) and remove other number. In this way a problem grid can be originated. The advantage of this method is that it will not be trapped inside an infinite loop and a solution will definitely be generated.

Now we will explore the Branch and Bound approach in detail. Generally Su-Doku is played with a value of n=9 (p=3). The program has considered the development for the standard value of n=9 but it has a flexible interface defining all the constant which can be changed and the program can be extended for larger values of n.

The algorithm for generating problem has been divided into two parts, one for generating the complete grid and second for the problem grid.

//algorithm createCompleteGrid ()



Initialize the empty grid


global freecols, filledPoints   


// freecols is the collection list of free columns in a particular column



//filledPoints is the collection list of filled squares in a row  


for (count=1 to n) {


 clear filledPoints;


 for (row=1 to n) {


  Initialize filledPoints with values 1-n


  bool repeat=true;


    while (repeat) {


     repeat=false;


     if freecols is empty


     than remove the other squares filled with the count and start from row= 0 


     else{ 


      select a column=col from freecols at random


      if (grid[row,col]!=empty or count already exists in corresponding row,col or box){


     remove (row,col) from freecols 


          continue;}


     }//else ends



    }//while ends



    if (repeat) continue;


     grid[row,col]=count;


  <span style="font-size: 10.0pt; line-height: 150%; font-family: Verdana">   add (
        row,col) to filledPoints


  }} //endfor loops 



   

The algorithm shown here is self explanatory. But in the given algorithm the program goes in an infinite loop or takes more time when rows are traversed in continuous order 1,2,3,4………, an intuitive explanation of the fact could be that the program is based on random selection of numbers, the random number algorithms are more successful when random numbers are well distributed over the solution set. When rows are incremented by one, all numbers are filled in starting rows (say 1, 2, 3, 4, and 5) and there is a possibility that no valid numbers are remaining for remaining rows. But if these five rows would have been 1, 3, 5, 7 and 9 there is a bigger domain for a random function to select for rows 2,4,6,8. Thus in the code the rows have been traversed in order 1, 3, 5,7,9,2,4,6,8.

// algorithm creatProblemGrid()



// k is the no of squares to be removed 



List points //a collection list of size n2 containing coordinates of the squares that



//can be removed



for (count = 0 to k) {


 if points is empty 


   return false;


 select a square at random and remove the number


 find the solution with the solving algorithm 


 if (!solution exists and unique) {


 count--;


 replace the removed number;


 remove the square from points


 continue;


 }


remove the square from points


}


return true; 

Graphics

The GUI interface of this program is very simple that you can easily understand after looking at the code. I have taken help of this article (Sudoku smart client) for developing GUI .

Finally

Dont forget to grade this article if you like it. I love it :)..........