Flood-It
I've been working on algorithms that solve Flood-It. I'm using a simple A* search. And then I'm using basically four ideas.
First, we can represent a board position as a network of cells where a cell represents a connected set of squares of the same color. Cell zero represents the set of squares of the same color connected to the upper-left corner. We can then quickly measure the distance of each cell from Cell zero. That gives us a lower bound on how many moves are needed to solve the game: we must at least clear a path to the furthest cell.
Secondly, consider the set of colors that are furthest from the origin. We will have to remove each of these colors, and we can't clear a color until we reach it's furthest cell. So for the lower bound we can add one move for each furthest color. More generally, for each distance, consider the set of colors at that distance and the set of colors at a further distance. Each color that is at a distance but not a further distance must be cleared at or after that distance. We can consume one color making a move to reach the distance, but any other colors will need an extra move that won't make forward progress toward reaching a further distance.
This above computation on the lower bound gives us the estimate of the cost to solve a board position needed by the A* search algorithm.
The third idea that we use helps us to reduce the number of next moves that we need to examine at a board position. Consider a cell at distance 'd' that has no neighbor at a further distance. That cell isn't blocking the path to any other cell, and we can take that cell whenever it is exposed and we happen to take it's color for some other reason. We can treat the cell as if it was at the furthest distance of any cell of its color.
We can work backwards through the distances adjusting the "effective distance" of each cell. We can increase the effective distance of a cell to be the maximum possible less than the effective distance of any cell that was at a normal distance greater than the normal distance of the cell we are adjusting. But, we also want to make sure that the "effective distance" is a distance where the color of the cell can be taken. So, for each color, we record the normal distances on which the color can be taken, and we reduce the effective distance of a cell to be one of the distances in the cells color list.
This idea allows us to restrict the next move colors to colors that are at an effective distance of 1.
Finally, we note that if we can clear a color, clearing the color is always at least as good as any other move. So if we can clear a color, we choose a single move that clears a color as our sole next move. (This is, at best, a very minor optimization.)
This simple set of ideas allows us to solve 6-color 21x21 boards. 6-color 28x28 boards remain elusive.
First, we can represent a board position as a network of cells where a cell represents a connected set of squares of the same color. Cell zero represents the set of squares of the same color connected to the upper-left corner. We can then quickly measure the distance of each cell from Cell zero. That gives us a lower bound on how many moves are needed to solve the game: we must at least clear a path to the furthest cell.
Secondly, consider the set of colors that are furthest from the origin. We will have to remove each of these colors, and we can't clear a color until we reach it's furthest cell. So for the lower bound we can add one move for each furthest color. More generally, for each distance, consider the set of colors at that distance and the set of colors at a further distance. Each color that is at a distance but not a further distance must be cleared at or after that distance. We can consume one color making a move to reach the distance, but any other colors will need an extra move that won't make forward progress toward reaching a further distance.
This above computation on the lower bound gives us the estimate of the cost to solve a board position needed by the A* search algorithm.
The third idea that we use helps us to reduce the number of next moves that we need to examine at a board position. Consider a cell at distance 'd' that has no neighbor at a further distance. That cell isn't blocking the path to any other cell, and we can take that cell whenever it is exposed and we happen to take it's color for some other reason. We can treat the cell as if it was at the furthest distance of any cell of its color.
We can work backwards through the distances adjusting the "effective distance" of each cell. We can increase the effective distance of a cell to be the maximum possible less than the effective distance of any cell that was at a normal distance greater than the normal distance of the cell we are adjusting. But, we also want to make sure that the "effective distance" is a distance where the color of the cell can be taken. So, for each color, we record the normal distances on which the color can be taken, and we reduce the effective distance of a cell to be one of the distances in the cells color list.
This idea allows us to restrict the next move colors to colors that are at an effective distance of 1.
Finally, we note that if we can clear a color, clearing the color is always at least as good as any other move. So if we can clear a color, we choose a single move that clears a color as our sole next move. (This is, at best, a very minor optimization.)
This simple set of ideas allows us to solve 6-color 21x21 boards. 6-color 28x28 boards remain elusive.
posted by Cesium at 17:53
1 Comments:
If you're still interested in this topic, you may want to have a look at my Flood-It clone which includes a solver algorithm, too. In fact, it has two solvers:
- DFS using various strategies
- A* using a strategy that I copied from a competition-winning program.
https://github.com/smack42/ColorFill
My program can solve puzzles up to 15x15 in 6 colors using an exhaustive search, thus finding the optimal solutions. Larger puzzles are solved by the other strategies that use more or less "deep" heuristics.
Post a Comment
<< Home