`nx_sudoku.nx` source

↩ module page · 318 lines · 14988 B
1// nx_sudoku.nx -- the FILE SURFACE for sudoku: proven-unique puzzle banks in the estate's own format.
2//
3// THIS FILE HOLDS NO ALGORITHM. Rules, solver, solution counter and carver live in nx_sudoku_core.nx
4// and are shared with nx_sudoku_wasm (the playable module). An earlier version of this file carried its
5// own sd_ok/sd_fill/sd_count/sd_carve, which meant TWO implementations of one ruleset in the estate --
6// the duplicate-ruler defect. The extraction was only half the fix; deleting this copy is the rest.
7// Verified by re-banking seed 1101 and comparing bytes: a refactor that reproduces the banked artifact
8// exactly has provably changed no behaviour.
9//
10// NATIVE BANK FORMAT. The bank is a sovereign nx_gamesave state file, NOT a TSV. TSV has no header, no
11// version, no checksum and no atomicity: a torn write or a flipped byte reads back as a plausible
12// puzzle. gs_save gives the estate's guarantees for free -- 48-byte versioned header, rolling checksum
13// with CORRUPTION REFUSED LOUD, a future format REFUSED rather than misparsed, atomic tmp+fsync+rename,
14// and additive .prev banking (rule 13).
15//   layout: 162 i64 per puzzle -- [0..80] the puzzle digits, [81..161] its solution.
16//
17// UNIQUENESS IS COUNTED, NEVER ASSUMED: a clue is removed only while exactly one solution survives, and
18// every row is re-counted before it reaches the file. The clue floor is 17 -- McGuire, Tugemann &
19// Civario (2012) proved no 16-clue sudoku has a unique solution, so fewer is CLAMPED, not honoured.
20//
21//   usage: nx_sudoku --kat                                self-test -> VERDICT=GREEN/RED, exit carries it
22//          nx_sudoku bank <count> <clues> <seed> <out.sav>    the native, checksummed bank
23//          nx_sudoku jsbank <in.sav> <out.js>                 derive the page fragment FROM that bank
24//          nx_sudoku gen <count> <clues> <seed>               text emit, for eyeballing a grid
25//   exit : 0 ok | 1 RED/refused | 2 usage
26// license_tier: ORIGINAL  expect_exit: 0
27import "nx_syscalls.nx"
28import "nx_gamesave.nx"
29import "nx_sudoku_core.nx"
30const SD_MAGIC_12345: i64 = 12345
31const SD_MAGIC_4242: i64 = 4242
32
33const SD_SCHEMA: i64 = 5211   // sudoku bank v1 schema id, checked on load
34const SD_CELLS:  i64 = 162    // 81 puzzle + 81 solution
35
36// ---------- io ----------
37func sd_w(s: *u8) -> i64 { var n: i64=0; while s[n]!=(0 as u8){n=n+1} sys_write(1,s,n); return 0 }
38func sd_pn(v: i64) -> i64 {
  let t: *u8=sys_mmap(28); var m: i64=v
  if m<0 { sys_write(1,"-" as *u8,1); m=0-m }
  var k: i64=0
  if m==0 { t[0]=48 as u8; k=1 }
  while m>0 { t[k]=(48+(m%10)) as u8; m=m/10; k=k+1 }
  let b: *u8=sys_mmap(28); var i: i64=0
  while i<k { b[i]=t[k-1-i]; i=i+1 }
  sys_write(1,b,k); return 0
47}
48func sd_cat(dst: *u8, off: i64, s: *u8) -> i64 {
  var o: i64=off; var i: i64=0
  while s[i]!=(0 as u8) { dst[o]=s[i]; o=o+1; i=i+1 }
  return o
52}
53func sd_atoi(s: *u8) -> i64 {
  var v: i64=0; var i: i64=0
  while s[i]!=(0 as u8) {
      let c: i64 = s[i] as i64
      if c>=48 { if c<=57 { v=v*10+(c-48) } }
      i=i+1
  }
  return v
61}
62
63// generate `cnt` proven-unique puzzles into cells[] (SD_CELLS i64 each). returns puzzles made.
64// The PRNG is seeded ONCE and the stream continues across puzzles -- seeding per puzzle would emit the
65// same grid `cnt` times. This is why the loop calls sc_fill/sc_carve directly rather than sc_gen.
66func sd_fill_bank(cells: *i64, cnt: i64, clu: i64, seed: i64) -> i64 {
  let cb: i64 = sys_mmap(SC_SIZE) as i64
  sc_seed(cb, seed)
  var made: i64 = 0
  var run: i64 = 1
  while run == 1 {
      if made >= cnt { run = 0 } else {
          sc_clear(cb, SC_G)
          if sc_fill(cb, SC_G, 0) == 1 {
              sc_copy(cb, SC_G, SC_SOL)
              sc_carve(cb, clu)
              // REFUSE to bank a row we have not just proven unique. carve already guarantees it;
              // re-checking means a silent lie cannot reach the file.
              sc_copy(cb, SC_G, SC_WORK)
              if sc_count(cb, SC_WORK, 0, 0) == 1 {
                  let b: i64 = made*SD_CELLS
                  var i: i64 = 0
                  while i < 81 {
                      cells[b+i]    = sc_get(cb, SC_G,   i)
                      cells[b+81+i] = sc_get(cb, SC_SOL, i)
                      i = i + 1
                  }
                  made = made + 1
              }
          } else { run = 0 }
      }
  }
  return made
94}
95
96// ---------- self-test ----------
97func sd_selftest() -> i64 {
  var f: i64 = 0
  let cb: i64 = sys_mmap(SC_SIZE) as i64
  let quad: *i64 = sys_mmap(64) as *i64
101
  // ---- a complete grid is produced and is internally legal ----
  sc_seed(cb, SD_MAGIC_12345)
  sc_clear(cb, SC_G)
  if sc_fill(cb, SC_G, 0)!=1 { f=f+1 }
  if sc_clues(cb, SC_G)!=81 { f=f+1 }
  sc_copy(cb, SC_G, SC_SOL)
  // legality: lift each cell and confirm its own value is still placeable
  var i: i64 = 0
  while i<81 {
      let v: i64 = sc_get(cb, SC_G, i)
      sc_put(cb, SC_G, i, 0)
      if sc_ok(cb, SC_G, i, v)!=1 { f=f+1 }
      sc_put(cb, SC_G, i, v)
      i=i+1
  }
  // a SOLVED grid has exactly one solution
  sc_copy(cb, SC_G, SC_WORK)
  if sc_count(cb, SC_WORK, 0, 0)!=1 { f=f+1 }
120
  // ---- NEG-CONTROL 1: the empty grid has many solutions (the counter is not stuck at 1) ----
  sc_clear(cb, SC_WORK)
  if sc_count(cb, SC_WORK, 0, 0)<2 { f=f+1 }
124
  // ---- NEG-CONTROL 2: a PLANTED unavoidable set must be detected as non-unique ----
  if sc_unavoidable(cb, SC_SOL, quad)!=1 { f=f+1 } else {
      sc_copy(cb, SC_SOL, SC_WORK)
      sc_put(cb, SC_WORK, quad[0], 0); sc_put(cb, SC_WORK, quad[1], 0)
      sc_put(cb, SC_WORK, quad[2], 0); sc_put(cb, SC_WORK, quad[3], 0)
      // assert the fixture REACHED the condition before asserting the outcome
      if sc_get(cb, SC_WORK, quad[0])!=0 { f=f+1 }
      if sc_count(cb, SC_WORK, 0, 0)<2 { f=f+1 }
  }
134
  // ---- POSITIVE CONTROL: a carved puzzle is unique, respects the floor, and is a subset ----
  sc_copy(cb, SC_SOL, SC_G)
  sc_seed(cb, 999)
  let left: i64 = sc_carve(cb, 30)
  if left<SC_CLUE_FLOOR { f=f+1 }
  if sc_clues(cb, SC_G)!=left { f=f+1 }
  sc_copy(cb, SC_G, SC_WORK)
  if sc_count(cb, SC_WORK, 0, 0)!=1 { f=f+1 }
  i = 0
  while i<81 {
      let g: i64 = sc_get(cb, SC_G, i)
      if g!=0 { if g!=sc_get(cb, SC_SOL, i) { f=f+1 } }
      i=i+1
  }
  // and it must actually have holes (a "puzzle" of 81 clues is not a puzzle)
  if left>=81 { f=f+1 }
151
  // ---- the 17-clue floor is CLAMPED, not silently honoured ----
  sc_copy(cb, SC_SOL, SC_G)
  sc_seed(cb, SD_MAGIC_4242)
  if sc_carve(cb, 5)<SC_CLUE_FLOOR { f=f+1 }
156
  // ---- DETERMINISM: same seed => identical grid ----
  let cb2: i64 = sys_mmap(SC_SIZE) as i64
  sc_seed(cb2, SD_MAGIC_12345)
  sc_clear(cb2, SC_G)
  if sc_fill(cb2, SC_G, 0)!=1 { f=f+1 }
  i = 0
  while i<81 {
      if sc_get(cb2, SC_G, i)!=sc_get(cb, SC_SOL, i) { f=f+1; i=81 } else { i=i+1 }
  }
166
  // ---- NATIVE BANK ROUND-TRIP: gs_save -> gs_load is bit-exact, rows still provably unique ----
  let bc: *i64 = sys_mmap(3*SD_CELLS*8) as *i64
  let made: i64 = sd_fill_bank(bc, 3, 34, 777)
  if made!=3 { f=f+1 }
  let bp: *u8 = "/tmp/nx_sudoku_kat_bank.sav" as *u8
  if gs_save(bp, SD_SCHEMA, bc, made*SD_CELLS, 0) < 0 { f=f+1 }
  if gs_verify(bp) < 0 { f=f+1 }
  let rb:   *i64 = sys_mmap(3*SD_CELLS*8) as *i64
  let meta: *i64 = sys_mmap(64) as *i64
  let got: i64 = gs_load(bp, rb, 3*SD_CELLS, meta)
  if got != made*SD_CELLS { f=f+1 }
  if got <= 0 { f=f+1 } else {
      var d: i64 = 0
      while d < got { if rb[d]!=bc[d] { f=f+1; d=got } else { d=d+1 } }
      var p: i64 = 0
      while p < made {
          let b: i64 = p*SD_CELLS
          var q: i64 = 0
          while q < 81 { sc_put(cb, SC_WORK, q, rb[b+q]); q=q+1 }
          if sc_count(cb, SC_WORK, 0, 0)!=1 { f=f+1 }
          q = 0
          while q < 81 { if rb[b+q]!=0 { if rb[b+q]!=rb[b+81+q] { f=f+1 } } q=q+1 }
          p = p + 1
      }
  }
  return f
193}
194
195// ---------- emit ----------
196func sd_emit_row(p: *i64, s: *i64) -> i64 {
  let line: *u8 = sys_mmap(200)
  var o: i64 = 0
  var i: i64 = 0
  while i<81 { line[o]=(48+p[i]) as u8; o=o+1; i=i+1 }
  line[o]=9 as u8; o=o+1
  i=0
  while i<81 { line[o]=(48+s[i]) as u8; o=o+1; i=i+1 }
  line[o]=10 as u8; o=o+1
  sys_write(1,line,o)
  return 0
207}
208
209func main(argc: i64, argv: *i64) -> i64 {
  if argc>=2 {
      let a1: *u8 = argv[1] as *u8
      if a1[0]==(45 as u8) {
          sd_w("=== nx_sudoku --kat (uniqueness COUNTED; 17-clue floor = McGuire/Tugemann/Civario 2012) ===\n" as *u8)
          sd_w("algorithm: nx_sudoku_core (shared with nx_sudoku_wasm -- ONE implementation in the estate)\n" as *u8)
          let f: i64 = sd_selftest()
          sd_w("checks failed=" as *u8); sd_pn(f)
          sd_w("  (complete-fill + legality + solved-is-unique + neg-control-empty + neg-control-planted-unavoidable-set + carve-unique + clue-floor-clamp + subset + determinism + native-bank-round-trip)\n" as *u8)
          if f==0 { sd_w("VERDICT=GREEN\n" as *u8); sys_exit(0); return 0 }
          sd_w("VERDICT=RED\n" as *u8); sys_exit(1); return 1
      }
      // bank <count> <clues> <seed> <out.sav>
      if a1[0]==(98 as u8) {
          if argc>=6 {
              let cnt: i64 = sd_atoi(argv[2] as *u8)
              let clu: i64 = sd_atoi(argv[3] as *u8)
              let sd:  i64 = sd_atoi(argv[4] as *u8)
              if cnt<=0 { sd_w("BANK-REFUSED count must be > 0\n" as *u8); sys_exit(2); return 2 }
              let cells: *i64 = sys_mmap(cnt*SD_CELLS*8) as *i64
              let made: i64 = sd_fill_bank(cells, cnt, clu, sd)
              if made!=cnt {
                  sd_w("BANK-REFUSED generated " as *u8); sd_pn(made)
                  sd_w(" of " as *u8); sd_pn(cnt); sd_w(" -- nothing written\n" as *u8)
                  sys_exit(1); return 1
              }
              // saved_at is CALLER-SUPPLIED 0 on purpose: the bank stays byte-reproducible for a
              // fixed (count, clues, seed), so a rebuild can be compared to the banked bytes.
              let rc: i64 = gs_save(argv[5] as *u8, SD_SCHEMA, cells, made*SD_CELLS, 0)
              if rc<0 { sd_w("BANK-FAIL gs_save rc=" as *u8); sd_pn(rc); sd_w("\n" as *u8); sys_exit(1); return 1 }
              sd_w("BANK-OK puzzles=" as *u8); sd_pn(made)
              sd_w(" fields=" as *u8); sd_pn(made*SD_CELLS)
              sd_w(" schema=" as *u8); sd_pn(SD_SCHEMA)
              sd_w(" path=" as *u8); sd_w(argv[5] as *u8); sd_w("\n" as *u8)
              sys_exit(0); return 0
          }
          sd_w("usage: nx_sudoku bank <count> <clues> <seed> <out.sav>\n" as *u8)
          sys_exit(2); return 2
      }
      // jsbank <in.sav> <out.js> -- DERIVE the page's script fragment FROM the native store.
      // The .sav is authoritative; this verb is the only reader, so the page parses no data format
      // and there is exactly one definition of the bank layout. gs_load REFUSES a corrupt or
      // future-version file, so a damaged bank cannot silently become a page with wrong puzzles.
      if a1[0]==(106 as u8) {
          if argc>=4 {
              let cap: i64 = GS_MAXFIELDS
              let cells: *i64 = sys_mmap(cap*8) as *i64
              let meta:  *i64 = sys_mmap(64) as *i64
              let n: i64 = gs_load(argv[2] as *u8, cells, cap, meta)
              if n<0 { sd_w("JSBANK-REFUSED gs_load rc=" as *u8); sd_pn(n); sd_w(" (" as *u8); sd_w(gs_errname(n)); sd_w(") -- nothing written\n" as *u8); sys_exit(1); return 1 }
              if n==0 { sd_w("JSBANK-REFUSED bank is empty -- nothing written\n" as *u8); sys_exit(1); return 1 }
              if n%SD_CELLS!=0 { sd_w("JSBANK-REFUSED field count " as *u8); sd_pn(n); sd_w(" is not a multiple of 162 -- not a sudoku bank\n" as *u8); sys_exit(1); return 1 }
              let pz: i64 = n/SD_CELLS
              let out: *u8 = sys_mmap(pz*180+256)
              var o: i64 = 0
              // A GENERATED ARTEFACT MUST DECLARE ITSELF, or a later reader consumes it as authored data.
              o = sd_cat(out, o, "/* NX-DERIVED: generated by nx_sudoku jsbank from a checksummed nx_gamesave bank. Do not edit. */\n" as *u8)
              o = sd_cat(out, o, "var SBANK=[" as *u8)
              var p: i64 = 0
              while p < pz {
                  if p>0 { out[o]=44 as u8; o=o+1 }
                  let b: i64 = p*SD_CELLS
                  out[o]=39 as u8; o=o+1
                  var i: i64 = 0
                  while i<81 { out[o]=(48+cells[b+i]) as u8; o=o+1; i=i+1 }
                  out[o]=124 as u8; o=o+1
                  i=0
                  while i<81 { out[o]=(48+cells[b+81+i]) as u8; o=o+1; i=i+1 }
                  out[o]=39 as u8; o=o+1
                  p=p+1
              }
              o = sd_cat(out, o, "];\n" as *u8)
              let fd: i64 = sys_openat_wr(argv[3] as *u8, 0x1a4)
              if fd<0 { sd_w("JSBANK-FAIL cannot open output\n" as *u8); sys_exit(1); return 1 }
              sys_write(fd, out, o)
              sys_close(fd)
              sd_w("JSBANK-OK puzzles=" as *u8); sd_pn(pz)
              sd_w(" bytes=" as *u8); sd_pn(o)
              sd_w(" from=" as *u8); sd_w(argv[2] as *u8); sd_w("\n" as *u8)
              sys_exit(0); return 0
          }
          sd_w("usage: nx_sudoku jsbank <in.sav> <out.js>\n" as *u8)
          sys_exit(2); return 2
      }
      // gen <count> <clues> <seed> -- text emit, kept for eyeballing a grid
      if argc>=5 {
          let cnt: i64 = sd_atoi(argv[2] as *u8)
          let clu: i64 = sd_atoi(argv[3] as *u8)
          let sd:  i64 = sd_atoi(argv[4] as *u8)
          if cnt<=0 { sd_w("GEN-REFUSED count must be > 0\n" as *u8); sys_exit(2); return 2 }
          let cells: *i64 = sys_mmap(cnt*SD_CELLS*8) as *i64
          let made: i64 = sd_fill_bank(cells, cnt, clu, sd)
          var p: i64 = 0
          let pz: *i64 = sys_mmap(81*8) as *i64
          let sz: *i64 = sys_mmap(81*8) as *i64
          while p<made {
              let b: i64 = p*SD_CELLS
              var i: i64 = 0
              while i<81 { pz[i]=cells[b+i]; sz[i]=cells[b+81+i]; i=i+1 }
              sd_emit_row(pz, sz)
              p=p+1
          }
          sys_exit(0); return 0
      }
      sd_w("usage: nx_sudoku --kat | bank <count> <clues> <seed> <out.sav> | jsbank <in.sav> <out.js> | gen <count> <clues> <seed>\n" as *u8)
      sys_exit(2); return 2
  }
  sd_w("usage: nx_sudoku --kat | bank <count> <clues> <seed> <out.sav> | jsbank <in.sav> <out.js> | gen <count> <clues> <seed>\n" as *u8)
  sys_exit(2); return 2
318}
nx_sudoku.nx source

`nx_sudoku.nx` source
