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