(untagged)

Another Sudoku Solver and Generator

Pascal Ganaye

0.00/5 (No votes)

9 Dec 2005

A program to help you to solve Sudoku problems or check if a Sudoku problem has only one solution.

Sample Image - sudoku2.png

Introduction

Yet another sudoku solver and generator, the first one in code project in VB though.
It searches all the solutions for a given Sudoku problem on the fly.
The interface is simple; the search is continuous and quite fast.
It is therefore useful if you want to generate your own problems.

Sudoku

Large part of this article is extracted from : http://en.wikipedia.org/wiki/Sudoku.
Please refer to it for more details on Sudoku.

From Wikipedia, the free encyclopedia.

Sudoku

Solving the puzzle

The program is using a technique called apparently 'backtracking search' according to Wikipedia.

This means it assign a value (say, 1, or the nearest available number to 1) to the first cell (say, the top left hand corner) and then moves on to assign the next available value (say, 2) to the next available cell. This continues until a conflict occurs, in which case the next alternative value is used for the last cell changed. If a cell cannot be filled, the program backs up one level (from that cell) and tries the next value at the higher level (hence the name backtracking).

This method is very simple and it solves most problems in less than a minute.

Speed improvement 1

To improve the speed the program also keep track of values played for each row, column and and 3x3 box.
Three arrays are used, horz(), vert() and box().
horz(0) indicates which cells are already entered in the first horizontal line
horz(1) indicates which cells are already entered in the second horizontal line...

To know what values can be played in the cell in the line 3 and column 2, the program must check horz(3), vert(2) and box(0).

Also each value is encoded using a 9 bits binary mask

a sudoku value of 1 is encoded with a 1
a sudoku value of 2 is encoded with a 2
a sudoku value of 3 is encoded with a 4
a sudoku value of 4 is encoded with a 8
...
a sudoku value of 9 is encoded with a 256

The binary format is very convenient; in order to check which value as been played in line 3 column 2, the program can do:
dim played as integer played = horz(3) or vert(2) or box(0)

Speed improvement

The second best improvement is fairly straight forward.
This problem like most game solver, can be seen as a tree parsing program.
And again like most problem of this type, it is always better to start with the maximum constraint first.
So rather than trying to play the first cell in the top left corner; the program find which cell has the less number of value fitting and play this one first.
' try to find the cell with the most constraints For i As Integer = 0 To 81 - 1 curCell = CellsArray(i) With curcell If .played = False Then If .forcedVal > 0 Then ' found a very good one bestCell = curCell Exit For Else ' try to calculate the constraints for curCell Dim pos As Integer = horz(.y) Or vert(.x) Or box(.box) curCellConstraint = nbBits(pos) If curCellConstraint > constraintMax Then bestCell = curCell constraintMax = curCellConstraint If constraintMax = 9 Then Exit For End If End If End If End With Next

Generating puzzles

When creating a Sudoku you must keep in mind that there can be only one solution for it, otherwise it is not considered a real Sudoku. Just enter values in the demo program until it displays a number of solution = 1.

Conclusion

Sudoku is not the most complicated or interesting problem to solve with a computer.

If you want a more complicated problem look at my Mac Mahon article I posted earlier this year.

If you know of any puzzle or problem that you think would be interesting to solve, please write to me or in the forum below.

I hope some people will find this program interesting. I try to make it easy to use, your comments are welcome.

History

9th december 2005 - First submission

(Japanese: 数独, sūdoku), sometimes spelled Su Doku, is a logic-based placement puzzle, also known as Number Place in the United States. The aim of the canonical puzzle is to enter a numerical digit from 1 through 9 in each cell of a 9×9 grid made up of 3×3 subgrids (called "regions"), starting with various digits given in some cells (the "givens"). Each row, column, and region must contain only one instance of each numeral. Completing the puzzle requires patience and logical ability. Although first published in 1979, Sudoku initially caught on in Japan in 1986 and attained international popularity in 2005.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here