Solving Flood-It Puzzles: A Comparison of Tailored A* Search with Declarative Solver Approaches

Philipp von Manteuffel; Benjamin Blankertz

cs.AIOct 22, 2026

Solving Flood-It Puzzles: A Comparison of Tailored A* Search with Declarative Solver Approaches

Authors: Philipp von Manteuffel, Benjamin Blankertz

Organizations: Chair for Neurotechnology Technische Universität Berlin

Abstract

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.

Figures & tables

Figure 5: Regression of solution length from size and colors. The points indicate the different solutions lengths that occurred in randomly generated puzzle instances for the given size and number of colors. The plane is a regression of the solution length ( moves ) from size and colors . Note, that this visualization does not indicate the distributions of moves . Those can be seen in the projections, Appendix A , Fig. 24 and 23 .

Table 1: Prediction of the minimum solution length. (a) The minimum solution length for Flood-It puzzles, predicted by OLS regression from the size (side length of a quadratic grid) and number of colors . In (b) the median across 100 puzzle instances was calculated per size and color. Note, that this is the same data as the OLS was trained on.

Figure 6: For each size and number of colors , 100 Flood-It instances were randomly created. The bar plots show the distribution of the minimum solution lengths for each pair of size and colors . The bar corresponding to the predicted minimum solution length based on a regression from size and color , see Sec. 4.3 , is shown in dark magenta.

Figure 7: A* Enhancements. Comparison of the solution times for different A* configurations in the minimization problem as survival plot. For each time budget on the

x

-axis up to the timeout limit of 120 s, the curves represent the ratio of puzzles solved within that time limit. The values in the legend specify the area under the curve (AUC) as an overall measure of performance.

LBC

uses simply the number of unsolved colors as lower bound, and

LBP

uses Algorithm 1 . LBP-Equiv exploits additionally the equivalence of game states. LBP-Equiv-McPs furthermore uses the “must check – presolved” strategy for pruning. For tie-breaking [

f

h

, lifo] was used in all variants. Data: 99 instances of the training set, see Sec. 5.1 .

Panel of Figure 8 — Figure 8: Comparison of different lower bounds for A*. (a) For each time budget on the $x$ -axis up to the timeout limit of 120 s, the curves represent the ratio of puzzles solved within that time limit. The more sophisticated lower bounds $LBL$ and $LBP$ introduced in Sec. 3.2 are compared to the simple lower bound of the number of unsolved colors ( $LBC$ ). (b) The better two heuristics are compared in a scatter plot. For points below the diagonal, $LBL$ is slower. The minimum solution length of each puzzle instance is color-coded. Note that 20.2% of the instances were not solved by either method. Data: 99 instances of the training set, see Sec. 5.1 .

Panel of Figure 9 — Figure 9: (a) Effect of exploiting equivalence of game states. In ‘Equal’ only exactly equal game states are identified, while in ‘Equiv’ the equivalence of game states is used for pruning the search of A*, see Sec. 3.3 . For points above the diagonal, ‘Equal’ is slower. The minimum solution length of each puzzle instance is color coded. (b) Comparison of tie-breaking strategies. Ties of game states with the same $f$ -value are resolved either by a ‘lifo’ selection (FLifo), or choosing the lowest $h$ value and on the third level either a ‘lifo’ (FHLifo) or a ‘fifo’ (FHFifo) selection, see Sec. 3.4 . Data: 99 instances of the training set, see Sec. 5.1 .

Panel of Figure 10 — Figure 10: Different solver engines for SAT. Comparison of the solution times when using the SAT formulation with different solver engines and constraint variants in the decision problem as survival plot. For each time budget on the $x$ -axis up to the timeout limit of 120 s, the curves represent the ratio of puzzles solved within that time limit. The values in the legend specify the area under the curve (AUC) as an overall measure of performance. Data: 99 instances of the training set, see Sec. 5.1 .

Panel of Figure 11 — Figure 11: Flood-It decision problem. Comparison of the solution times for the solvers in the decision problem as survival plot. For each time budget on the $x$ -axis up to the timeout limit of 120 s, the curves represent the ratio of puzzles solved within that time limit. The scaling on the $x$ -axis is linear in (a) and logarithmic in (b) . Note, that the $y$ -axis starts at $0.5$ in the left subplot. Data: 233 instances of the test set, see Sec. 5.1 .

Figure 12: Flood-It minimization problem. Comparison of the solution times for the solvers in the minimization problem as survival plot. For each time budget on the

x

-axis up to the timeout limit of 120 s, the curves represent the ratio of puzzles solved within that time limit. Data: 233 instances of the test set, see Sec. 5.1 .

Figure 13: Scatter plot of solution times for the minimization problem using the A* and the SAT-Solver. Each puzzle instance is one data point, and their solution times for A* are on the

x

- and for SAT on the

y

-axis. For points above the diagonal line, A* finds the solution faster, while points below correspond to puzzles that were solved faster with SAT. Puzzle instances are color-coded by the minimum solution length. Dots that are crossed out were not within the time limit of 1200 s by at least one of the solvers. (Note that the survival plot in Fig. 12 has a different time limit of 120 s.) Data: 233 instances of the test set, see Sec. 5.1 .

Appendix figures & tables11 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 14: The graph compares the overall performance of the different SAT solvers available in PySAT on 99 Flood-It instances as a survival plot. For the time budget on the

x

-axis up to two minutes, the curves show the proportion of the puzzles solved. As an overall performance measure, we use the area under the curve (AUC). The values for each solver are given in the legend. For better display, only the range 0.5 to 1 is shown on the

y

-axis. The abbreviations for the solver are: g42 : Glucose 4.2.1, cd19 : CaDiCaL 1.9.5, gc4 : Gluecard 4.1, mgh : MinisatGH, mcm : MapleCM, cms : CryptoMinisat; see the main text for references. Moreover, ‘v1’ refers to the first SAT formulation given in Sec. 4 and ‘pc’ indicates that the optional constraints (P) and (C) have been used.

Figure 15: The coefficient of variation (CV) was calculated across 10 runs for each solver and each puzzle of the training set. The results for six different SAT solvers are shown as box plots with an overlay of individual data points.

Panel of Figure 16 — Figure 16: This graph shows the performance of the two SAT formulations for the decision problem side-by-side. The first formulation is described in Sec. 4 and the second in Sec. A.1 .

Figure 17: Distribution of solving times. Five selected instances have been solved repeatedly in ten runs using the eight different SAT formulations. The distribution of the ten solving times is shown as violinplot for each solver and instance. The numbers on top are the coefficients of variation.

Figure 18: Coefficient of variation (CV) across repeated runs. The same puzzle instances have been solved using different formulations in the SAT solver to calculate CVs. The boxplot of CVs is shown with an overlay of the individual CVs for each instance. A number above a box shows the median CV. Data: 99 Flood-It instances of the training set.

Figure 19: Comparison of the best constraint (CP) and binary integer programming (BIP) version of each solver (Z3, Gurobi, CPLEX) for the decision problem as survival plot. For each time budget on the

x

Figure 20: Variation in solving time for fixed ‘complexity’. Each plot shows data for a fixed combination of puzzle size and number of colors , which can be seen as a measure of (potential) complexity of the puzzle. The violin plots show the distribution of the solution times for the decision problem.

Figure 21: Solving time when using different values for solution length

T

. For ten Flood-It instances, the solution time with the SAT decision solver was measured for solution lengths

T=\texttt{T}_{\text{min}}-5,\dots,\texttt{T}_{\text{min}}+5

, where

\texttt{T}_{\text{min}}

is the minimum solution length. (Just to clarify: The solvers return ‘ unsolvable ’ for

T<\texttt{T}_{\text{min}}

and might return a suboptimal solution when

T>\texttt{T}_{\text{min}}

Panel of Figure 22 — Figure 22: Average solving time when using different values for solution length $T$ . The graph shows the solving times of Fig. 21 averaged across the 10 puzzle instances. Note the different scaling in the subfigures.

Figure 23: Regression of solution length projected to colors. The plots are projections of the data from Fig. 5 to the different numbers of colors. Each plot shows the distribution of the solution length for the indicated puzzle size as violin plots with an overlay of individual data points. Horizontal lines are shown at quartiles and median. The red line is a projection of the regression plane, see Fig. 5 .

Figure 24: Regression of solution length projected to size. The plots are projections of the data from Fig. 5 to the different puzzle sizes. Each plot shows the distribution of the solution length for the indicated number of colors as violin plots with an overlay of individual data points. Horizontal lines are shown at quartiles and median. The red line is a projection of the regression plane, see Fig. 5 .

Tree Search

Tree Search explores branching sequences of actions or decisions to find high-quality solutions under limits on time, memory, or computation.

See all 57 papers

Oct 21, 2026

An Exact 93-Move Solution to a Nonlocal Crystal-Exchange Puzzle

We determine the minimum number of directional commands needed to solve alevel of Order of the Sinking Star, modeled as a crystal-exchangepuzzle on an 11*11 board. A command swapsthe player with the nearest crystal in the selected row or column, regardlessof distance; only an empty ray permits an ordinary unit walk. Two gates admitthe player to the exit exactly while all sixteen crystals occupy their targetcells. We give an explicit 93-command solution and exclude every shortersolution by an exact, cost-bounded breadth-first search. The search representsa position by its seventeen occupied cells and one active cell. Its admissibleheuristic partitions command costs between a compressed core abstraction andresidual motion, strengthened by a necessary activation detour and a cornervisit condition. The completed computation retained 605,349,215 occupied setsand 1,863,925,136 states. We prove the reductions and pruning conditions,describe the exact storage scheme, and provide source code, execution logs,and a reproduction driver. The result is a computer-assisted proof for thespecified instance, with an explicit implementation trust boundary.

Zilai Wang

Topic pending

Ask PDF

Sep 20, 2026

Expansion Counts under Standard A* Tie-Breaking Strategies on the Final Plateau

In the A* search algorithm, the tie-breaking strategies for nodes with the same

f

-value determines which states A* expands on the final

f

-layer. For nine standard tie-breaking strategies, we show that under a consistent heuristic, every pair has positive-cost instances favoring each strategy over the other by an arbitrarily large additive expansion gap. A parameterized unit-cost grid example also gives unbounded expansion-count ratios between low-

h

with FIFO and LIFO. In unit-cost search with

h > 0

at non-goals, exact heuristic values near the goal lead to complementary extremal results: low-

h

minimizes the number of remaining expansions from a common configuration within the perfect region, while high-

h

maximizes the total number of expansions when every final-plateau state with

h=1

is a goal predecessor. Finally, with the evaluation function

f_α = g + αh

, when

h>0

at non-goals, every heuristic weight

0 \leq α<1

eliminates tie-breaking sensitivity, and all tie-breaking strategies expand the same set of states.

Alex Fukunaga

The University of Tokyo

Tree Search

Ask PDF

Sep 6, 2026

Probabilistic Focal Search: Accelerating Bounded-Suboptimal Search via Lower-Bound Advancement

Bounded-suboptimal search seeks a solution within a factor

w

of optimal while reducing search effort. Focal Search (FS) uses heuristic guidance within FOCAL, the frontier nodes eligible under the threshold

w f_{\min}

, but its deterministic policy may leave

f_{\min}

unchanged for many expansions. We introduce Probabilistic Focal Search (PFS), which follows the FS guided choice with probability

p

and expands a minimum-

f

OPEN node with probability

1-p

. The latter branch encourages the lower bound to advance, enlarging FOCAL and admitting nodes that may lead to feasible solutions. By balancing guidance and lower-bound advancement, this mechanism can reduce time to a bounded solution when progress is limited by delayed FOCAL admission. As a secondary transfer experiment, we apply the same scheduler to Dynamic Potential Search, yielding Probabilistic Dynamic Potential Search (PDPS). We benchmark PFS against FS on N-Puzzle, Pancake Sorting, and the Traveling Salesperson Problem (TSP), and evaluate its anytime extension on the Generalized Covering TSP (GCTSP), using multiple

w

and

p

values. Across these benchmarks, the largest gains occur when long

f_{\min}

plateaus delay useful FOCAL admissions; in such settings, the probabilistic factor may reduce node expansions by about 90% or more (e.g., on N-Puzzle and TSP). For the anytime algorithm family, Anytime Probabilistic Focal Search (APFS) outperforms all tested algorithms in evaluating anytime methods on GCTSP. We also observe that the benefit is smaller when the deterministic search already advances efficiently (e.g., Pancake Sorting), indicating that the probabilistic factor is most useful when FOCAL admission is a search bottleneck. The PDPS transfer shows that the mechanism also transfers to potential guidance, although its common-success effects remain domain- and bound-dependent.

Minh Vu Duc, Trung Le Huu, Hà Minh Hoàng +3

SLSCM Lab, National Economics University · University of Warwick · DataOpt Lab, National Economics University +2

Tree Search

Ask PDF

Abstract

Tree Search

Explore similar work

An Exact 93-Move Solution to a Nonlocal Crystal-Exchange Puzzle

Expansion Counts under Standard A* Tie-Breaking Strategies on the Final Plateau

Probabilistic Focal Search: Accelerating Bounded-Suboptimal Search via Lower-Bound Advancement