CS Paper Radar

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

Zilai Wang

cs.AI math.CO ·submitted 2026-10-21 09:49 UTC · v1
theoryunusual

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.

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.AI ·2026-10-22 ·Philipp von Manteuffel, Benjamin Blankertz
similarity 0.59
Abstract · 22 pages main text, 35 pages in total; 13 figures plus 12 figures in the appendix

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.

0.32

Bellman Search in Arbitrary Finite Dimension: A Self-Similar Cell Theorem and Effective Computability of Planar Shoreline Search

cs.CG math.MGmath.OC ·2026-08-29 ·Florentin Koch
theory similarity 0.54
Abstract · 23 pages, 1 figure. English revision 8.3

A shoreline-search path starts at the origin and must meet an unknown affine line, without knowing either its normal or its distance. We first establish a self-similar reduction theorem for homogeneous search problems whose historical information is a record profile updated by pointwise maximum. Two quasi-returns of the normalized state delimit a block that renews the required profile by itself; a short connector closes this block into a cell. Every finite-ratio path can therefore be approximated, with arbitrarily small loss, by repetitions of a single cell at all scales. The main chain is then made effective. A finite coding of the state space computably bounds the scale factor and normalized length of a nearly optimal cell. For planar Shoreline search, the support function of the convex hull gives an exact cell functional. A one-sided polygonalization then reduces the problem to a computable number of vertices, after which quantifier elimination decides whether a polygonal cell exists below a rational threshold. It follows that the optimal deterministic planar Shoreline value $C_2^*$ is a computable real: for every rational $ε>0$, an algorithm terminates with a rational interval of width at most $ε$ containing $C_2^*$. Additional results---sliding memory, Bellman transitions, deadlines, geometric filters, and relative equilibria---are presented separately as a toolbox for certified computation and for the study of spiral rigidity; they are not used in the computability proof.

0.61

H-BRICK: Hierarchical Boundary Reachability Index with Compressed Kleene Closure for Directed Grid Graphs

cs.RO ·2026-11-05 ·Tolga Özaslan, Elif A. Özaslan
theory similarity 0.51
Abstract

Repeated directed reachability queries arise in online path planning, task-agent allocation, and swarm control on static grid maps, where reachability is asymmetric and full transitive closure is storage-prohibitive. We introduce H-BRICK, a Hierarchical Boundary Reachability Index with Compressed Kleene closure for exact cell-to-cell queries on directed grid graphs. H-BRICK partitions the graph into tiles, computes a local Boolean Kleene closure within each tile, and projects it onto the tile's boundary ports. The resulting directed port-to-port summaries are then composed recursively across shared interfaces up to a single root covering the graph. We prove algebraically that the construction is exact: in the Boolean Kleene algebra of binary relations, every composed summary equals the boundary projection of the regional reflexive transitive closure, and every cell-to-cell query agrees with reachability in the original graph. Experiments on directed grid graphs across diverse map topologies compare H-BRICK against directed search and component-based baselines, and compare its storage requirements against full transitive closure. A batched reachability evaluation further demonstrates that sharing endpoint lifts across many-source/many-target queries amortizes hierarchical traversal and, at k=64, yields a 5.0x-22.9x throughput improvement over the scalar query loop. The results show that hierarchical boundary compression is most advantageous in query-intensive spatial graphs where online search traverses large reachable regions and the hierarchy maintains compact boundary interfaces.

0.37

MeshSIPP: Efficient Lattice Planning in Dynamic Environment

cs.AI cs.RO ·2026-10-07 ·Marat Agranovskiy, Konstantin Yakovlev
benchmarktheory similarity 0.51
Abstract

Autonomous navigation in dynamic environments requires computing spatiotemporal trajectories that satisfy non-holonomic motion constraints. When the trajectories of the moving obstacles are predictable or known, a promising approach is to rely on the combination of state lattices constructed from precomputed feasible motion primitives and Safe Interval Path Planning -- a search-based algorithm with strong theoretical guarantees. While this approach yields feasible paths, the rich primitive sets needed for smooth navigation induce a large branching factor, which becomes costly when coupled with time-dependent obstacle intervals. To this end, we present MeshSIPP, an efficient planner that removes the computational bottleneck by exploiting the fact that many primitives sweep the same regions and can therefore be validated together. MeshSIPP propagates primitives as spatial bundles, screens them with lightweight bounding-interval checks, and defers the expensive exact departure-time search until a primitive reaches its terminal state. A time-aware pruning rule additionally discards redundant space-time branches early in the search. We prove that the resulting search is complete and optimal. Extensive experiments over more than 6,000 benchmark instances and real-time ROS~2 simulations show that MeshSIPP achieves up to a 3$\times$ speedup over state-of-the-art spatiotemporal planners.

0.18

Sowing the Seeds of Intractability: Kalah is PSPACE-complete

cs.CC cs.GTmath.CO ·2026-11-12 ·Ethan Dickey, Ethan Mader
similarity 0.50
Abstract · 55 pages, 6 figures, 5 tables

Kalah is a classic two-player game in the mancala family of sowing games. Computers have solved several standard-size starting positions, but the complexity of the game on boards of growing size has remained open. We study the natural generalization in which the number of pits per side is part of the input and an arbitrary position is given, with the stone counts given in unary. We show that deciding whether a designated player can force a win from such a position is PSPACE-complete. The hard positions have Alice to move first and both stores initially empty. The same positions are hard under either common convention for capture opposite an empty pit, and with or without the bonus rule, which gives a player another turn when the last stone is sown into their own store. We introduce Line Kalah as an intermediate problem, a game on a line in which stones that leave the line effectively disappear and Alice must save each of her target pits before Bob captures it, and we reduce quantified Boolean formulas to it. The reduction uses a set of sequential timer piles whose last stones approach a group of targets, forcing Alice to choose between two captures in order to set the truth value of a variable, and a final capture gadget to test a clause chosen by Bob (only one is needed adversarially). Since either player may move any pile at any time, the stages are placed so that premature timer firings protect earlier potential targets. For a true formula, Alice's strategy against arbitrary opposing play either gains enough time to save the remaining targets (after Bob deviates from the intended play) or reaches the final test with a correctly encoded, protected input. Finally, the line positions are embedded in Kalah with both stores empty. A separate Bob pit holds the score adjustment, so the winner takes a strict majority of the stones.

0.24

Real-to-Sim Generation: Synthesizing Scenario Programs from Real-World Data via Constraint Solving

cs.PL ·2026-09-20 ·Peishan Huang, Wenmeng Zhang, Yusen Chen, Zhenbang Chen
published similarity 0.50
Abstract · 31 pages, 4 figures, 4 tables. Accepted at OOPSLA 2026, to appear in PACMPL Vol. 10, No. OOPSLA2, Article 395 (DOI: 10.1145/3839527). This i…

The demand for synthetic training data is hindered by the sim-to-real gap, as current data-driven and LLM-based generators often produce physically implausible scenarios. To address this, we propose R2SGEN, a Real-to-Sim framework that synthesizes structured scenario programs from real-world data. To overcome the combinatorial explosion and intractability of monolithic Satisfiability Modulo Theories (SMT) encoding, we introduce a decoupled synthesis strategy. This approach separates the discrete structural program search from continuous geometric resolution using lightweight, atomic SMT constraints. Furthermore, we significantly accelerate the search process by integrating two tailored pruning mechanisms: Common Prefix Abstraction-based pruning for Breadth-First Search and Branch-and-Bound for Depth-First Search. We evaluate R2SGEN on 20 real-world scenes of varying complexity from the nuScenes dataset. Experimental results show that our method guarantees consistency with the input scene and produces substantially lower-cost programs than the LLM-based baselines under the evaluated inputs. Both proposed search paradigms exhibit complementary advantages, proving highly efficient and scalable for high-complexity synthetic data generation.

0.41

Computing Equilibria in Integer Programming Games with Shared Constraints

cs.GT math.OC ·2026-10-03 ·Bainian Hao, Hyunwoo Lee, Robert Hildebrand, Carla Michini
similarity 0.50
Abstract

We develop a cutting-plane algorithm for computing pure Nash equilibria in finite integer games with shared constraints, where a deviation may be feasible against one opponent profile and infeasible against another. Conditional equilibrium inequalities capture this dependence through an explicit activation term. We give affine encodings of costs and activation conditions and prove that the resulting inequalities characterize the equilibrium set exactly. Embedded as lazy constraints in branch-and-cut, they yield the Generalized Zero-Regret algorithm for optimizing a linear objective over exact or approximate equilibria; a bisection procedure maintains certified bounds on the smallest achievable approximation factor. We also prove that, when the conditional polytopes have integral vertices, a concave cost is constant on the minimal face containing an equilibrium strategy, so strict concavity forces vertex strategies; for uniform integer-splittable bin packing, a cost-preserving transformation yields vertex equilibria even without strict concavity. We give formulations for bin packing, network formation, and knapsack games with shared capacities and evaluate the algorithm on 3,300 instances, computing a socially optimal equilibrium on all but 43, certifying nonexistence on 16, and certifying approximation factors within a few percent where no exact equilibrium exists.

0.41

A Minimum Exact Disjunctive Basis for Two-Robot Solvability Profiles

cs.DC cs.ROmath.CO ·2026-10-13 ·Tsukasa Ninomiya, Shota Naito, Naoki Kitamura, Yuichi Sudo, Koichi Wada
theory similarity 0.50
Abstract · 100 pages, 2 figures, 9 tables

We completely characterize the solvability profiles of tasks for two autonomous mobile robots in the plane under variable disorientation, chirality, and rigid movements. The four standard capability models and the schedulers considered here have a known quotient order Q of thirteen computational classes. A task's solvability profile is the set of classes in which it is solvable, and is necessarily an upset of Q. We prove that every upset is realizable and construct a minimum exact disjunctive basis of thirteen concrete tasks. The basis contains one task for each principal upset. For every antichain of Q, the disjunction of the corresponding tasks has profile exactly equal to the union of their profiles. This exactness is not implied by the individual profiles: an algorithm may satisfy different disjuncts in different executions. We establish it by constructing, for every algorithm in each maximal class outside the target union, a single admissible fair execution violating all selected predicates simultaneously. Consequently, the realizable profiles form the entire finite distributive lattice Up(Q): there are exactly 54 profiles, counted by the antichain polynomial 1 + 13z + 24z^2 + 16z^3, and each has a canonical disjunctive representation using at most three principal tasks. We also identify six tasks whose solvability signatures recover every inclusion and incomparability in Q, and prove that six is minimum even among arbitrary separating tasks. Their profiles are precisely the principal upsets generated by the join-irreducible elements of Q. In contrast, any task family generating every profile by exact disjunctions must contain all thirteen principal profiles. Thus our exact disjunctive basis has minimum size and is unique at the profile level.

0.33