GPU constraints / incidence, domains, and search
Research settingIndependent
The Sudoku work is a concrete solver architecture: a three-phase CUDA pipeline that combines constraint propagation, a continuous relaxation, and discrete search. Its research question is how to direct parallel effort toward the parts of the constraint graph that can resolve the most remaining choices.
From the research record
Inspect the work
Original figures, recorded values, and explicit model details. Each exhibit identifies its source and what the comparison means.
Three operations inside the CUDA solver
Scroll horizontally to inspect the full table →
| Phase | Representation | Operation | Output used by the next phase |
|---|---|---|---|
| Propagation | Candidate bitmasks | Arc consistency and hidden singles | Reduced candidate domains |
| Relaxation | Softmax probabilities | Continuous energy relaxation | Candidate preferences |
| Search | Discrete assignments | Iterative-deepening depth-first search | A checked assignment or continued search |
This is the architecture described by the solver companion. It does not reuse the inconsistent historical speedup headline or pool kernel latency with batched throughput.
Read the technical figure
Source: Sudoku companion. The partial board and candidate set explain constraint incidence; neither is a benchmark input or measured solver trajectory.
Source: Sudoku companion. The partial board and candidate set explain constraint incidence; neither is a benchmark input or measured solver trajectory.
Supporting detail
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.
Sources, scope, and next question
Solver and manuscript described in the Sudoku companion; historical benchmark comparisons require separation.
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.