SuDoku Solver and Generator

• Download source files - 92.02 KB
• Download demo project - 44.26 KB

Introduction

Well, SuDoku is not a new game and many softwares are already available on the net for playing SuDoku. I tried my hand at developing SuDoku one year ago and after a long time, am 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 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 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. Generate 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 remaining 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 on 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 a unique solution, generate other child otherwise kill the node (replace the number in its original position) and remove the 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 constants which can be changed and the program can be extended for larger values of n.

The algorithm for generating the problem has been divided into two parts, one for generating the complete grid and the 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 so simple that you can easily understand it after looking at the code. I have taken the help of this article (Sudoku smart client) for developing the GUI.

Finally

Don't forget to grade this article if you like it. I love it. :)..........