Solving Flood-It Puzzles: A Comparison of Tailored A* Search with Declarative Solver Approaches
This paper addresses the NP-hard Flood-It minimization and decision problems on colored graphs. The authors develop a tailored A* search using novel game-state equivalences, lower-bound heuristics, and pruning rules, and compare it against SAT, ILP, and CP formulations. The study matters because it provides the first systematic empirical comparison of exact solvers for Flood-It, showing that domain-informed search dominates on most modest instances while SAT scales better on the hardest cases.
The paper delivers a solid engineering contribution with limited theoretical novelty. The tailored A* convincingly outperforms generic declarative solvers on roughly 75% of minimization instances, yet the comparison is structurally tilted because SAT must solve iterative decision problems while A* is natively optimized for minimization. The experimental protocol is clean with a held-out test set, though some cross-paradigm comparisons involve different time horizons and solver configurations that complicate a fair assessment. As stated, "A* search is the fastest in finding a minimal solution in about 75% of the Flood-It instances tested." Conversely, "with increasing complexity, quantified by the minimum solution length, the SAT-based approach outperforms A*."
The domain-specific A* optimizations are well-motivated and rigorously evaluated. The new game-state equivalence in Theorem 2.11 is formally proved and practically impactful, yielding search speedups up to 10x, while the $LBP$ heuristic based on safe and combined moves achieves speedups up to 100x over simpler bounds. The systematic ablation of heuristics, equivalences, and tie-breaking strategies on a dedicated training set before evaluating on a held-out test set is methodologically sound. Specifically, "The lower bound LBP (Algorithm 1), which takes safe moves into account additionally to the level structure, results in a speedup of up to factor 100." On equivalences, the authors report that "This results in more solved test instances and a faster solving time in 94.9% of the cases with a speedup factor of up to 10."
Several issues weaken the generality and comparability of the results. First, the strategically derived pruning rules (Op, Mc, Ps) provided negligible benefit once the strong $LBP$ heuristic and equivalence pruning were active, suggesting their marginal practical value. Second, the comparison between A* and SAT for minimization is inherently asymmetric: A* is architecturally designed for optimization, whereas SAT requires an iterative probe sequence, making the head-to-head framing somewhat misleading. Third, the ILP and CP results are barely reported in the main text and dismissed as uncompetitive without detailed analysis, leaving open whether poor performance stems from weak formulations or lack of solver tuning. This is especially pertinent because the SAT, ILP and CP formulations "are logically equivalent," yet their realized performance differed drastically across engines. On pruning the authors note that "In our simulations, the benefit of the pruning strategies of Sec. 3.1 vanished when the other optimizations (equivalent game states and LBP) are employed." Regarding the surprise that SAT beat ILP/CP on minimization, the conclusion offers only a post-hoc rationalization: "A potential reason for this outcome is that the minimization formulation requires a larger variable array that encompasses the largest assumed solution length."
The internal evidence supports the claim that A* with $LBP$ and equivalences is best for small-to-mid instances, and that SAT overtakes for high complexity. However, the comparison to prior work is thin. The paper positions itself as the first systematic comparison, yet the SAT formulation from van Stiphout et al. is reported to be "inferior to the direct formulation in our experiments" without deep architectural analysis, and the popular GitHub implementation by Puchert is mentioned but never directly benchmarked. The linear regression for solution-length prediction, $\text{predicted solution length} = 2.4 \cdot \text{colors} + 1.4 \cdot \text{size} - 14.3$, is trained and evaluated on the same random distribution, and the authors themselves concede that "there is also evidence that the actual relationship is nonlinear," which undermines confidence in using it to bound universal solver instances.
Reproducibility is mixed. The experimental setup is documented clearly: board sizes, color counts, training and test splits, hardware details, and solver versions are all stated. However, no persistent code repository or artifact is linked, and the exact constraint scripts and A* hyperparameters are not publicly archived. The paper states that "Experiments were run on a MacBook Pro with an M2 Max chip and 96 GB memory," and that "The A* approach was implemented in C++, whereas we used Python interfaces to different solvers," but without the actual encodings and build instructions an independent team would need substantial engineering to reproduce the reported survival curves and crossing points.
We present an optimized approach for finding minimal move sequences to solve Flood-It puzzles using A* search and compare it with approaches using SAT, Integer Programming, and Constraint Programming solvers. The performance of A* search is considerably improved by using an appropriate heuristic and sophisticated equivalences of game states to limit the search space. Each aspect is systematically evaluated, providing insights that generalize to other problems. By comparing the best variant of each approach, the A* search is the fastest in finding a minimal solution in about 75 % of the Flood-It instances tested. This result is in line with our expectation since A* specifically looks for a minimum solution. In contrast, the SAT-based approach is designed to solve the decision problem of whether a solution with a given length exists. An iterative search is required to determine a minimum solution length using a SAT-based approach. However, with increasing complexity, quantified by the minimum solution length, the SAT-based approach outperforms A*. We also compared the different approaches to the decision problem, where A* again performed best for the largest number of puzzles. Here, again, SAT supersedes A* for higher complexities, albeit with a lower crossing point.
Pick a starting point or write your own. Challenges run in the background, so you can keep reading while the AI investigates.
No challenges yet. Disagree with the review? Ask the AI to revisit a specific claim.