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 p4 squares where generally p=3.The larger square grid has p2xp2 dimensions. Each larger square grid has p2 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=p2), without repeating the numbers in the same row, column or box. I have named this rule as the principle of uniqueness.
1.Solve the problem
2.Genearte the problem
3.Graphics (An important part to make the interface attractive)
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
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 loopsThe 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;
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 .
Dont forget to grade this article if you like it. I love it :)..........
| You must Sign In to use this message board. | ||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||
