Didn’t your mother tell you not to gang up on the other kids?
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….
Answers to questions:
- 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.
- Is there an initial configuration of the board which looks sensible, but has a logical inconsistency so there aren’t actually any solutions.
- In the puzzles posed by newspapers (at least the easy ones I have done), there is normally always a fully constrained position for every next move. Is this always the case?
- If there isn’t a fully constrained position for every next move, are all subtrees except one blind alleys, or not?
- How does one generate a puzzle where one knows that there are always enough constraints to make a reasonably unambiguous decision?
- In the case of underconstrained configurations how large is the state space?
- In the case of no initial constraints (no numbers at all), how large is the state space of all possible solutions?