Metraipolis › archive › dc_fbc2b508ff95

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

Source: arXiv (en)
Original: https://arxiv.org/abs/2610.31100
License (as archived): CC0-1.0
Archived: 2026-10-23T15:13:14.896Z
SHA-256 of the archived text: b26e04787ae4d45eddbfbebd3677dc17f727990a2b9834b2325429405de3f782
Stable URL of this page: https://metraipolis.com/documento/dc_fbc2b508ff95

How to cite

Solving Flood-It Puzzles: A Comparison of Tailored A* Search with Declarative Solver Approaches — arXiv:2610.31100 — arXiv (en), https://arxiv.org/abs/2610.31100 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_fbc2b508ff95 (Metraipolis archive dc_fbc2b508ff95, sha256 b26e04787ae4d45eddbfbebd3677dc17f727990a2b9834b2325429405de3f782)

BibTeX

@misc{dcfbc2b508ff95,
  title = {Solving Flood-It Puzzles: A Comparison of Tailored A* Search with Declarative Solver Approaches — arXiv:2610.31100},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.31100},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_fbc2b508ff95; sha256 b26e04787ae4d45eddbfbebd3677dc17f727990a2b9834b2325429405de3f782},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.31100. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.AI, nuovi lavori del giorno).
Categorie arXiv: Artificial Intelligence (cs.AI).
Pagina del lavoro: https://arxiv.org/abs/2610.31100 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-23T15:09:08.435Z dalla pagina https://arxiv.org/list/cs.AI/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).