I get a lot of traffic to this blog because of my Sudoku solver. Google analytics tells me most of it lands on the original version that I wrote, and not the optimised version that's now the worlds fastest XSLT 2.0 solution - an issue which this post should hopefully rectify.
The puzzle on the right is apparently the worlds hardest Sudoku puzzle. If I run my solver "Sudoku.xslt" using Kernow's performance testing feature I get this result:
Ran 5 times
Run 1: 328 ms
Run 2: 344 ms
Run 3: 328 ms
Run 4: 391 ms
Run 5: 328 ms
Ignoring first 2 times
Total Time (last 3 runs): 1 second 47 ms
Average Time (last 3 runs): 349 ms
So on my machine the average execution time is 349ms, which is pretty good considering the original version would take minutes for several puzzles. As far as I know this version will solve all puzzles in under a second on my machine (Core 2 duo E6600, 2gb).
How does it do it? This is taken from the web page where it's hosted:
It accepts the puzzle as 81 comma separated integers in the range 0 to 9, with zero representing empty. It works by continuously reducing the number of possible values for each cell, and only when the possible values can't be reduced any further it starts backtracking.
The first phase attempts to populate as many cells of the board based on the start values. For each empty cell it works out the possible values using the "Naked Single", "Hidden Single" and "Naked Tuples" techniques in that order (read here for more on the techniques). Cells where only one possible value exists are populated and then the second phase begins.
The second phase follows this process:
* Find all empty cells and get all the possible values for each cell (using Naked Single and Hidden Single techniques)
* Sort the cells by least possible values first
* Populate the cells with only one possible value
* If more there's more than one value, go through them one by one
* Repeat
This is how it solves the Al Esgargot: A slightly modified version of the solution gives this output with the $verbose parameter set to true. As you can see it's found that it can insert a 1 at position 66 using the static analysis of the puzzle (position 66 is middle-right of the bottom-left group). Next it's decided that there are two possible values 4 and 6 at index 12 (middle-right cell of top-left group), so it tries 4 and continues. With that 4 in place it's found that there's only one possible value at index 39, a 3, so it inserts that and continues. It will keep reducing the possible values based on the current state of the board, inserting the only possible values or trying each one when there are many, until either there are no possible values for an empty cell, or the puzzle is solved.
(the solution is shown below)
Populated single value cell at index 66 with 1
Trying 4 out of a possible 4 6 at index 12
Only one value 3 for index 39
Trying 5 out of a possible 5 7 at index 10
Trying 1 out of a possible 1 9 at index 13
Only one value 9 for index 15
Trying 6 out of a possible 6 7 at index 16
Only one value 7 for index 17
Trying 2 out of a possible 2 4 at index 7
Trying 6 out of a possible 6 8 at index 2
Only one value 8 for index 3
Only one value 2 for index 48
Only one value 6 for index 57
Only one value 5 for index 60
Only one value 9 for index 63
Only one value 5 for index 74
Only one value 1 for index 78
Only one value 3 for index 69
Only one value 5 for index 71
Only one value 6 for index 81
Only one value 4 for index 36
! Cannot go any further !
Trying 8 out of a possible 8 at index 2
Only one value 6 for index 3
Trying 4 out of a possible 4 5 at index 4
Only one value 3 for index 9
Only one value 3 for index 23
Only one value 4 for index 26
Only one value 3 for index 53
Only one value 5 for index 54
Only one value 4 for index 36
Only one value 6 for index 44
Only one value 8 for index 48
Only one value 2 for index 57
Only one value 8 for index 73
Only one value 9 for index 47
Only one value 7 for index 50
Only one value 6 for index 60
Only one value 9 for index 64
! Cannot go any further !
Trying 5 out of a possible 5 at index 4
Only one value 9 for index 47
Only one value 2 for index 67
Only one value 7 for index 49
Only one value 9 for index 64
Only one value 2 for index 80
Only one value 1 for index 32
Only one value 2 for index 48
Only one value 5 for index 50
Only one value 8 for index 58
Only one value 8 for index 73
! Cannot go any further !
Trying 4 out of a possible 4 at index 7
Only one value 3 for index 9
Only one value 4 for index 23
Only one value 3 for index 24
Only one value 2 for index 26
Only one value 3 for index 53
Only one value 5 for index 54
Only one value 8 for index 4
Trying 2 out of a possible 2 6 at index 2
Only one value 6 for index 3
Trying 7 out of a possible 7 8 at index 19
Only one value 8 for index 20
Only one value 7 for index 29
Only one value 9 for index 40
Only one value 7 for index 50
Only one value 6 for index 44
Only one value 2 for index 49
Only one value 2 for index 28
Only one value 8 for index 48
Only one value 2 for index 57
Only one value 5 for index 67
Only one value 7 for index 58
Only one value 8 for index 61
Only one value 3 for index 68
Only one value 2 for index 70
! Cannot go any further !
Trying 8 out of a possible 8 at index 19
Only one value 7 for index 20
Only one value 8 for index 29
Only one value 9 for index 47
Only one value 2 for index 48
Only one value 8 for index 57
Only one value 4 for index 37
Only one value 9 for index 40
Only one value 7 for index 49
! Cannot go any further !
Trying 6 out of a possible 6 at index 2
Only one value 2 for index 3
Only one value 6 for index 57
Trying 7 out of a possible 7 8 at index 19
Only one value 8 for index 20
Trying 2 out of a possible 2 4 at index 28
Only one value 7 for index 29
Only one value 9 for index 47
Only one value 2 for index 49
Only one value 9 for index 40
Only one value 6 for index 44
Only one value 7 for index 50
Only one value 9 for index 59
! Cannot go any further !
Trying 4 out of a possible 4 at index 28
Only one value 9 for index 37
Only one value 4 for index 44
Only one value 6 for index 42
Trying 2 out of a possible 2 7 at index 29
Only one value 7 for index 47
Only one value 2 for index 49
Only one value 7 for index 32
Only one value 9 for index 50
! Cannot go any further !
Trying 7 out of a possible 7 at index 29
Only one value 1 for index 32
Only one value 2 for index 33
Only one value 2 for index 47
Trying 7 out of a possible 7 9 at index 49
Only one value 9 for index 50
Only one value 6 for index 77
Only one value 1 for index 78
Only one value 5 for index 80
Only one value 5 for index 56
Only one value 8 for index 60
Only one value 2 for index 61
Only one value 8 for index 70
Only one value 6 for index 71
Only one value 9 for index 74
Only one value 2 for index 64
Only one value 4 for index 81
Only one value 4 for index 58
Only one value 9 for index 67
Only one value 8 for index 73
Only one value 2 for index 76
Done!
1, 6, 2, 8, 5, 7, 4, 9, 3,
5, 3, 4, 1, 2, 9, 6, 7, 8,
7, 8, 9, 6, 4, 3, 5, 2, 1,
4, 7, 5, 3, 1, 2, 9, 8, 6,
9, 1, 3, 5, 8, 6, 7, 4, 2,
6, 2, 8, 7, 9, 4, 1, 3, 5,
3, 5, 6, 4, 7, 8, 2, 1, 9,
2, 4, 1, 9, 3, 5, 8, 6, 7,
8, 9, 7, 2, 6, 1, 3, 5, 4,
If you have a solution that can statically detect more cells to fill using different techniques than I have, or has a better strategy than simply backtracking when there's more than one value, then I'd be interested to know it works.
I'm pretty sure the XSLT is as good as it can be, but if you think it can be improved in any way then let me know.
14 comments:
thanks for posting this! :)
Hi,
I created a solver in C#. For the above puzzle, my solver solves in 203 ms.
You can look at my solution on
http://www.codeproject.com/KB/cs/SudokuPuzzle.aspx
yeah, i think there is a better way. We actually have the same processor, and my solver is averaging 45ms.
I'll upload and link my code.
If you do it right, you should be able to solve ALL uniquely solvable 9x9 sudokus in less than 1 millisecond and average around 30 microseconds. These timings are not at all impressive.
Obviously time alone isn't enough, you also need to know the hardware the code is run on. Run this code on suitable hardware and you might get it down to 30 microseconds average.
Assuming you meant a standard desktop, please show me how to "do it right" with benchmarks showing your times.
Also (and I shouldn't have to point this out but...) the goal wasn't the fastest Sudoku solver, it's the fast XSLT Suduoku solver.
Ok. The preliminary version (i.e. first functional version) of my program solves and verifies uniquiness for the following puzzles in the respective times (±2㎲):
well-known puzzle: 703㎲
.......39
.....1..5
..3.5.8..
..8.9...6
.7...2...
1..4.....
..9.8..5.
.2....6..
4..7.....
puzzle on this page: 253㎲
1....7.9.
.3..2...8
..96..5..
..53..9..
.1..8...2
6....4...
3......1.
.4......7
..7...3..
'evil' from websudoku: 23㎲
....8..3.
4.1.....7
..5..64..
..4.3..5.
...958...
.6..2.3..
..82..9..
6.....2.1
.1..6....
'medium' from websudoku: 14㎲
...8.....
.7.2..94.
..4.7.5.6
.....76.9
74.....85
1.65.....
3.5.6.2..
.61..8.5.
.....2...
No special hardware. Just a Core 2 Q8200 without using any multithreading.
Congratulations... please show me the XSLT so I can run it myself.
Opps. I guess I parsed the title incorrectly. I though it was claiming that the world's fastest sudoku solver is written in XSLT, which is clearly not the case. This may very well be a fast solver written in XSLT, but you may need to use a more suitable language to go for real speed. The time for Escargot resembles something a little slower than what is capable of the slow and interpreted language Mathematica, who's times are basically 1000 fold what I gave above.
Would you mind coding up your algorithm in another language of your choice and giving the speed competition another go?
Ahh ok, that explains your original "not at all impressive" statement.
It's not in my interest to code Sudoku solvers - it was just something unusual to do using XSLT.
If you have an interesting problem to solve using XSLT let me know and we can have a speed competition.
Actually, several runs of the code in a row give quite different results. Apparently, it was done executing before it could get settled(?) in the cache. Anyways, both the top one and escargot are averaging around 150㎲ to solve.
I have one question/comment about your solver. Is your naked/hidden singles logic complete and optimized? If it is, the most difficult sudokus shouldn't take more than 50-80 times longer than the easiest ones. More specialized logic shouldn't be implemented unless the sinlges are absolutely solid. This is the stage I find myself in with the solver.
P.S. I actually wrote the solver in highly optimized hand-coded assembly, so XSLT has no chance in this case. C does, though.
This puzzle is easy. It only appears difficult because it requires one brute force move to solve. The puzzle is rated less than 3500.
Easter Monster is rated 13541 and Golden Nugget is rated 17660 and they require one or two brute force moves to unlock. I have puzzles rated higher than the ones mentioned and don't require a brute force move or guessing to solve. I have the worlds most difficult Sudoku Puzzle guaranteed. And its for sale to the highest bidder.
Hey i got a new answer
152. 857. 493
436. 921. 678
789. 643. 521
875. 312. 946
914. 586. 732
623. 794. 185
368. 475. 219
541. 239. 867
297. 168. 354
incorrect !?
see the second row, 6 appears 2 times.
436 921 678
IT IS A UNIQUE PUZZLE.
I took your XSLT stylesheet and integrated it with an interactive XSLT (Saxon-JS) interface. Check this: http://www.masereeuw.nl/sudoku/index.html.
Strangely enough, I had to change the type of some variables and functions from xs:integer+ to xs:integer*. Can it be that Saxon's typechecking rules have evolved?
Post a Comment