CS Paper Radar

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

Philipp von Manteuffel, Benjamin Blankertz

cs.AI ·submitted 2026-10-22 11:13 UTC · v1

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.

Comment
22 pages main text, 35 pages in total; 13 figures plus 12 figures in the appendix

Closest papers

Nearest neighbours by meaning across the whole index.

Codoku: Renewable Program-Reasoning Challenges for Frontier Coding Agents

cs.SE cs.AI ·2026-09-28 ·Cong Li, Hao Sun, Zenan Li, Zhendong Su
benchmarkcode/data similarity 0.61
Abstract

Existing program-reasoning benchmarks ask large language models to predict a program's behavior on a given input. Coding agents break two assumptions on which these benchmarks rest: an agent can recover the answer by executing the program instead of reasoning about it, and fixed task sets drawn from existing programs are increasingly exposed to contamination, yet costly to renew. We introduce Codoku (code sudoku), a renewable benchmark in which a solver fills typed cells in a partial program to satisfy global static and dynamic constraints, such as a prescribed control-flow graph and execution path. Because a partial program cannot be executed and valid fillings are sparse in an exponentially large space of interdependent choices, neither tool use nor enumeration can substitute for program reasoning. Puzzles are synthesized from scratch via semantic reification, so fresh puzzles of controllable complexity can be generated on demand, each with a witness that guarantees solvability. We evaluate five frontier models on 300 puzzles through a coding agent free to use any tool within a fixed budget. Small puzzles already challenge open-weight models, whereas even proprietary models solve only about half of the large ones. Codoku thus offers a renewable testbed for program reasoning that can keep pace with rapidly improving coding agents. GitHub: https://github.com/connglli/Codoku.

0.42

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

cs.AI math.CO ·2026-10-21 ·Zilai Wang
theoryunusual similarity 0.59
Abstract

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.

0.32

Tactix: Towards a Programmable Strategy Interface for Flexible SAT Solving

cs.LO cs.AImath.LO ·2026-10-17 ·Haoze Wu, André Schidler, Armin Biere, Nina Narodytska
similarity 0.57
Abstract

Modern SAT solvers combine a rich repertoire of proof rules with sophisticated strategies that determine when and how to apply them. Often, the internal implementations are tightly coupled to particular strategies, making it inconvenient to define new strategies without changing solver internals. We present Tactix, a proof-producing sequential CDCL solver that incorporates a wide range of techniques in state-of-the-art solvers with a clean separation of proof rules from solving strategies. This separation enables a public interface through which users can invoke particular techniques, observe their effects, and program a wide range of solving strategies. The default strategy of Tactix is programmable over this interface and outperforms state-of-the-art solvers on benchmarks from the 2024--2026 SAT Competitions. We also use the interface to develop novel strategies tailored to challenging benchmarks from two application domains, which led to performance gains over strong baselines. We intend Tactix to serve as an infrastructure for designing and evaluating novel solving strategies. Finally, we also present a self-study of the AI-assisted development process behind Tactix.

0.08

Improved Deterministic Algorithms for $k$-SAT: Generalization of Chains and Recurrence Proof

cs.DS ·2026-11-12 ·Binbin Cui, S. Cliff Liu, Yongrui Yu
similarity 0.57
Abstract

We present a deterministic algorithm for 3-SAT running in $1.32736^n$ time. The algorithm is built on a branching-and-chain framework augmented with a polynomial-time expansion procedure that joins short chains through additional clauses to form bounded-size blocks, which impose stronger constraints on the assignment space. After branching, the algorithm chooses between derandomized local search guided by the block structure and enumeration of block assignments together with selected port variables, reducing the remaining formula to 2-SAT. A weighted analysis of branching, partial-assignment, and local-search costs, together with inductive bounds for chains and block interactions, establishes the running-time guarantee. The framework is self-contained and also offers guidance for practical SAT solver design by identifying useful clause-overlap structures and suggesting when to switch between local-search and reduction-based strategies.

0.27

The Case for Automated Hyperspecialization: Evidence from SAT

cs.SE cs.LO ·2026-09-13 ·Harrison Green, Claire Le Goues, Fraser Brown
benchmark similarity 0.57
Abstract

The software status quo is to use one system to process many different kinds of inputs. In contrast, we propose hyperspecialization: creating new software that is optimized for a single class of inputs. Hyperspecializing manually is anywhere from expensive to impossible. We conjecture that coding agents make automated hyperspecialization cheap, effective, and safe for problems with measurable performance and checkable output. This paper explores one such problem, SAT solving, by synthesizing hundreds of workload-specific SAT solvers at an average cost of \$37 each. Our specialists outperform their competition-winning, general-purpose cousins by 5$\times$ on average, and by over $10\times$ on a quarter of benchmark families. A general-purpose solver constructed from over a hundred of our prototype hyperspecialists won the SAT track at the 2026 SAT Competition.

0.40

Learning to Rank Propagators in Constraint Programming

cs.LG cs.AI ·2026-11-08 ·Matija Lojović, Mladen Nikolić
similarity 0.56
Abstract

The order in which propagators are executed can substantially affect the performance of constraint programming solvers, yet propagator priorities are typically determined by fixed, manually designed heuristics. In this work, we explore learning instance-dependent propagator priorities from static problem features. We formulate the task as a learning-to-rank problem, addressing the challenge that the quality of a priority assignment can be measured through solver runtime, while the desired priorities of individual propagators are not directly observable. A self-attention-based model jointly scores the propagators present in an instance and is trained using pairwise preferences derived from solver runtimes measured under randomized propagator priority assignments, with a Plackett-Luce-based ranking objective. Predicted rankings are mapped to the discrete priority levels of the Choco solver before search begins, without modifying its propagation or search procedures. We evaluate the approach on XCSP3 instances and demonstrate that propagator ordering can have a substantial impact on solving time. On a test set of 698 instances, picked out as most difficult by problem class, the learned priorities increase the number of solved instances from 634 to 654, reduce median solver runtime by 27.93%, and reduce aggregate penalized runtime (PAR1) by 12.65% compared with Choco's default priorities. We further observe that improvements vary across problem classes and show that a simple policy selecting between learned and default priorities further increases the number of solved instances. These results demonstrate the potential of learning instance-dependent propagator priorities to improve constraint programming performance, particularly on difficult instances.

0.25

Direct Pass@$k$ Optimization for Thought Pruning: Balancing Quality and Diversity in Test-Time Reasoning

cs.AI cs.CL ·2026-10-22 ·Mahdi Salmani, Adel Javanmard, Devansh Gupta, Meisam Razaviyayn
similarity 0.56
Abstract

Test-time scaling has emerged as a key inference strategy for reasoning models, where a model generates a large number of candidate solutions in the hope of finding at least one correct solution. Running all candidate solutions to completion can be computationally demanding, so recent work prunes the candidate pool after generating only a short prefix, committing further computation only to the surviving candidates. Existing pruning strategies divide broadly into two categories: Quality-based methods assign a score to each partial solution and discard those predicted to ultimately lead to an incorrect final solution, while diversity-based methods select partial solutions that follow different reasoning trajectories and are therefore likely to cover different final solutions. The tension between these two objectives is an instance of exploration versus exploitation, yet little to no prior work on pruning exposes this trade-off directly, let alone optimizes it. In this paper, we introduce a pruning procedure that addresses this trade-off directly by optimizing pass@$k$ over the selected solution pool. In particular, it chooses the pool to maximize the probability that at least one of its partial solutions, when continued to completion, yields a correct answer. Because this objective simultaneously rewards high-quality partial solutions and penalizes redundancy among them, quality and diversity are naturally balanced by the criterion itself rather than through separate ad-hoc design choices. On eight open-weight reasoning models, our method outperforms existing quality-based and diversity-based pruning strategies. The gains are particularly pronounced when the pruning procedure keeps a moderate number of partial solutions for continued generation, highlighting the value of directly balancing quality and diversity during pruning.

0.21

A Non-CDCL SAT Solver with Early Conflict Detection: The Watched-Literal-Based CSFLOC Solver

cs.LO ·2026-08-25 ·Gábor Kusper
published similarity 0.56
Abstract · In Proceedings AFL 2026, arXiv:2608.23071

CSFLOC is a non-CDCL SAT decision procedure based on counting subsumed full-length ordered clauses. The classical CSFLOC loop traverses the ordered space of full-length clauses by a monotone counter: if the current full-length clause is not subsumed by the input formula, its negation is a satisfying assignment; otherwise, a subsuming clause determines a counter jump. The main bottleneck is the repeated search for such a subsuming clause. This paper presents CSFLOC-WL, and its current implementation CSFLOC-WL3, in which this search is replaced by watched-literal prefix propagation over the negation of the current full-length clause represented by the counter. The central mechanism is early conflict detection: if propagation under a common prefix derives opposite unit consequences for the same variable, then the two reason clauses are resolved immediately and the resolvent is used as a new counter-jump cause. The resulting solver is not a CDCL solver: it has no CDCL decision tree, no restart policy, and no first-UIP backjumping loop. It remains a counter-guided full-length-clause-counting solver, but it imports the watched-literal data structure and reason clauses as engineering tools for discovering jumps. Experiments on selected UNSAT SATLIB instances compare CSFLOC-WL3 with CSFLOC21TU and CaDiCaL 3.0.0. The results are mixed: CSFLOC-WL3 is strong on several random 3-SAT instances near the random-3-SAT satisfiability threshold, whereas CSFLOC21TU remains faster on several structured cases, apparently because it contains a more mature cache mechanism that is not yet present in CSFLOC-WL3.

0.37