"""Original local Sudoku teaching fixture, version 1.0, Learn Coding USA, 2026-11-01.
Standard-library only. Run in an empty folder: writes data/ and output/.
Deterministic MRV backtracking, ascending digits. Not a reproduction of Williams.
"""
from pathlib import Path
import csv,json,time,platform,sys
R=Path(__file__).resolve().parent
for x in ['data','output']:(R/x).mkdir(exist_ok=True)
base=[(r*3+r//3+c)%9+1 for r in range(9) for c in range(9)]
def encode(b):return ''.join(map(str,b))
def units():
 return ([[r*9+c for c in range(9)] for r in range(9)]+[[r*9+c for r in range(9)] for c in range(9)]+[[r*9+c for r in range(br,br+3) for c in range(bc,bc+3)] for br in [0,3,6] for bc in [0,3,6]])
UNITS=units();PEERS=[set(j for u in UNITS if i in u for j in u)-{i} for i in range(81)]
def parse(text):
 if len(text)!=81 or any(c not in '0123456789' for c in text):return None,'malformed_input'
 b=list(map(int,text))
 for u in UNITS:
  v=[b[i] for i in u if b[i]]
  if len(v)!=len(set(v)):return None,'inconsistent_clues'
 return b,None
def independently_validate(board,clues):
 """Check completed units and original clues, separately from search candidates."""
 return len(board)==81 and all(set(board[i] for i in u)==set(range(1,10)) for u in UNITS) and all(not g or board[i]==g for i,g in enumerate(clues))
def search(clues,excluded=None,node_budget=100000):
 b=clues.copy();nodes=0;cutoff=False;answer=None
 def dfs():
  nonlocal nodes,cutoff,answer
  if nodes>=node_budget:cutoff=True;return False
  nodes+=1;choices=None;chosen=None
  for i,v in enumerate(b):
   if v:continue
   c=set(range(1,10))-{b[j] for j in PEERS[i]}
   if not c:return False
   if choices is None or len(c)<len(choices):chosen=i;choices=c
  if chosen is None:
   if excluded is not None and b==excluded:return False
   answer=b.copy();return True
  for digit in sorted(choices):
   b[chosen]=digit
   if dfs():return True
   if cutoff:break
  b[chosen]=0;return False
 start=time.perf_counter();found=dfs();elapsed=time.perf_counter()-start
 return dict(answer=answer,found=found,nodes=nodes,cutoff=cutoff,seconds=elapsed,exhausted=not found and not cutoff)
fixtures=[]
def add(k,b,expected,proof):fixtures.append(dict(puzzle_id=k,grid=encode(b) if isinstance(b,list) else b,expected_status=expected,expected_basis=proof,source='Author constructed from a valid Latin-pattern Sudoku; no external puzzle corpus'))
b=base.copy();b[0]=0;add('U1',b,'unique','One missing cell forced by its row')
b=base.copy()
for i in range(9):b[i*9+i]=0
add('U2',b,'unique','Exactly one blank in each row; each missing row digit is forced')
b=base.copy();b[:9]=[0]*9;add('U3',b,'unique','Exactly one blank in each column; each missing column digit is forced')
b=[0 if x in [1,2] else x for x in base];add('A1',b,'multiple','Base completion and global digit 1/2 swap are distinct valid witnesses satisfying all clues')
b=base.copy();b[1]=b[0];add('C1',b,'inconsistent_clues','Duplicate nonzero digit in first row')
b=base.copy();b[1]=0;b[27]=0;b[0]=2;add('C2',b,'no_solution','Initial clues have no duplicates, but first-row blank requires 1 and its column already contains 1')
add('M1',encode(base)[:-1],'malformed_input','Only 80 characters')
add('M2','x'+encode(base)[1:],'malformed_input','Nondigit character')
def csvout(name,rows):
 with (R/'data'/name).open('w',newline='',encoding='utf-8') as f:
  w=csv.DictWriter(f,fieldnames=list(rows[0]));w.writeheader();w.writerows(rows)
csvout('sudoku-original-fixtures.csv',fixtures)
assert independently_validate(base,base)
amb=list(map(int,fixtures[3]['grid']));swapped=[2 if x==1 else 1 if x==2 else x for x in base]
assert base!=swapped and independently_validate(base,amb) and independently_validate(swapped,amb)
runs=[];witnesses=[]
for run_id,puzzle_id,budget in [(f'R{i+1}',x['puzzle_id'],100000) for i,x in enumerate(fixtures)]+[('R9','U2',0)]:
 f=next(x for x in fixtures if x['puzzle_id']==puzzle_id);clues,error=parse(f['grid']);row=dict(run_id=run_id,puzzle_id=puzzle_id,clue_count=sum(c!='0' for c in f['grid']) if len(f['grid'])==81 and f['grid'].isdigit() else '',solver_version='LCA-MRV-1.0',completion_node_budget=100000,certification_node_budget=budget,completion_nodes='',completion_seconds='',certification_nodes='',certification_seconds='',certification_cutoff=False,status='',expected=f['expected_status'] if run_id!='R9' else 'one_found_uniqueness_unresolved',witnesses_valid='',measurement='One local run; nodes count recursive calls, not universal work units')
 if error:row['status']=error
 else:
  first=search(clues);row.update(completion_nodes=first['nodes'],completion_seconds=first['seconds'])
  if first['found']:
   assert independently_validate(first['answer'],clues)
   witnesses.append(dict(run_id=run_id,puzzle_id=puzzle_id,role='first_completion',grid=encode(first['answer']),valid=True))
   second=search(clues,excluded=first['answer'],node_budget=budget)
   row.update(certification_nodes=second['nodes'],certification_seconds=second['seconds'],certification_cutoff=second['cutoff'],witnesses_valid=True)
   if second['found']:
    assert second['answer']!=first['answer'] and independently_validate(second['answer'],clues)
    witnesses.append(dict(run_id=run_id,puzzle_id=puzzle_id,role='alternative_completion',grid=encode(second['answer']),valid=True));row['status']='multiple'
   elif second['exhausted']:row['status']='unique'
   else:row['status']='one_found_uniqueness_unresolved'
  elif first['exhausted']:row['status']='no_solution'
  else:row['status']='no_completion_found_search_unresolved'
 assert row['status']==row['expected'],row
 runs.append(row)
csvout('sudoku-local-run-results.csv',runs);csvout('sudoku-validated-witnesses.csv',witnesses)
csvout('sudoku-blank-experiment-ledger.csv',[dict(puzzle_id='',clue_count='',solver_version='',configuration='',completion_seconds='',certification_seconds='',timeout_or_budget='',final_status='',validation_reference='')])
summary=dict(fixture_count=8,run_count=9,expected_matches=9,validated_witnesses=len(witnesses),python=sys.version.split()[0],architecture=platform.machine(),selection='Three forced unique examples, one known ambiguous example, two contradiction examples, two malformed inputs; plus deliberate zero-node certification cutoff on U2',method='First completion then fresh search excluding exactly that completion; full exhaustive failure establishes uniqueness under implemented rules; node cutoff remains unresolved',node_budget_note='R9 deliberately permits zero certification nodes. It is a controlled interruption demonstration, not an observed natural timeout.',runs=runs)
(R/'output/experiment-results.json').write_text(json.dumps(summary,indent=2)+'\n')
print(json.dumps({k:v for k,v in summary.items() if k!='runs'},indent=2));print([(x['run_id'],x['status'],x['completion_nodes'],x['certification_nodes']) for x in runs])