code wiki / _hdl_build / nx_sudoku_core.nx
nx_sudoku_core.nx source
↩ module page · 222 lines · 8398 B
1// nx_sudoku_core.nx -- LIB (no main): the ONE sudoku algorithm in the estate, written BASE-RELATIVE
2// so the identical code runs natively (base = an mmap'd buffer) and inside our WebAssembly (base = 0).
3//
4// WHY BASE-RELATIVE. The estate's wasm game contract (nx_wasm_2048, nx_wasm_craft) is that a game is
5// pure integer logic over a flat memory image addressed as base+offset. A module written that way needs
6// no allocator, no syscalls and no host cooperation, so the SAME source is the native binary AND the
7// browser module. The alternative -- one copy in NishiLang for the tool and another in JavaScript for
8// the page -- is two implementations of one ruleset, which is the duplicate-ruler defect the estate
9// keeps paying for. There is exactly ONE solver, ONE counter and ONE carver here, and both consumers
10// (nx_sudoku for banks, nx_sudoku_wasm for play) compose them.
11//
12// THE LOAD-BEARING PROPERTY: uniqueness is COUNTED, never assumed. sc_carve empties a cell only when
13// sc_count still returns exactly 1, and sc_count saturates at 2 because "is it still unique" only ever
14// needs to separate 1 from more-than-1. The clue floor is 17 -- McGuire, Tugemann & Civario (2012)
15// proved exhaustively that no 16-clue sudoku has a unique solution, so a request for fewer is CLAMPED
16// rather than honoured: asking for 16 asks for something that provably does not exist.
17//
18// Deterministic: the PRNG is a seeded LCG held in the memory image, so a given seed reproduces a given
19// puzzle exactly. A generator you cannot re-run is not one you can test.
20// license_tier: ORIGINAL No hw writes (Rule 26).
21
22// ---- memory map, all relative to the caller's base ----
23const SC_G: i64 = 0 // 81 i64 the working / puzzle grid
24const SC_SOL: i64 = 648 // 81 i64 its full solution
25const SC_WORK: i64 = 1296 // 81 i64 scratch grid for counting
26const SC_ORD: i64 = 1944 // 81 i64 removal order
27const SC_SHUF: i64 = 2592 // 81*9 per-depth candidate shuffle (never allocated in the hot loop)
28const SC_RNG: i64 = 8424 // 1 i64 LCG state
29const SC_SIZE: i64 = 8432 // total bytes a caller must provide
30
31const SC_CLUE_FLOOR: i64 = 17
32const SC_LCG_A: i64 = 1103515245
33const SC_LCG_C: i64 = 12345
34const SC_LCG_M: i64 = 2147483648
35
36// ---- cell access ----
37func sc_get(base: i64, off: i64, i: i64) -> i64 { let p: *i64 = (base+off) as *i64; return p[i] }
38func sc_put(base: i64, off: i64, i: i64, v: i64) -> i64 { let p: *i64 = (base+off) as *i64; p[i]=v; return 0 }
39func sc_copy(base: i64, src: i64, dst: i64) -> i64 {
40 var i: i64 = 0
41 while i<81 { sc_put(base,dst,i, sc_get(base,src,i)); i=i+1 }
42 return 0
43}
44func sc_clear(base: i64, off: i64) -> i64 {
45 var i: i64 = 0
46 while i<81 { sc_put(base,off,i,0); i=i+1 }
47 return 0
48}
49func sc_clues(base: i64, off: i64) -> i64 {
50 var n: i64 = 0
51 var i: i64 = 0
52 while i<81 { if sc_get(base,off,i)!=0 { n=n+1 } i=i+1 }
53 return n
54}
55
56// ---- deterministic PRNG (state lives in the image so wasm needs no host RNG) ----
57func sc_seed(base: i64, s: i64) -> i64 {
58 var v: i64 = s
59 if v<=0 { v=1 }
60 sc_put(base,SC_RNG,0,v)
61 return 0
62}
63func sc_next(base: i64) -> i64 {
64 var v: i64 = sc_get(base,SC_RNG,0)*SC_LCG_A + SC_LCG_C
65 v = v % SC_LCG_M
66 if v<0 { v = 0-v }
67 sc_put(base,SC_RNG,0,v)
68 return v
69}
70func sc_below(base: i64, n: i64) -> i64 { if n<=0 { return 0 } return sc_next(base)%n }
71
72// ---- rules ----
73// may v be placed at cell i of grid `off` without breaking row, column or box?
74func sc_ok(base: i64, off: i64, i: i64, v: i64) -> i64 {
75 let r: i64 = i/9
76 let c: i64 = i-r*9
77 var k: i64 = 0
78 while k<9 {
79 if sc_get(base,off,r*9+k)==v { return 0 }
80 if sc_get(base,off,k*9+c)==v { return 0 }
81 k=k+1
82 }
83 let br: i64 = r-(r%3)
84 let bc: i64 = c-(c%3)
85 var a: i64 = 0
86 while a<3 {
87 var b: i64 = 0
88 while b<3 { if sc_get(base,off,(br+a)*9+bc+b)==v { return 0 } b=b+1 }
89 a=a+1
90 }
91 return 1
92}
93
94// randomized complete fill of grid `off`. Candidate order is shuffled per depth into SC_SHUF, so
95// nothing is allocated inside the recursion.
96func sc_fill(base: i64, off: i64, i: i64) -> i64 {
97 if i==81 { return 1 }
98 if sc_get(base,off,i)!=0 { return sc_fill(base,off,i+1) }
99 let sh: i64 = SC_SHUF + i*9*8
100 var k: i64 = 0
101 while k<9 { sc_put(base,sh,k,k+1); k=k+1 }
102 var q: i64 = 8
103 while q>0 {
104 let j: i64 = sc_below(base,q+1)
105 let t: i64 = sc_get(base,sh,q)
106 sc_put(base,sh,q, sc_get(base,sh,j))
107 sc_put(base,sh,j,t)
108 q=q-1
109 }
110 k=0
111 while k<9 {
112 let v: i64 = sc_get(base,sh,k)
113 if sc_ok(base,off,i,v)==1 {
114 sc_put(base,off,i,v)
115 if sc_fill(base,off,i+1)==1 { return 1 }
116 sc_put(base,off,i,0)
117 }
118 k=k+1
119 }
120 return 0
121}
122
123// COUNT solutions of grid `off`, saturating at 2. Mutates and restores `off`.
124func sc_count(base: i64, off: i64, i: i64, n: i64) -> i64 {
125 if n>1 { return n }
126 if i==81 { return n+1 }
127 if sc_get(base,off,i)!=0 { return sc_count(base,off,i+1,n) }
128 var acc: i64 = n
129 var v: i64 = 1
130 while v<=9 {
131 if sc_ok(base,off,i,v)==1 {
132 sc_put(base,off,i,v)
133 acc = sc_count(base,off,i+1,acc)
134 sc_put(base,off,i,0)
135 if acc>1 { return acc }
136 }
137 v=v+1
138 }
139 return acc
140}
141
142// carve SC_G down toward `clues`, removing a cell ONLY while exactly one solution survives.
143// returns the final clue count (never below SC_CLUE_FLOOR).
144func sc_carve(base: i64, clues: i64) -> i64 {
145 var target: i64 = clues
146 if target<SC_CLUE_FLOOR { target=SC_CLUE_FLOOR }
147 var i: i64 = 0
148 while i<81 { sc_put(base,SC_ORD,i,i); i=i+1 }
149 var q: i64 = 80
150 while q>0 {
151 let j: i64 = sc_below(base,q+1)
152 let t: i64 = sc_get(base,SC_ORD,q)
153 sc_put(base,SC_ORD,q, sc_get(base,SC_ORD,j))
154 sc_put(base,SC_ORD,j,t)
155 q=q-1
156 }
157 var left: i64 = 81
158 var k: i64 = 0
159 var run: i64 = 1
160 while run==1 {
161 if k>=81 { run=0 } else {
162 if left<=target { run=0 } else {
163 let p: i64 = sc_get(base,SC_ORD,k)
164 let sv: i64 = sc_get(base,SC_G,p)
165 if sv!=0 {
166 sc_put(base,SC_G,p,0)
167 sc_copy(base,SC_G,SC_WORK)
168 if sc_count(base,SC_WORK,0,0)!=1 { sc_put(base,SC_G,p,sv) } else { left=left-1 }
169 }
170 k=k+1
171 }
172 }
173 }
174 return left
175}
176
177// generate one proven-unique puzzle into SC_G with its solution in SC_SOL.
178// returns clue count, or -1 if a complete grid could not be produced.
179func sc_gen(base: i64, clues: i64, seed: i64) -> i64 {
180 sc_seed(base,seed)
181 sc_clear(base,SC_G)
182 if sc_fill(base,SC_G,0)!=1 { return 0-1 }
183 sc_copy(base,SC_G,SC_SOL)
184 let left: i64 = sc_carve(base,clues)
185 // REFUSE to hand back a puzzle we have not just proven unique. carve already guarantees it; the
186 // second check means a silent lie cannot escape this function.
187 sc_copy(base,SC_G,SC_WORK)
188 if sc_count(base,SC_WORK,0,0)!=1 { return 0-1 }
189 return left
190}
191
192// find an UNAVOIDABLE SET in a SOLVED grid: four cells forming a rectangle across two rows, two
193// columns and two boxes holding just two distinct values, which can always be exchanged. Blanking all
194// four therefore ALWAYS admits >=2 solutions, which makes it a guaranteed non-unique fixture rather
195// than a guess at one. Writes the 4 indices to out[0..3]; returns 1 if found.
196func sc_unavoidable(base: i64, off: i64, out: *i64) -> i64 {
197 var r1: i64 = 0
198 while r1<9 {
199 var r2: i64 = r1+1
200 while r2<9 {
201 var c1: i64 = 0
202 while c1<9 {
203 var c2: i64 = c1+1
204 while c2<9 {
205 let a: i64 = sc_get(base,off,r1*9+c1)
206 let b: i64 = sc_get(base,off,r1*9+c2)
207 let c: i64 = sc_get(base,off,r2*9+c1)
208 let d: i64 = sc_get(base,off,r2*9+c2)
209 if a==d { if b==c { if a!=b {
210 out[0]=r1*9+c1; out[1]=r1*9+c2; out[2]=r2*9+c1; out[3]=r2*9+c2
211 return 1
212 } } }
213 c2=c2+1
214 }
215 c1=c1+1
216 }
217 r2=r2+1
218 }
219 r1=r1+1
220 }
221 return 0
222}