Solving stone flood game update#

5 Bealbeach City → Gym #4 (Vinoville Town).

3 Returning to Moki Town → Gym #2 (Burole Town).

I think this means that it's safe to fill it sooner rather than later.ģ) The greedy algorithm for neighbor field count makes sense for a 2 color map. It cannot be bundled with any other fills. But I'm not convinced that this is a simple graph traversal, since changing to a color shared by 2 neighbors visits 2 nodes, and not 1.Ĭolor elimination should probably play some role in the heuristic.ġ) It is never correct to fill with a color that is not already on the graph.Ģ) If there is one color field with a unique color, at least one fill will be required for it. The color 1 has the largest perimeter by any measure, but the color 2 is the optimal choice. Maybe the tie-breaker goes to the color that's common to the most groups on the map.Īnyway, note that the goal of the game is to reduce the number of distinct color fields and not to maximize the perimeter, as different color schemes can occasionally make a larger field a sub-optimal choice. I'm not sure if there needs to be a tie-breaker for when multiple fields have the same weight though. Overall, I think this should actually compute in O(n log n) time, where n is the number of pixels and the log(n) only comes from maintaining the sorted list of weights.

Solving stone flood game update#

Merge the collections, and update the sort for all the collections affected by the merge (all the new neighbors of the merged collection). The largest count of neighboring collections with a single color is the weight of this collection.ģ) Take the collection with the highest count of neighbors with a single color, and fill it to that color. You're trying to reduce the number of color fields to 1, so reducing more color fields earlier shouldn't be any less efficient than reducing fewer earlier.ġ) Define a collection of existing like-colored groups.Ģ) For each collection, count the number of neighboring collections by color.

I'm not certain, but I'm fairly sure that this could be solved greedily. My solver is not super-fast but it can find a guaranteed optimal solution in no more than a couple minutes. Once we know which midpoint state is on the path to an optimal solution, the program can perform DFS using that midpoint state as a goal (and pruning any path that selects a square not in the midpoint.) Or, it might be feasible to just build up the paths in the BFS steps, at the cost of some additional memory. The other pruning technique which proved to be key to a fast solver is simply checking whether there are more than N colors left, if you are N or fewer steps away from the current best solution. (A heuristic applied to the order of the subtrees examined in the second step would probably help some, as well.) Both of these BFS searches can be pruned by eliminating states found in previous depths, and the latter search can be bounded by the depth of the best-known solution. Then, I examine each state at the midpoint depth and perform a new BFS starting with that as the root. The search strategy I took is to perform BFS up to a 'midpoint' depth where the number of states would become infeasible, somewhere between 11 and 13 moves works best.

(With a depth-first strategy it is therefore important to maintain a history to avoid a redundant work.) The effective branching factor seems closer to 3 than to 5. I observed that the search space actually grows much slower than the branching factor of the search tree, because there are quite a lot of duplicate positions. I took a slightly different approach because I was interested in finding the provably optimal path, not just a 'good' one. Combining a good heuristic with bounded DFS (or BFS with lookahead) results in solutions that are quite fast for the standard 14x14 grid. Heuristics look at the number of squares and distribution of colors left unchosen, or the distance to the 'farthest away' square. Most of the solvers out there are heuristic and do not guarantee optimality. I have been working on this, and after I got my solver working I took a look at the approaches others had taken.