Flood-It/Globs

The solitaire game "Globs" or "Flood-It" consists of a rectangular grid with each square assigned a color. Adjacent squares of the same color form a "glob" (a connected component on the graph). Your control is to change the color of the upper-leftmost glob, thereby growing it larger and larger by matching color of adjacent globs. The object is to reduce the puzzle to a single glob, in a minimum number of moves.

Typical values: 14x14 grid, 6 colors, 25 move limit.

The number of paths through this game is large enough that brute-force search probably won't work well. Given 25 moves and 5 choices per move (picking the same color as the previous move doesn't make sense), there are about 3*10^17 choices.

Last night after deciding I was definitively done with work for the day, I tried a heuristic approach. First, compute the shortest path(s) to each glob from the start position. Start with the longest such path, L. Then iteratively:

1. Compute the game state after playing L
2. Identify the glob with the longest minimum path M (calculated from the start position) which has not yet been absorbed.
3. Set L' to the join of L and M (a shortest common supersequence.)
4. Repeat steps 1-3 until all globs are absorbed by L.

Coding up shortest common supersequence is fun, and the resulting algorithm is very fast. But, the heuristic performs poorly, returning solutions that take between 23 and 28 moves on the randomly-generated examples I tried.

One obvious weakness is that we should not pick the glob that is furthest from the start, but instead furthest from the user-controlled glob. Given the speed of the shortest-path computation this should be feasible.

A more aggressive join-based approach would be to find a broad set of paths to 'distant' globs, including some nonoptimal ones, and then find the joins over multiple paths at once. But this seems like it could require an unfeasibly large number of candidate paths. Even if we heuristically reduce to, say, 15 target globs, we could compare no more than a few paths to each glob: for example 5^15 = 30.5 million 15-way supersequence calculations. An improvement on the heuristic is to look for longest candidates that are of different colors. If we found just 6 candidates and looked for a join of their shortest paths, that might do significantly better.

I also wondered whether the problem would be more feasible if tackled via reverse search. We know that the board at move N-1 (in an N-move solution) will consist of just globs of one color, and on the previous move just two colors. We might be able to identify a small set of feasible near-ending positions and work our way back from there--- but the number of subsets of globs of one color is still large enough to give one pause.

Ideally there would be a dynamic programming approach but the game doesn't seem amenable to decomposition until the endgame. Like my original heuristic approach, a good solution for a reduced region might not be expandable into a good solution for the entire board.

Board:

EDCEFDEBBDFFAB
EACDACFFDEBBEE
FEFDCFBDBEBCFC
EEEFCECAFFEABC
EFBDBCEEFDBCAE
EABDAEFEDFBCEF
AABBEBDAFFDCDB
CBBDCCBECAFAAF
DDFDBDEBFEFEAB
BFFABBFCEDEFCB

Minimum distances:

[ 0][ 1][ 2][ 3][ 4][ 5][ 6][ 7][ 7][ 8][ 9][ 9][10][11]
[ 0][ 1][ 2][ 3][ 4][ 5][ 6][ 7][ 8][ 8][ 9][ 9][ 9][10]
[ 0][ 1][ 2][ 3][ 4][ 5][ 6][ 6][ 7][ 8][ 9][ 9][10][10]
[ 1][ 2][ 3][ 3][ 4][ 5][ 6][ 7][ 8][ 8][ 9][10][11][11]
[ 2][ 2][ 2][ 3][ 4][ 5][ 6][ 7][ 8][ 8][ 9][10][11][11]
[ 2][ 3][ 3][ 4][ 5][ 6][ 7][ 7][ 8][ 9][10][11][12][12]
[ 3][ 4][ 4][ 5][ 6][ 6][ 7][ 8][ 8][ 9][10][11][12][13]
[ 4][ 5][ 5][ 6][ 7][ 7][ 7][ 8][ 9][10][10][11][12][13]
[ 5][ 6][ 5][ 6][ 6][ 7][ 7][ 7][ 8][ 9][10][11][12][13]
[ 5][ 5][ 5][ 5][ 6][ 7][ 8][ 8][ 9][ 9][10][11][12][13]
[ 6][ 5][ 5][ 6][ 7][ 7][ 8][ 9][10][10][11][12][12][13]
[ 6][ 6][ 6][ 6][ 7][ 8][ 9][10][11][11][11][12][12][13]
[ 7][ 7][ 7][ 6][ 7][ 8][ 9][10][10][11][12][12][12][13]
[ 7][ 7][ 7][ 7][ 8][ 8][ 9][10][10][11][12][13][13][13]

Solution steps:

Starting with (10, 13) and (8, 13)
Sequence: AEBCBECBFAFBAFC
Unreached: set([(7, 3), (11, 11), (5, 9), (7, 12), (2, 8), (3, 11), (0, 7), (11, 7), (12, 5), (5, 6), (4, 12), (1, 6), (0, 10), (9, 6), (3, 7), (2, 5), (1, 11), (10, 3), (0, 3), (1, 2), (13, 12), (2, 9), (11, 5), (10, 7), (12, 9), (5, 12), (3, 13), (12, 6), (1, 5), (13, 7), (13, 11), (3, 6), (0, 4), (1, 10), (12, 10), (5, 3), (11, 13), (4, 10), (5, 4), (2, 6), (9, 10), (5, 11), (4, 5), (1, 13), (12, 7), (11, 9), (6, 11), (1, 4), (5, 13), (11, 0), (0, 9), (7, 5), (0, 5), (5, 10), (7, 7), (0, 12), (13, 10), (4, 11), (3, 5), (0, 1), (13, 6), (7, 0), (8, 1), (3, 12), (11, 8), (7, 13), (0, 13), (2, 4), (0, 6), (1, 8), (12, 4), (11, 6), (6, 13), (1, 7), (2, 3), (13, 9), (9, 13), (7, 8), (0, 2), (9, 12), (2, 12)])
Sequence: AEBCBECBFAFBAFEC
Unreached: set([(7, 3), (5, 9), (2, 8), (3, 11), (0, 7), (11, 7), (12, 5), (4, 12), (1, 6), (0, 10), (9, 6), (3, 7), (2, 5), (1, 11), (10, 3), (0, 3), (1, 2), (11, 5), (8, 1), (12, 9), (5, 12), (3, 13), (12, 6), (1, 5), (13, 7), (13, 11), (3, 6), (0, 4), (1, 10), (12, 10), (5, 3), (11, 13), (5, 4), (2, 6), (9, 10), (5, 11), (4, 5), (1, 13), (12, 7), (6, 11), (1, 4), (5, 13), (11, 0), (0, 9), (0, 5), (5, 10), (0, 12), (13, 10), (4, 11), (3, 5), (0, 1), (13, 6), (3, 12), (11, 8), (7, 13), (0, 13), (2, 4), (0, 6), (6, 13), (1, 7), (2, 3), (13, 9), (9, 13), (7, 8), (0, 2), (9, 12), (2, 12)])
Sequence: AEBCBECBFAFBAFECF
Unreached: set([(7, 3), (5, 9), (2, 8), (3, 11), (0, 7), (11, 7), (12, 5), (4, 12), (1, 6), (0, 10), (3, 7), (2, 5), (1, 11), (10, 3), (0, 3), (1, 2), (11, 5), (8, 1), (9, 6), (5, 12), (3, 13), (12, 6), (1, 5), (13, 7), (3, 6), (0, 4), (1, 10), (12, 10), (11, 13), (5, 4), (2, 6), (9, 10), (5, 11), (4, 5), (1, 13), (12, 7), (6, 11), (1, 4), (5, 13), (11, 0), (0, 9), (0, 5), (5, 10), (0, 12), (13, 10), (4, 11), (5, 3), (0, 1), (13, 6), (3, 12), (0, 13), (2, 4), (0, 6), (6, 13), (1, 7), (2, 3), (13, 9), (9, 13), (7, 8), (0, 2), (9, 12), (2, 12)])
Sequence: AEBCBECBFAFBAFECFB
Unreached: set([(7, 3), (5, 9), (2, 8), (3, 11), (4, 12), (1, 6), (0, 10), (3, 7), (2, 5), (10, 3), (0, 3), (1, 2), (11, 5), (8, 1), (9, 6), (5, 12), (3, 13), (12, 6), (1, 5), (13, 7), (0, 4), (1, 10), (12, 10), (2, 6), (9, 10), (5, 11), (4, 5), (1, 13), (12, 7), (6, 11), (1, 4), (5, 13), (11, 0), (0, 9), (0, 5), (0, 12), (13, 10), (4, 11), (5, 3), (0, 1), (13, 6), (3, 12), (0, 13), (2, 4), (0, 6), (6, 13), (1, 7), (2, 3), (13, 9), (7, 8), (0, 2), (9, 12), (2, 12)])
Unreached: set([(3, 12), (3, 13), (1, 13), (0, 13), (5, 13), (3, 11), (4, 12), (2, 12), (0, 10)])
Found sequence: 26

Tags:
• Post a new comment

Error

default userpic