Friday, March 30, 2007

Er, the real "hardest Sudoku"

Following the comment from Malcom below, I've run my Sudoku solver against the real "AL Escargot"...

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:

xmlizer said...

May be a dummy question : is the solution unique ?

Andrew Welch said...

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.

piers said...

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!