The Challenge
Since I came across the first sudoku I was wondering if it could by solved by SQL using queries that select just the right value for a cell.Well, some day I tried, here is what I have got now.
Previous Parts
In part one tables und views are described.
In part two I introduce rules and the solving procedure.
Here you will see some convenience features and conclusion.
And of course the source, created for Microsoft SQL Server, tested with version 2012.
Playing
For starting and solving a game there are some stored procedures for convenience. With game I mean the "start position", together with a name and description.
Creating a Game
For the first test I used a sudoku created by my Android sudoku app, level "extreme".declare @gameID intexec dbo.CreateGame 'Name of Game', 'Some Description','..38....4.9..1..8.2....73..7....18...8..9..7...47....3..12....9.6..3..4.3....52..', @gameID outputselect @gameID
Starting
With this procedure the tables Cell, Candidate and CandidateMask are initialized with the start position of game 1.exec StartGame 1
Viewing
You can have a look at the currently known cells with
If you want to see the candidates, use
That gives you for the game above:select * from Board
Row
|
C1
|
C2
|
C3
|
C4
|
C5
|
C6
|
C7
|
C8
|
C9
|
1
|
NULL
|
NULL
|
3
|
8
|
NULL
|
NULL
|
NULL
|
NULL
|
4
|
2
|
NULL
|
9
|
NULL
|
NULL
|
1
|
NULL
|
NULL
|
8
|
NULL
|
3
|
2
|
NULL
|
NULL
|
NULL
|
NULL
|
7
|
3
|
NULL
|
NULL
|
4
|
7
|
NULL
|
NULL
|
NULL
|
NULL
|
1
|
8
|
NULL
|
NULL
|
5
|
NULL
|
8
|
NULL
|
NULL
|
9
|
NULL
|
NULL
|
7
|
NULL
|
6
|
NULL
|
NULL
|
4
|
7
|
NULL
|
NULL
|
NULL
|
NULL
|
3
|
7
|
NULL
|
NULL
|
1
|
2
|
NULL
|
NULL
|
NULL
|
NULL
|
9
|
8
|
NULL
|
6
|
NULL
|
NULL
|
3
|
NULL
|
NULL
|
4
|
NULL
|
9
|
3
|
NULL
|
NULL
|
NULL
|
NULL
|
5
|
2
|
NULL
|
NULL
|
If you want to see the candidates, use
That gives you:select * from CandidateMaskDisplay
Row
|
C1
|
C2
|
C3
|
C4
|
C5
|
C6
|
C7
|
C8
|
C9
|
1
|
1...56...
|
1...5.7..
|
NULL
|
NULL
|
.2..56...
|
.2...6..9
|
1...567.9
|
12..56..9
|
NULL
|
2
|
...456...
|
NULL
|
....567..
|
..3456...
|
NULL
|
.234.6...
|
....567..
|
NULL
|
.2..567..
|
3
|
NULL
|
1..45....
|
....56.8.
|
...456..9
|
...456...
|
NULL
|
NULL
|
1...56..9
|
1...56...
|
4
|
NULL
|
.23.5....
|
.2..56..9
|
..3456...
|
.2.456...
|
NULL
|
NULL
|
.2..56..9
|
.2..56...
|
5
|
1...56...
|
NULL
|
.2..56...
|
..3456...
|
NULL
|
.234.6...
|
1..456...
|
NULL
|
12..56...
|
6
|
1...56..9
|
12..5....
|
NULL
|
NULL
|
.2..56.8.
|
.2...6.8.
|
1...56..9
|
12..56..9
|
NULL
|
7
|
...45..8.
|
...45.7..
|
NULL
|
NULL
|
...4.678.
|
...4.6.8.
|
....567..
|
..3.56...
|
NULL
|
8
|
....5..89
|
NULL
|
.2..5.789
|
1.......9
|
NULL
|
.......89
|
1...5.7..
|
NULL
|
1...5.78.
|
9
|
NULL
|
...4..7..
|
......789
|
1..4.6..9
|
...4.678.
|
NULL
|
NULL
|
1....6...
|
1....678.
|
Solving
For better readability of output I set nocount on.set nocount onexec Solve
Here is the solution:
Row
|
C1
|
C2
|
C3
|
C4
|
C5
|
C6
|
C7
|
C8
|
C9
|
1
|
5
|
7
|
3
|
8
|
2
|
9
|
1
|
6
|
4
|
2
|
4
|
9
|
6
|
5
|
1
|
3
|
7
|
8
|
2
|
3
|
2
|
1
|
8
|
6
|
4
|
7
|
3
|
9
|
5
|
4
|
7
|
3
|
9
|
4
|
5
|
1
|
8
|
2
|
6
|
5
|
6
|
8
|
5
|
3
|
9
|
2
|
4
|
7
|
1
|
6
|
1
|
2
|
4
|
7
|
8
|
6
|
9
|
5
|
3
|
7
|
8
|
5
|
1
|
2
|
7
|
4
|
6
|
3
|
9
|
8
|
9
|
6
|
2
|
1
|
3
|
8
|
5
|
4
|
7
|
9
|
3
|
4
|
7
|
9
|
6
|
5
|
2
|
1
|
8
|
Output from PRINT:
Iteration 1 ApplyRuleSingleCandidate solves 0 cells.
Iteration 1 ApplyRuleSingleTokenInGroup solves 5 cells.
Iteration 2 ApplyRuleSingleCandidate solves 0 cells.
Iteration 2 ApplyRuleSingleTokenInGroup solves 1 cells.
Iteration 3 ApplyRuleSingleCandidate solves 0 cells.
Iteration 3 ApplyRuleSingleTokenInGroup solves 0 cells.
Removed 0 candidates due to complete match in same group
Removed 0 candidates due to exclusive partial sets in same group
Removed 1 candidates due to candidate values in a square in only one row or column
Iteration 4 ApplyRuleSingleCandidate solves 0 cells.
Iteration 4 ApplyRuleSingleTokenInGroup solves 0 cells.
Removed 0 candidates due to complete match in same group
Removed 0 candidates due to exclusive partial sets in same group
Removed 0 candidates due to candidate values in a square in only one row or column
nestlevel 2: guessing value 1 in cell 17
Iteration 5 ApplyRuleSingleCandidate solves 0 cells.
Iteration 5 ApplyRuleSingleTokenInGroup solves 3 cells.
Iteration 6 ApplyRuleSingleCandidate solves 1 cells.
Iteration 6 ApplyRuleSingleTokenInGroup solves 5 cells.
Iteration 7 ApplyRuleSingleCandidate solves 3 cells.
Iteration 7 ApplyRuleSingleTokenInGroup solves 6 cells.
Iteration 8 ApplyRuleSingleCandidate solves 3 cells.
Iteration 8 ApplyRuleSingleTokenInGroup solves 3 cells.
Iteration 9 ApplyRuleSingleCandidate solves 1 cells.
Iteration 9 ApplyRuleSingleTokenInGroup solves 2 cells.
Iteration 10 ApplyRuleSingleCandidate solves 1 cells.
Iteration 10 ApplyRuleSingleTokenInGroup solves 3 cells.
Iteration 11 ApplyRuleSingleCandidate solves 2 cells.
Iteration 11 ApplyRuleSingleTokenInGroup solves 7 cells.
Iteration 12 ApplyRuleSingleCandidate solves 4 cells.
Iteration 12 ApplyRuleSingleTokenInGroup solves 3 cells.
Iteration 13 ApplyRuleSingleCandidate solves 0 cells.
Iteration 13 ApplyRuleSingleTokenInGroup solves 0 cells.
Removed 0 candidates due to complete match in same group
Removed 0 candidates due to exclusive partial sets in same group
Removed 0 candidates due to candidate values in a square in only one row or column
Solved!
Harder Than Hardest
Inspired by this success, I searched the internet for the hardest sudoku. The hardest I found is solved with a guessing depth of 6. Sudoku should not need any guessing, so obviously there is at least one rule missing.I can describe one: a set in exactly two rows and two squares forbids these values as candidates in the third square in these two rows. But I did not implement it (yet).
What I was curious about is how the solving process would react on a complete empty starting position. That is not solvable unambiguously, of course, but it is the ultimate edge case. Unfortunately trying this I run into the limit of maximum allowed nestlevel (recursiveness) of stored procedures, which is 32.
Conclusion
I like playing sudoku, but writing a sudoku solver is even more fun for me.
Throwing an exception in a trigger causes the transaction to be in an uncommitable state. That's why I check the state after inserting values into table Cell in the stored procedure, not in the trigger.
SQL Server does not really have nested transactions, but savepoints did the job.
datamanny, you have a brilliant brain and I think it is amazing how you did this? I downloaded the source code and when I have time want to go through it and learn something. Thank you for sharing!
ReplyDelete