Blog Post

Sudoku by SQL Part 3 of 3

,

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

declare@gameID int
execdbo.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 output
select @gameID

For the first test I used a sudoku created by my Android sudoku app, level "extreme".

Starting

exec StartGame 1

With this procedure the tables Cell, Candidate and CandidateMask are initialized with the start position of game 1.

Viewing 

You can have a look at the currently known cells with

select * from Board

That gives you for the game above:

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

select * from CandidateMaskDisplay

 That gives you:

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

set nocount on

exec Solve

For better readability of output I set nocount on.
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.

Feel free to add a comment!

Rate

You rated this post out of 5. Change rating

Share

Share

Rate

You rated this post out of 5. Change rating