| fax
| | Joined: 07 Aug 2005 | | Posts: 1 | | : | |
Items |
|
 Posted: Sun Aug 07, 2005 5:08 am Post subject: SDKSolve - Sudoku Solver for Win9x (Win98, WinXP) |
 |
|
Hi All
Great forum! I learned a thing or two about sudoku patterns by reading this forum  which I've incorporated in to my program - see section on solve methods, particularly the solve methods SR, SS, ST, SU, SV...
It can be dowloaded from
http://afax.fly.to/sudoku
Let me know what you think...
Here's a description:
| Code: |
-----------------------------------------------------------
SDKSolve is a "trainer" for sudoku, whereby the program tries to solve the sudoku by logic only (subjective definition!) - although a brute force method is also included, which can find all the valid solutions for a grid (if there is more than one solution).
SDKSolve is a sudoku "learning tool", or "suggest a move".
The solve methods have been constructed (I believe) in a way that is more amicable for human solvers (while keeping in mind that sudoku is an NP-complete problem).
-----------------------------------------------------------
Usage:
To load a grid, go to File->Load Grid, and choose a text file containing the grid information.
The text file containing the grid information should have the following structure:
The first line should indicate the dimension of the grid (e.g. put in 9 for the normal sudoku grid).
The second line should indicate the starting value of the numbers.
The ordering of the number is as follows:
0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ
E.g. if the dimension is 9, and the starting value is 1, then it is expected the numbers are:
123456789
For blank, use a dot --> .
Characters like tab, end of line, -, |, +, space, are ignored. So the following are all valid:
. 3 . . . 1 . . .
. . 6 . . . . 5 .
5 . . . . . 9 8 3
. 8 . . . 6 3 . 2
. . . . 5 . . . .
9 . 3 8 . . . 6 .
7 1 4 . . . . . 9
3 2 . . . . 8 . .
. . . 4 . . . 3 .
.3...1...
..6....5.
5.....983
.8...63.2
....5....
9.38...6.
714.....9
32....8..
...4...3.
.3.|..1|...
..6|...|.5.
5..|...|983
---+---+---
.8.|..6|3.2
...|.5.|...
9.3|8..|.6.
---+---+---
714|...|..9
32.|...|8..
...|4..|.3.
.3...1...|..6....5.|5.....983|.8...63.2|....5....|9.38...6.|714.....9|32....8..|...4...3.
For examples of grid files, see s1.txt and s2.txt
-----------------------------------------------------------
To start solving the grid, choose Simulation->Start (or use the project toolbar).
To pause, choose Simulation->Pause (or use the project toolbar).
To stop, choose Simulation->Stop (or use the project toolbar).
To step through the solve procedure one by one, choose Simulation->Step (or use the project toolbar); to go to the next solve, choose Simulation->Step again.
To fast step, choose Simulation->Fast Step (or use the project toolbar). The Fast Step is similar to the Step above, except it fast forward all the Solve 0 (S0) procedures (all the solve methods are discussed below).
At anytime, to see the work grid, choose View->Grid (or use the project toolbar).
To see the solution grid, choose View->Solution Grid (or use the project toolbar).
To see another type of view for the grid, choose View->Grid Type 2 (or use the project toolbar).
In View Grid Type 2:
- To fit the grid display to page, choose View->Fit to Page.
- To zoom in or out, choose View->Zoom. To zoom in use the left mouse button; to zoom out use the right mouse button.
To view the log of all the steps taken, choose View->Event Log (or use the main toolbar).
To see another type of view of the log, choose View->Event Log Type 2 (or use the main toolbar).
In View Event Log Type 2:
- To fit the grid display to page, choose View->Fit to Page.
- To zoom in or out, choose View->Zoom. To zoom in use the left mouse button; to zoom out use the right mouse button.
After any of the Start, Step, or Fast Step, the work grid and/or solution grid may be changed. To restore it to the original grid (when it was first loaded), choose Edit->Reset Grid.
To change the order a solve method is run (or not at all), choose Project->Settings
E.g. if put in 21345, then solve method 2 is run first, then solve method 1, then 3, then 4, then 5
if put in 2145, then solve method 3 will not be executed.
For solve method Z (brute force method), the maximum number of solutions to be searched can be changed from Project->Settings. See the description on solve method Z below.
Other settings for the project are available in Project->Settings.
-----------------------------------------------------------
The grid numbering:
The row and column numbering is as follows:
1 2 3 4 5 6 7 8 9
|-----------------------------------
1| . 3 . | . . 1 | . . .
2| . . 6 | . . . | . 5 .
3| 5 . . | . . . | 9 8 3
|-----------------------------------
4| . 8 . | . . 6 | 3 . 2
5| . . . | . 5 . | . . .
6| 9 . 3 | 8 . . | . 6 .
|-----------------------------------
7| 7 1 4 | . . . | . . 9
8| . 2 . | . . . | 8 . .
9| . . . | 4 . . | . 3 .
E.g. in the above, cell (1,2) contains 3,
and cell (2,3) contains 6.
Similarly, for a grid of dimension 16:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
|----------------------------------------------------------
1| F B . 6 | C . 7 8 | 1 D . . | 4 A . 0
2| . 4 . . | . 2 . . | . . . . | . . 8 .
3| . . . . | . 9 1 . | . A . . | . . . .
4| . . D C | 5 4 6 B | 8 3 2 . | F . . .
|----------------------------------------------------------
5| 9 A B . | 2 . . . | 3 C 5 8 | E . . .
6| . E 8 D | 6 A . . | 7 1 . 4 | 3 5 . .
7| . . 3 . | . . 8 C | E 2 . 9 | . . . B
8| . 0 . . | F . 5 . | D B 6 A | 9 8 . .
|----------------------------------------------------------
9| 1 6 . . | . . . 2 | . 0 . E | D F 3 8
10| 2 3 0 . | 7 F 9 6 | . . C D | B E 1 .
11| 5 7 . E | 8 . C D | F . . . | . . 9 A
12| . 9 F A | 3 . 0 E | 5 8 B 2 | C 6 7 .
|----------------------------------------------------------
13| . . . 7 | B . F . | . 5 3 . | 0 . 6 .
14| 3 C 2 . | . . E 5 | B . . . | . 1 . .
15| . . . F | . . . . | 0 . . . | . . . .
16| 0 . A 4 | 9 . . . | 2 E 8 F | . . B D
The block numbering is as follows:
1 2 3 4 5 6 7 8 9
|-----------------------------------
1| | |
2| 1 | 2 | 3
3| | |
|-----------------------------------
4| | |
5| 4 | 5 | 6
6| | |
|-----------------------------------
7| | |
8| 7 | 8 | 9
9| | |
So the top-left hand block is block 1, the middle block is block 5, and so on.
Similar numbering exists for grid of dimension 16 and higher.
-----------------------------------------------------------
The solve methods:
S0: solve method 0 is the simple solve method.
E.g. if have a 3 on cell (1,2), then remove (from the solution grid) the value 3 from
row 1, column 2, and block 1 (cell (1,2) is in block 1).
S1 and S3: Number pattern
If we have on a row from a solution grid of dimension 9:
12 12 (pattern of two)
123 123 123 (pattern of three)
12 23 13 (pattern of three)
1234 1234 1234 1234 (pattern of four)
And so on, then we can eliminate the numbers from other cells in the row.
We can also have (where the value 123 exist only on these three cells):
123 123 1237 (pattern of three)
12 13 237 (pattern of three)
12 137 237 (pattern of three)
And so on, then we can eliminate the 7 from the third cell above.
While the examples above show pattern of two and more, we can also have the trivial pattern of one number. This trivial case is set as solve 1 (S1). The rest is set as solve 3 (S3). S3 will find the two cases above interchangeably. S1 is described in more details below.
S1: Look at a row and see if a number occurs only once in the row. That cell must contain that number. Repeat for column and block.
E.g. One row from a solution grid of dimension 9:
1 3 5 789 789 789 26 4 28
Cell (x, 7) must contain 6
S2: intersection of row and block, column and block, block and row, block and column.
If we have the number 5 occurring as follows (for intersection of row and block):
x 5x 5xx x x x x x x (row 1)
5x x x (row 2)
x 5x x (row 3)
Then the value 5 must occur in row 1, so can remove the other 5 from the block (in row 2 and row 3).
The same idea is applied to intersection of column and block, block and row, block and column.
S3: see above.
S4: common intersection of:
- n rows and n columns
- n rows and n blocks
- n columns and n rows
- n columns and n blocks
- n blocks and n rows
- n blocks and n columns
where n is >= 2
If we have the following (as an example for common intersection of two rows and two columns):
x x x x 2x x x 2x x
x x x x x x x x x
x x x x 2x x x 2x x
x x x x 2x x x x x
x x x x x x x 2x x
x x x x x x x x x
x x x x 2x x x 2x x
x x x x x x x x x
x x x x x x x x x
Then the value 2 must lie in either cell (1,5)(7,8) or (1,8)(7,5). The value 2 can therefore be eliminated from other cells in column 5 and column 8.
The same idea is applied to the other intersections.
S5: number pairs forming closed chain:
If we have the following:
x x x x 17 x x 57 x
x x x x x x x x x
x x x x x x x x x
x x x x 27 x x 25 x
x x x x x x x x x
x x x x x x x x x
x x x x x x x x x
x x x x x x x x x
x x x x x x x x x
Then we have the following closed chain:
17-72-25-57->71 (back to original cell with 71).
Cell (1,5) is therefore 1.
The number pair is connected through either row, column, or block association.
The chain can be much larger than four.
How do you spot such a chain?
To "spot" a suitable starting cell, look for cells that has two neighbours sharing a common value. For example, the two neighbours of cell (1,5) both share a common value 7.
In the above example, consider the two cells with values 72-25
The left number can be considered a 'no' value, and the right number a 'yes' value.
The cell can't have a 7 (no), so it necessarily have to have the value 2 (yes)
The next cell can't have a 2 because of the previous cell, so it has a 5
I'd like to call the link in the two cells above a 'yes' link.
We can also have a 'no' link - described below.
A simple extension/generalization to the above would be to also consider numbers that occur only twice in a row, column, or block.
If we have the following:
x x x x 78 x x x x
x x x x x x x x x
x x x x x x x x x
x x x x 378 x x 179 x
x x x x x x x x x
x x x x x x x x x
x x x x x x x x x
x x x x x x x x x
x x x x x x x x x
Suppose cell (1,5) is in the middle of a chain:
...-87
For clarity, put a comma between the 'no' and 'yes' value:
...-8,7
We can link cell (4,5) with cell (1,5):
...-8,7-7,38
As cell (4,5) can't have a 7, then cell (8,5) must have a 7:
...-8,7-7,38-19,7
So while a 'yes' link results in yes-no common value, e.g. 23-35, common 3
a 'no' link results in a no-yes common value, e.g. 78-57
There are different ways to describe solve method 5, but I believe the above is more amicable for human solvers.
Note: solve 5 may take a while to run, even longer than the brute force search (described below) method SZ - which solves any 3x3 sudoku in almost an instant :)
-----------------------------------------------------------
Other solve methods:
SL: Solve method L is a cut-down version of solve method 5.
In solve method L, only 'yes' link is considered, and only cells with exactly two possible values are considered.
SM: Solve method M is also a cut-down version of solve method 5, but is more powerful than solve method L.
In solve method M, 'yes' and 'no' links are considered, however only cells with exactly two possible values are considered as possible starting cells.
SN (X-Wing): Solve method N is a cut-down version of solve method 4.
In solve method N, only n=2 is considered.
SP: Solve method P is a cut-down version of solve method 3.
In solve method P, only occurrence of the following types are considered:
Suppose we have (where the value 123 exist only on these three cells):
123 123 1237 (pattern of three)
12 13 237 (pattern of three)
12 137 237 (pattern of three)
And so on, then we can eliminate the 7 from the third cell above.
SQ: Solve method Q is also a a cut-down version of solve method 3.
In solve method Q, only occurrence of the following types are considered:
If we have on a row from a solution grid of dimension 9:
12 12 (pattern of two)
123 123 123 (pattern of three)
12 23 13 (pattern of three)
1234 1234 1234 1234 (pattern of four)
And so on, then we can eliminate the numbers from other cells in the row.
SR (hidden and naked pair): Solve method R is a cut-down version of solve method 3.
In solve method R, only pattern of length 2 is considered.
SS (hidden and naked triplet): Solve method S is a cut-down version of solve method 3.
In solve method S, only pattern of length 3 (or less) is considered.
ST (Swordfish): Solve method T is a cut-down version of solve method 4.
In solve method T, only n=3 (or less) is considered.
SU (XY-Wing): Solve method U is a cut-down version of solve method L (solve method L is a cut-down version of solve method M).
In solve method U, only closed chain of length 4 is considered.
SV (Turbot fish): Solve method V is a cut-down version of solve method L (solve method L is a cut-down version of solve method 5).
In solve method V, only closed chain of length 5 (or less) is considered.
SG: Solve method G is a cut-down version of solve method M (solve method M is a cut-down version of solve method 5).
In solve method G, only closed chain of length 4 is considered.
I haven't given this pattern a name, but it's similar (or can be considered an extension) of the XY-wing pattern.
SH: Solve method H is a cut-down version of solve method M (solve method M is a cut-down version of solve method 5).
In solve method H, only closed chain of length 5 (or less) is considered.
I haven't given this pattern a name, but it's similar (or can be considered an extension) of the turbot fish pattern.
SJ: Solve method J is a cut-down version of solve method 5.
In solve method J, only closed chain of length 4 is considered.
I haven't given this pattern a name, but it's similar (or can be considered an extension) of the XY-wing pattern.
SK: Solve method K is a cut-down version of solve method 5.
In solve method K, only closed chain of length 5 (or less) is considered.
I haven't given this pattern a name, but it's similar (or can be considered an extension) of the turbot fish pattern.
SZ: Finally, when all else fails, solve method Z is the brute force method (or trial and error, or guessing, whatever you want to call it).
This solve method will find all valid solutions, up to a certain value n.
The value n can be changed from Project->Settings.
For example, if n is set to 2000, then the solve method will continue to search the solution space for valid solutions, until the number of valid solutions found = 2000, or the search space has been thoroughly searched and all the valid solutions have been found which are < 2000.
That is, if n is set to 2000, and a grid has 1520 possible solutions, then the solver will show that there are 1520 solutions, and display all 1520 valid solutions.
If on the other hand, a grid has 2350 possible solutions, then the solver will stop once it finds 2001 solutions, display a message that there are more than 2000 valid solutions, and display the first 2000 valid solutions it finds.
If you'd like to include all the solve methods (except P, Q), then the recommended solve order is: 12RS3NT4UVGHJKLM5Z
-----------------------------------------------------------
Version history:
Version 1.17 (7 August 2005):
- On my visit to several sudoku forums, I noticed that people have given names to several patterns found in sudoku. These include: hidden pair, naked pair, X-wing, swordfish, XY-wing, turbot fish. I have added several solvers (which are cut-down version of solver 1 to 5) to cater for these named patterns. These solvers are named SR, SS, ST, SU, SV. I have also added solvers SG, SH, SJ, SK as extensions to the XY-wing and turbot fish patterns.
- Miscellaneous improvements.
Version 1.16 (20 July 2005):
- Removed certain restrictions on solve method 5 (S5) and solve method M (SM). The solver is now able to solve more sudoku, but is slower! :)
Version 1.15 (19 July 2005):
- GUI bug fix
Version 1.14 (19 July 2005):
- Added different type of views for viewing the grid
- Solutions from solve method Z (SZ - brute force search) are now added to the Event Log. Size of Event Log can now be limited through Project->Settings.
- Miscellaneous improvements.
Version 1.13 (17 July 2005):
- Fixed bug in solve method 5 (S5) and solve method M (SM).
- Created a new solve method 3 (S3); Renamed old S3 to solve method P (SP). Also created a new solve method Q (SQ), a variant of S3.
- Miscellaneous improvements.
Version 1.00 initial release:
- Implemented solve method 1, 2, 3, 4, 5 (S1, S2, S3, S4, S5).
|
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in
Log in to check your private messages
