Things I now know about sudoku!

So, I did a bit of reading, and wrote a little solver. Will solve most puzzles instantly, and all puzzles with a unique solution in under thirty ten seconds. Not bad for a days work. Doesn’t even need multiple CPU cores.

I notice that Knuth has a clever way to do it a thousand times faster. I have not represented all the constraints explicitly….

My solver is here.

Before:

After:

Answers to questions:

  • Yes.
  • Not necessarily, but for human solvable problems, the decision tree is pretty constrained. There may be heuristics I don’t know about.
  • Depends on initial constaints, sometimes yes, sometimes no.
  • That’s the next big thing I have to figure out. It looks much more tricky.
  • As one passes the point where there is not enough information to find a unique solution, for every digit you remove from the initial configuration, the solution space goes up by a factor of between 10 and 100 roughly.
  • With no initial constraints, taking symmetries into account, the state space is five billion. Not taking symmetries into account it’s one trillion times that again.

Leave a Reply

Your e-mail address will not be published. Required fields are marked *