On Wed, Mar 25, 2015 at 2:31 PM, Marko Rauhamaa <ma...@pacujo.net> wrote: > Ian Kelly <ian.g.ke...@gmail.com>: > >> The test puzzle that you posted has 23 values already filled in. How >> does it perform on harder puzzles with only 17 clues (the proven >> minimum)? One would expect it to be around a million times slower. > > Just try it. The example had a minimum of clues (drop one clue and > you'll get multiple solutions). > > <URL: http://www.telegraph.co.uk/news/science/science-news/9359579/W > orlds-hardest-sudoku-can-you-crack-it.html> mentions this puzzle: > > ======================================================================== > 8 . . . . . . . . > . . 3 6 . . . . . > . 7 . . 9 . 2 . . > . 5 . . . 7 . . . > . . . . 4 5 7 . . > . . . 1 . . . 3 . > . . 1 . . . . 6 8 > . . 8 5 . . . 1 . > . 9 . . . . 4 . . > ======================================================================== > > It takes about 2 seconds for my Python program to find the answer but it > spends a total of 110 seconds to exhaust the problem space. > > The analogous C program finished the whole thing in 200 milliseconds.
"Hard" for a human doesn't necessarily mean "hard" for a programmatic solver in this case. Try your solver on this one: $ cat sudoku2.dat . . . 7 . . . . . 1 . . . . . . . . . . . 4 3 . 2 . . . . . . . . . . 6 . . . 5 . 9 . . . . . . . . . 4 1 8 . . . . 8 1 . . . . . 2 . . . . 5 . . 4 . . . . 3 . . I tried the first puzzle you posted, and it took about a second. I then started running it on this one before I started typing up this post, and it hasn't finished yet. While that was running, I then tried running Norvig's solver on this puzzle, and it completed in about 0.07 seconds. For the curious, this puzzle was arbitrarily collected from http://theconversation.com/good-at-sudoku-heres-some-youll-never-complete-5234 -- https://mail.python.org/mailman/listinfo/python-list
