12,405,895 members (72,661 online)
alternative version

65.8K views
47 bookmarked
Posted

# SuDoku Solver and Generator

, 1 Oct 2008 CPOL
 Rate this:
Software for playing SuDoku

## 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 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 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.

## Design of the Code

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.

## Share

 Software Developer India
No Biography provided

## You may also be interested in...

 First Prev Next
 My vote of 5 Member 374801219-Apr-11 23:14 Member 3748012 19-Apr-11 23:14
 Will it generate a puzzle with unique solution always Divya Kulkarni2-May-10 15:31 Divya Kulkarni 2-May-10 15:31
 Re: Will it generate a puzzle with unique solution always Abhishek _Agarwal13-Aug-10 21:37 Abhishek _Agarwal 13-Aug-10 21:37
 Good work Boby Thomas P1-May-09 19:47 Boby Thomas P 1-May-09 19:47
 Re: Good work Abhishek _Agarwal3-May-09 15:55 Abhishek _Agarwal 3-May-09 15:55
 Compile error Mikeanical9-Oct-06 6:56 Mikeanical 9-Oct-06 6:56
 Re: Compile error Abhishek _Agarwal11-Oct-06 19:15 Abhishek _Agarwal 11-Oct-06 19:15
 Re: Compile error Abhishek _Agarwal12-Oct-06 20:51 Abhishek _Agarwal 12-Oct-06 20:51
 Save puzzle does not return ReorX25-Aug-06 1:58 ReorX 25-Aug-06 1:58
 Re: Save puzzle does not return Abhishek _Agarwal25-Aug-06 23:13 Abhishek _Agarwal 25-Aug-06 23:13
 Last Visit: 31-Dec-99 18:00     Last Update: 29-Jul-16 16:45 Refresh 1