The first idea that comes to mind is generating all possible sequences of no more than 25 steps. Considering the large number of configurations, we are constrained to limiting the number of steps (e.g. no more than 5) through which we "look ahead" and plan accordingly.
This way, for any board configuration, we want to define the cost of one step, and try to somehow bring it to a minimum.
The notion of a "cost" can be defined in several ways:
- the number of connected components (most important)
- the number of edge cells that are visited
- the number of edges reached (least important)
By merging all three heuristics, we can develop a strategy that is good enough to pass most test cases.
However, there are still some tests where our method exceeds the 25-step limit. In this situation, we keep track of the first 25 steps, choose a random step where we try a different color, and rebuild the configuration from there on. If the sequence is still too long, we go back to the previous step and apply the same idea.
