It sucks because it resists pruning. If you can’t get rid of the vast majority of unsolvable paths through the puzzle early on, you will never solve it. I looked at a pair of level 49 puzzles last night; one was 21 flips, the other was 24. These won’t prune until a very low level. Let’s assume that, through a flash of insight, you were able to correctly place the first four pieces correctly. It would still take many hours to complete.
There’s only three things you can do with puzzles like this.
First: Get the number of flips down. Refuse to bother with a puzzle with more than a dozen or so flips. These can still take hours to do.
Second: Be quick about giving up. You’re going to have to be lucky to solve one of these in a reasonable amount of time. If you’re not solving it in an hour, start over.
Third: Be creative. This is going to be hardest for me. I can optimize code, use a different language, even explore low-level Cell processor coding along with significant parallelism.
There’s so many paths through this tree. Every puzzle may be solvable, but we’re really only interested in the ones that can be solved in an hour or so.
2 Comments
There are two other strategies to consider. I’ve wrote about them loosely in my NP profile.
Essentially, you can put more intelligence into the algorithm: focus more efforts into choosing good pieces or more efforts into pruning earlier. There stuff to be gained there.
Also, you can choose a different search strategy: you can do a modified BFS, and bounce around a lot.
That’s pretty much the only variants I can see in getting a good solution.
For the record, I picked a Level 49 puzzle at random. 29 flips. I got an answer within an hour, although two hours for this level is not unreasonable.
There are at least 3 solutions in the puzzle I received; this is the one advantage of the late-40 puzzles.