Using Saxon 8.9.0.3b from the command line with the -3 option (to discount java startup time) the average time across three runs is 2213ms... which isn't bad at all.

This is when I just solve the puzzle starting at the top-left - if I turn on the ordering feature where empty cells are processing by least number of possibilities first, then the time dramatically increases to ~58 seconds, which shows why Sudoku is NP-complete.

If you're interested the solution it produced is:

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,

## 3 comments:

May be a dummy question : is the solution unique ?

Apparently a "proper puzzle" has a single solution:

http://en.wikipedia.org/wiki/List_of_Sudoku_terms_and_jargon

So yes, I would assume the solution is unique.

Ha ha... good work! One thing that seemed odd when I first came across the claim to have found the "world's most complicated sudoku" is that a sudoku is really a member of a class of analogous instances: if you take a sudoku and swap row 1 with row 2 or row 3, for instance, the solution will be unchanged, since you haven't changed the set of [1..9] in a) any rows, b) any columns or c) any blocks.

So discovery of a world's most complicated actually implies discovery of a class of some 2(6^6) instances... well, a big number, in any case! Cheers!

Post a Comment