Signed p-adic Residual Encodings of Finite-Domain All-Different Systems with a Sudoku Case Study

Greg Baker

cs.LGSep 13, 2026

Signed p-adic Residual Encodings of Finite-Domain All-Different Systems with a Sudoku Case Study

Authors: Greg Baker

Organizations: School of Computing, Australian National University Canberra, Australia

Abstract

We study signed, weighted affine $p$ -adic residual objectives as native encodings of finite-domain constraints. For primes that separate the finite alphabet, sufficiently weighted positive unary rows pin each coefficient to its allowed set, while negative rows reward unequal endpoints or clause satisfaction. A coordinatewise domination theorem places every global minimiser in the finite domain; there the loss is, up to an additive constant, the all-different conflict count or the negative number of satisfied CNF clauses. Standard Sudoku provides an $81$ -coefficient case study without a one-hot lift. A client-side implementation exposes the generated dataframes, arithmetic, diagnostics, and searches.

Figures & tables

Term used here	Classical reading	Reference
finite-domain all-different system	Finite-domain constraint system in which the variables in each designated scope must take pairwise distinct values	Section 1
dataframe; row; synthetic observation	Tabular presentation of signed weighted affine forms; a row $(\sigma,u,b,\gamma)$ contributes $\sigma\gamma\|u^{\top}x-b\|_{p}$ . Positive rows are penalties and negative rows are bounded rewards	Definition 1
feature vector $u$ ; target $b$	Normal vector and right-hand side defining the affine residual $u^{\top}x-b$	Definition 1
coefficient vector $x$	Optimisation variable in $\mathbb{Z}_{p}^{n}$ ; in the Sudoku model its coordinates are cell values	Definition 1
compiler; compilation	Constructive encoding or reduction from a constraint system to a signed residual objective	Theorem 1
coordinatewise domination	Exact-penalty threshold: each pinning weight exceeds the total interaction weight incident on its coordinate	Theorem 1

Table 1: Correspondence between the applied vocabulary used in this paper and standard mathematical or constraint-programming readings.

Figure 1: A tiny list-colouring instance. The assignment

x_{1}=1

x_{2}=2

x_{3}=3

respects the domains and makes every edge unequal.

Row	$x_{1}$	$x_{2}$	$x_{3}$	Target	Signed weight	Role
$P_{1}$	$1$	$0$	$0$	$1$	$+3$	domain well
$P_{2}$	$1$	$0$	$0$	$2$	$+3$	domain well
$P_{3}$	$0$	$1$	$0$	$2$	$+3$	domain well
$P_{4}$	$0$	$1$	$0$	$3$	$+3$	domain well
$P_{5}$	$0$	$0$	$1$	$1$	$+3$	domain well
$P_{6}$	$0$	$0$	$1$	$3$	$+3$	domain well

Table 2: Dataframe view of Figure 2 . The three coefficient columns form the feature vector, and each row contributes its signed weight times the

5

-adic norm of feature dot coefficient minus target.

Row	Type	Synthetic observation	Role
$P_{1}$	positive	$(+1,e_{1},1,3)$	pin $x_{1}$ to $D_{1}$
$P_{2}$	positive	$(+1,e_{1},2,3)$	pin $x_{1}$ to $D_{1}$
$P_{3}$	positive	$(+1,e_{2},2,3)$	pin $x_{2}$ to $D_{2}$
$P_{4}$	positive	$(+1,e_{2},3,3)$	pin $x_{2}$ to $D_{2}$
$P_{5}$	positive	$(+1,e_{3},1,3)$	pin $x_{3}$ to $D_{3}$
$P_{6}$	positive	$(+1,e_{3},3,3)$	pin $x_{3}$ to $D_{3}$

Figure 2: Synthetic dataset for the toy list-colouring instance in Figure 1 . Here

e_{1},e_{2},e_{3}

denote the standard basis vectors of

\mathbb{Z}^{3}

Coefficient vector $x$	$L_{\mathrm{toy}}(x)$	Proper list-colouring?
$(1,2,1)$	$7$	yes
$(1,2,3)$	$7$	yes
$(1,3,1)$	$7$	yes
$(1,3,3)$	$8$	no
$(2,2,1)$	$8$	no
$(2,2,3)$	$8$	no

Table 3: All eight hyperplanes determined by the domain-pinning rows.

Row	$x_{1}$	$x_{2}$	Target	Signed weight	Role
$C_{1}$	$1$	$0$	$1$	$-1$	reward $(z_{1})$
$C_{2}$	$-1$	$1$	$1$	$-1$	reward $(\neg z_{1}\vee z_{2})$
$U_{1,0}$	$1$	$0$	$0$	$+3$	Boolean well
$U_{1,1}$	$1$	$0$	$1$	$+3$	Boolean well
$U_{2,0}$	$0$	$1$	$0$	$+3$	Boolean well
$U_{2,1}$	$0$	$1$	$1$	$+3$	Boolean well

Table 4: Signed regression dataframe compiled from the two-clause formula

\Phi

. Constraint rows reward nonzero residuals; well rows force Boolean coefficients.

$x$	$(z_{1},z_{2})$	Clauses satisfied	Loss
$(0,0)$	$(\mathrm{true},\mathrm{true})$	$2$	$4$
$(0,1)$	$(\mathrm{true},\mathrm{false})$	$1$	$5$
$(1,0)$	$(\mathrm{false},\mathrm{true})$	$1$	$5$
$(1,1)$	$(\mathrm{false},\mathrm{false})$	$1$	$5$

Table 5: Brute-force regression for

\Phi

Figure 3: The

20

distinct peers of cell

x

: eight cells in the same row, eight in the same column, and four additional cells in the same

3\times 3

box.

Figure 4: Screenshot of https://padic-logic.symmachus.org/ : the Sudoku route after a row-swap run reaches a valid completion. The native $81$ -cell grid, the $1{,}299$ -row signed objective summary, the theoretical-floor equality, and the zero-conflict search result.

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

	Mihara’s forcing theorem	Signed affine compiler here
Base terms	Nonnegative $p$ -adic optimisation concentrated near a product of residue sets	Signed affine residuals that are zero or units on the target finite domain
Pinning condition	One forcing scale $M$ above the base objective’s range on the finite set	Coordinatewise $\lambda_{i}$ above the absolute incident interaction weight
Off-domain control	Concentration plus positive unary forcing	Ultrametric Lipschitz bound for positive and negative interaction rows
Finite-domain role	Preserve the base objective’s optima on $C$	Realise equality, inequality, and forbidden-hyperplane indicators exactly
Main consequence	Positive linear regression NP-hard for each fixed prime	Compact complement encoding and exact minimum-conflict characterisation

Appendix

Table 6: Comparison with Mihara’s generalisation of Baker forcing [ 17 ] . The two results share finite-domain pinning but use different hypotheses to control the remaining objective.

Figure 5: Standard example puzzle used for the heuristic traces.

Figure 6: Seed-

0

row-wise random initialisation (restart

0

), before any swaps.

Step	Row	Swap (columns)	Swap (digits)	Type	Conflicts (before)	(after)
1	5	$7\leftrightarrow 8$	$2\leftrightarrow 6$	best	56	53
2	6	$3\leftrightarrow 6$	$1\leftrightarrow 5$	best	53	49
3	2	$2\leftrightarrow 3$	$2\leftrightarrow 8$	best	49	45
4	4	$7\leftrightarrow 6$	$7\leftrightarrow 4$	random	45	47
5	7	$1\leftrightarrow 5$	$3\leftrightarrow 9$	best	47	40
6	4	$6\leftrightarrow 7$	$7\leftrightarrow 4$	best	40	38

Appendix

Table 7: First eight swap steps for the standard example puzzle (seed

0

). The table records both the swapped column indices and the digits occupying those columns before each move. Rows and columns are

1

-indexed.

Step	Row	Swap (columns)	Conflicts (before)	(after)
1	5	$2\leftrightarrow 8$	56	56
2	6	$7\leftrightarrow 8$	56	56
3	2	$3\leftrightarrow 7$	56	55
4	8	$2\leftrightarrow 8$	55	51
5	4	$2\leftrightarrow 3$	51	50
6	4	$6\leftrightarrow 7$	50	51

Appendix

Table 8: First eight Zubarev-walk swap steps for the standard example puzzle (seed

0

). Rows and columns are

1

-indexed.

Method	Clues	Puzzles	Solved	Median steps	Median time (s)
Stepwise	36	6	6	537.5	0.270
Stepwise	30	6	6	2784	1.315
Stepwise	26	6	6	7040	3.990
Zubarev walk	36	6	6	4533.5	2.091
Zubarev walk	30	6	6	8751.5	3.951
Zubarev walk	26	6	6	9911	4.786

Appendix

Table 9: Descriptive proof-of-concept results on

18

paired, randomly carved puzzles (not uniqueness-checked), using

T=60{,}000

steps and

R=15

restarts. The Zubarev walk uses a linear schedule

\beta_{0}=0.5

\beta_{1}=6.0

Figure 7: Conflict trajectory for the stepwise row-swap heuristic on the paired-table

30

-clue instance with puzzle seed

115642242

(solve seed

2738956839

), from the row-wise random initialisation on restart

0

Experiment	Setting	Solved	Summary
E1	Greedy cell-swap on $15$ primes, $50$ puzzles, $3$ random initialisations per puzzle–prime pair ( $2250$ runs)	$0/2250$	Mean lift $0.003$ ; mean $12.5$ steps
E2 greedy	Greedy cell-swap on the $5$ strongest E1 primes, again with $50$ puzzles and $3$ initialisations ( $750$ runs)	$0/750$	Mean lift $0.009$ ; mean $19.3$ steps
E2 SA	Simulated annealing on the same $750$ runs	$0/750$	Mean lift $0.000$ ; mean $5000$ steps

Appendix

Table 10: Archived local-search results for the powers-of-two encoding. The E1 prime sweep used primes

2,3,5,7,11,13,17,23,47,73,97,127,257,521,2311

Constraint Satisfaction

Constraint satisfaction studies how to find or optimize assignments that obey interacting rules across discrete and structured problems.

See all 86 papers

Anatomy of a Sound Neural Reasoner: One-Shot Amortization, First-Pass Poisoning, and Search Inertness in Clue-Rich Completion
Jul 22, 2026Aleksey KomissarovSudoku Solving Inference-Time Search
Neapolis University, Pafos, Cyprus
DiBS: Diffusion-Informed Branch Selection
Jun 2, 2026Bo Liu, Yuan Xie, Yuan Gao +4Sudoku Solving Diffusion Guidance
1Jilin University · 2The Chinese University of Hong Kong, Shenzhen · 3Southwest University +3
Global Difference Constraint Propagation for Constraint Programming
Jul 22, 2026Lucas Kletzander, Jip J. Dekker, Andreas Schutt +1Constraint Propagation Constraint Satisfaction
1Databases and Artificial Intelligence Group, TU Wien, Karlsplatz 13, Wien, 1040, Austria. · Department of Data Science and Artificial Intelligence, Monash University, Clayton, 3168, Victoria, Australia. · 3ARC Training Centre in Optimisation Technologies, Integrated Methodologies, and Applications (OPTIMA), Melbourne, Victoria, Australia. +1

Jul 22, 2026J/K move · Enter open · S save

Anatomy of a Sound Neural Reasoner: One-Shot Amortization, First-Pass Poisoning, and Search Inertness in Clue-Rich Completion

Aleksey Komissarov

Neapolis University, Pafos, Cyprus

Sudoku Solving Inference-Time Search Structured Reasoning Constraint Satisfaction Test-Time Augmentation

Open paper AskPDF arXiv

Neural solvers are built to deduce, branch, and revise intermediate states. The Lattice Deduction Transformer (LDT) appears to do exactly that. In clue-rich Sudoku, it does not: one forward pass commits essentially the entire grid (every blank cell on standard 6x6, 94-96% on augmented 9x9), turning the iterative solver into a one-shot predictor wrapped in an exact verifier. All hard-slice failures are decided before search begins, when the first pass confidently deletes a value required by the true solution. We call this first-pass poisoning. Adding learned branching, MRV, backtracking, value exclusion, and shared nogoods (CoLT) does not change which Sudoku instances are solved; it cuts repeated invalid derivations 1,497-fold. At the frozen training budget, constraint-graph attention alone matches full-CoLT accuracy, while positional tables recover only under substantially longer training, indicating an optimization and sample-efficiency advantage rather than an absolute capacity difference. The diagnosis predicts two effective interventions. Digit-permutation augmentation raises 9x9 accuracy from below 1% to 96.5 +/- 0.3 across three training seeds on a symmetry-disjoint split. Test-time union over symmetry-transformed passes raises all three hard-slice checkpoints from 72.8-78.9% to 100% without retraining. On from-scratch graph coloring, one-shot behavior disappears and search changes accuracy. In clue-rich completion, LDT-like systems are one-shot amortized predictors rather than learned search procedures: accuracy is determined by calibration and symmetry, while search primarily removes computational waste.

Abstract

Constraint Satisfaction

Explore similar work

Anatomy of a Sound Neural Reasoner: One-Shot Amortization, First-Pass Poisoning, and Search Inertness in Clue-Rich Completion

DiBS: Diffusion-Informed Branch Selection

Global Difference Constraint Propagation for Constraint Programming