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
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 intexecdbo.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
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
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 onexec 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:
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.
