Is there an efficient way of solving this game?

We can easily arrive at a lower bound on the number of moves remaining, by using breadth-first search to assign a distance to each of the remaining globs, where "distance" == # of moves required to absorb the glob. But this bound is not very tight--- we might follow one branch of moves to absorb a distant glob and still have just as many moves left to reach a different glob. I tried using the max distance as the heuristic for an A* search, but this didn't work particularly well--- there are just way too many possible paths for a reasonably-sized game.

Depth-first search will feasibly identify an upper bound, but again not a particularly good one.

I have been trying to think of a dynamic programming approach but it seems hard to come up with a formulation of the problem that doesn't either leave out valid solutions, or suffer exponential blowup.

One property that seems useful is that a path to a glob can be arbitrarily interleaved with other paths. That is, inserting an extra move into a path doesn't break the path. So if the minimal path to a glob on the far right is Red-Green-Yellow-Blue-Purple, and the minimal path to a glob on the bottom is purple-green-yellow-blue, then the path pRGgYyBbP will reach both globs, and can obviously be simplified to purple-red-green-yellow-blue-purple.

But does this interleaving really result in the minimal path to hit _both_ globs? I think that in some cases it does not. It is certainly the case that (more generally) given a set of globs, the optimal path to reach every glob in the set need not contain every minimal path as a subpath.

For example, here's a small game with optimal solution blue-yellow-purple-red-green (or blue-purple-red-green-yellow, or blue-purple-red-yellow-green):

RGGGGRG RGGGGRR RBYYYPG RBBBBPG

But, the optimal path to the upper right red region is green-red, which is not a subpath of the complete solution.

## Error

Your reply will be screened

Your IP address will be recorded

You must follow the Privacy Policy and Google Terms of use.