crossword15-18 -- search analysis records
==========================================

2026-10-15  Arc consistency: analytic check (search advisor, arc consistency gap)
---------------------------------------------------------------------------------
Question: along the spec's search, how many placements that the spec's crossing check accepts
can never be completed, how many of those does arc consistency (propagation over crossing
letters to a fixpoint) remove, and at what cost per state?  Two sizes of the crossword family:
crossword5-11-1 (5x5, 10 slots) and crossword15-18 (15x15, 70 slots).

Method: cwdict_ac.py (independent Python).  Random paths follow the spec's slot order; at each
step up to 8 (15x15) or 20 (5x5) listed words passing the spec's crossing check are tested:
arc consistency over all open slots, then, if it passes, an exact completion search (budget
2000 words, fewest values first, propagation after each choice).  Paths are extended only with
completable placements (the regime of the checked search).  Open-slot domains: dictionary
words (forwards and reversed) plus unused listed words.
  python3 cwdict_ac.py probs/problem-crossword15-18.lisp src/English-words-455K.txt SEED PATHS PER-STEP
  (DUMP=grids15.lisp writes each tested grid with its verdict, for the SBCL timing.)

Results (counts of placements the spec accepts):
  5x5,  seed 1, 20 paths:  283 accepted; 7 uncompletable (2.5%); arc consistency removes all 7.
  15x15, seed 2, 7 paths: 1082 accepted; 615 uncompletable (57%); arc consistency removes 482
                          (78%); 133 pass it but have no completion; 4 unknown at the budget.
                          Open-slot values fall 45% (1.67e9 to 0.93e9 summed over samples).
  15x15, seed 3, 3 paths:  395 accepted; 159 uncompletable (40%); arc consistency removes 145
                          (91%); 14 pass it but have no completion; 5 unknown.
  The share of doomed placements grows steeply with grid size; arc consistency catches most.

Cost (SBCL 2.6.9 in the Linux VM, time15.lisp + time15b.lisp on the 395 dumped grids, using
the spec's own initial-domains / propagate / complete-grid):
  arc consistency alone        2.1 to 4.8 ms per placement (2.3 ms on completable grids)
  complete-grid (budget 2000)  2.0 ms where arc consistency already fails, 30 ms on
                               completable grids, 115 ms on budget-limited ones
  plain search                 about 0.2 ms per state per thread (22 million program cycles
                               in 5 minutes at 16 threads, design notes)
  So arc consistency alone is a middle setting: about 10 times a plain state, about 13 times
  cheaper than the full check, leaving 10-20% of the uncompletable placements.  The spec's
  completion check already starts with this propagation.

crossword13 (word list only, cw13_ac.py): the spec's search is already free of dead ends (24
states, first solution); arc consistency at the start cuts the values from 181 to 23 (solves
it) but saves no states.

Soundness finding and fix: 33 of the 138 listed words (e.g. BRERRABBIT, AUNTAUDREY,
UNITEDWAY) are not in the dictionary, yet the crossing check and the completion solver
judged open slots by dictionary words only, so a placement whose crossing could still take
such a listed word was rejected (best grids could be missed).  Fixed 2026-10-15:
read-dictionary adds the listed words not already present, so every check sees them.
Checked: "BRERRABB??" now fits; arc consistency and completion timings unchanged (above).
crossword5-11-1 is not affected (all its listed words are in the dictionary).

2026-10-15  Arc consistency as a search setting (library src/ww-arc-consistency.lisp)
------------------------------------------------------------------------------------
The spec's propagation now runs on the engine library: one constraint per open slot,
restricting each crossing slot by its letters at the shared cell.  Checked exact against
the previous code: 150 random grids (seed 42, 1 to 14 random listed placements), identical
complete-grid verdicts (108 complete, 42 impossible) and identical narrowed domains, same
time (4.7 to 4.8 s for all 150, Linux VM).  2 of the 42 impossible grids pass arc consistency.

New setting *search-completion-budget* :arc-consistency (propagation only, no word tried).
Fixed-time run, user's machine: 16 threads, (setf *min-tasks* 32 *tasks-per-thread* 2),
*random-state* seeded 1, stopped after about 5 minutes (368 s):
  arc consistency only   ~240,000 program cycles (~362,000 states, ~1,100 states/s)
                         best grid 18 listed words; (analyze) :IMPOSSIBLE; (repair) kept 15
  full check (2000)      48,000 to 54,000 program cycles; 18, 19, 19 words, all completable
  no check, then repair  ~22 million program cycles; 24 placed, 17 kept
Lesson: arc consistency alone lets 10-20% of uncompletable placements through (analytic
check above), and a best-value search ends on exactly those grids, so the partial check did
worse than both alternatives.  Its value here is inside the exact completion check.

2026-10-15  Restarts: repeated short randomized runs against one long run
-------------------------------------------------------------------------
Question: does restarting (new random early placements) beat one long run, whose workers
each make one dive and never revisit their early placements (~3,000 expansions per worker
in 5 minutes against ~70 slots)?
Setup, user's machine: 16 threads, (setf *search-completion-budget* 2000),
(setf *min-tasks* 32 *tasks-per-thread* 2); each run stopped by a temporary prune-state?
deadline of 30 s; *random-state* seeded (sb-ext:seed-random-state (+ (* 100 batch) i)),
batches 1-3, i = 0-9.  Words placed per run (every best grid passes the completion check):
  batch 1: 17 20 19 18 19 17 18 18 18 21   best 21, mean 18.5
  batch 2: 17 17 17 20 17 19 17 18 17 19   best 20, mean 17.8
  batch 3: 18 17 18 19 18 19 19 17 17 18   best 19, mean 18.0
  baseline, three 5-minute runs (same settings): 18 19 19, mean 18.7
Finding: a 30-second run averages 18.1 words, nearly what a 5-minute run reaches, so the
extra time of a long run adds under one word; ten restarts in the same 5 minutes gave
21, 20 and 19 (21 is the best grid found so far).  The value of a run is mostly set by its
early placements, so spreading the time over many random starts beats one long run.  This
holds whenever tasks are too large to finish in the run time, as in every larger instance.
Open: the best restart length (30 s was not tuned).
Built (2026-10-15): *time-limit* (seconds, 0 = none; a stopped run reports "Search stopped at
the time limit" and its outcome reason is TIME-LIMIT, never exhausted) and
(solve-restarts runs seconds [first-seed]), which seeds run i with first-seed + i, prints
each run's result, and keeps the best run's *best-states*.  Checked in the Linux VM: two
serial series with first seed 100 (10 s runs) both gave 18 and 16 and kept the 18; a 2-thread
run stopped at 8.0 s; backtracking honours the limit; (test) 27 problems, 0 failures.
Restart length, user's machine, same settings: (solve-restarts 30 10 1000), (... 2000),
(... 3000), three series of thirty 10-second runs (5 minutes each):
  seeds 1000-1029: best 18, mean 15.4
  seeds 2000-2029: best 18, mean 14.9
  seeds 3000-3029: best 18, mean 15.0
Against ten 30-second runs (best 21, 20, 19; mean 18.1) and one 5-minute run (18, 19, 19).
Finding: 10 seconds is too short; a run spends its first seconds on task generation and the
first dive, and a 10-second run averages 3 words fewer than a 30-second one.  Restarts pay
only once each run is long enough for its dive to place most of the words it will place;
here 30 seconds was, and beat both shorter and longer runs.  Lengths between 30 seconds and
5 minutes are untested.
