GPU constraint solving: propagation, relaxation, and search

The research in context

A constraint satisfaction problem asks for values for a set of variables such that every rule holds at once. Sudoku is a compact example: 81 cells, each with up to nine candidate digits, and 27 all-different constraints over rows, columns and boxes. General constraint satisfaction is NP-complete, so practical solvers combine propagation, which deletes candidates that cannot appear in any solution, with search, which guesses a value and backtracks on contradiction. On a GPU the question becomes one of allocation: thousands of threads are available, and a policy must decide which variables to examine and which branches to explore first.

The deposited manuscript (February 2026) and its public repository, sudoky-energy, describe a CUDA solver with an instance-level gate. A parameter Γ, computed from the amount of assigned structure relative to the largest local constraint density, sends an instance to propagation alone (Γ > 1.0), to all three phases (0.35 < Γ ≤ 1.0), or to propagation followed directly by search (Γ ≤ 0.35). The relaxation phase shrinks its step size where local constraint density is high. The search phase orders values by the local priority and prunes branches with a holonomy-based dead-end test. The manuscript states that minimum-remaining-values, the degree heuristic and checkerboarding are recovered when particular weights are set to zero.

The deposit reports runs on 15-clue extreme Sudoku (66 empty cells, Γ ≈ 0.19, so under the gate the relaxation phase is bypassed) on an NVIDIA GeForce RTX 5070 Laptop GPU with CUDA 13.1. A batch of 65,536 instances was fully solved at about 260,000 puzzles per second. For a single instance it reports 20.4 milliseconds of GPU time including host overhead, against 77.8 milliseconds for its Dancing Links implementation. The project page separately reports a 7.8-millisecond average kernel time, excluding transfers, across 11 well-known hard puzzles. These measure different things and are not combined here.

Three kinds of work inside one solver

The first phase uses bitmasks for arc consistency and hidden-single detection. The second represents candidate choices with softmax probabilities and relaxes an energy objective. The third performs iterative-deepening depth-first search with a structural branch priority. These are distinct operations, so their contributions should be measured separately.

The proposed local priority combines saturation, scarcity, and coupling. A variable’s information-value score includes its neighbors’ local scores and divides by its remaining domain size. This makes the mechanism more specific than the claim that geometry makes puzzles easy: it is a computable proposal for choosing where to propagate or branch.

The timing comparisons need different denominators

The companion mixes batched throughput, individual hard-puzzle latency, CUDA kernel timing, and comparisons against Python, Dancing Links, and an energy-based model. Those are different measurements. Kernel timing excludes transfers; a large batch can amortize costs that a single difficult puzzle cannot.

One published headline is internally inconsistent with its nearby latency table: 313 milliseconds divided by 7.8 milliseconds is about 40, not 40,128. This account therefore preserves the solver design without carrying that speedup headline forward. Finding a solution, proving uniqueness, and demonstrating infeasibility also require separate comparisons.

The next research step

The decisive experiment is an ablation within the same solver: keep propagation and backtracking fixed, then replace the structural priority with minimum-remaining-values and a simple unweighted order. That would identify the scheduling contribution.

Source record

1. Sudoku project material.
2. CSP project material.
3. Curvature-Guided Wavefront Execution for GPU-Accelerated Constraint Satisfaction on the Davis Manifold.

No new experiments are reported in this research note. Figure captions distinguish saved research records, source-model calculations, and explanatory diagrams.