import Mathlib /-! # Sudoku Solver Write a program to solve a Sudoku puzzle by filling the empty cells. A sudoku solution must satisfy all of the following rules: Each of the digits 1-9 must occur exactly once in each row. Each of the digits 1-9 must occur exactly once in each column. Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid. The '.' character indicates empty cells. ## Constraints - board.length == 9 - board[i].length == 9 - board[i][j] is a digit or '.'. - It is guaranteed that the input board has only one solution. ## Provided examples - `board = [["5", "3", ".", ".", "7", ".", ".", ".", "."], ["6", ".", ".", "1", "9", "5", ".", ".", "."], [".", "9", "8", ".", ".", ".", ".", "6", "."], ["8", ".", ".", ".", "6", ".", ".", ".", "3"], ["4", ".", ".", "8", ".", "3", ".", ".", "1"], ["7", ".", ".", ".", "2", ".", ".", ".", "6"], [".", "6", ".", ".", ".", ".", "2", "8", "."], [".", ".", ".", "4", "1", "9", ".", ".", "5"], [".", ".", ".", ".", "8", ".", ".", "7", "9"]]` → `[["5", "3", "4", "6", "7", "8", "9", "1", "2"], ["6", "7", "2", "1", "9", "5", "3", "4", "8"], ["1", "9", "8", "3", "4", "2", "5", "6", "7"], ["8", "5", "9", "7", "6", "1", "4", "2", "3"], ["4", "2", "6", "8", "5", "3", "7", "9", "1"], ["7", "1", "3", "9", "2", "4", "8", "5", "6"], ["9", "6", "1", "5", "3", "7", "2", "8", "4"], ["2", "8", "7", "4", "1", "9", "6", "3", "5"], ["3", "4", "5", "2", "8", "6", "1", "7", "9"]]` - `board = [["8", ".", ".", ".", "4", ".", "6", "7", "."], ["6", ".", ".", "8", ".", "3", ".", "2", "."], [".", "7", ".", ".", ".", ".", ".", ".", "."], ["1", ".", "6", ".", ".", ".", "7", "5", "9"], [".", "9", ".", "5", ".", "7", "3", "1", "."], ["7", "5", "3", ".", ".", ".", "2", ".", "4"], [".", "4", ".", ".", ".", ".", ".", "6", "."], [".", "3", ".", "9", ".", "8", ".", ".", "7"], [".", ".", "7", ".", "1", ".", ".", ".", "8"]]` → `[["8", "2", "5", "1", "4", "9", "6", "7", "3"], ["6", "1", "9", "8", "7", "3", "4", "2", "5"], ["3", "7", "4", "2", "5", "6", "8", "9", "1"], ["1", "8", "6", "3", "2", "4", "7", "5", "9"], ["4", "9", "2", "5", "8", "7", "3", "1", "6"], ["7", "5", "3", "6", "9", "1", "2", "8", "4"], ["9", "4", "8", "7", "3", "5", "1", "6", "2"], ["2", "3", "1", "9", "6", "8", "5", "4", "7"], ["5", "6", "7", "4", "1", "2", "9", "3", "8"]]` - `board = [[".", "2", ".", "1", ".", "4", ".", ".", "."], [".", ".", "4", ".", ".", ".", "6", "3", "."], ["5", ".", ".", ".", "6", ".", ".", "9", "."], ["2", ".", ".", ".", ".", "9", ".", ".", "."], [".", ".", "1", "3", ".", ".", "2", ".", "."], [".", ".", ".", "5", ".", ".", ".", ".", "7"], [".", "1", "6", ".", "4", ".", ".", "2", "."], [".", "5", ".", ".", ".", ".", "9", ".", "."], ["7", ".", ".", "8", ".", "1", ".", "4", "."]]` → `[["6", "2", "9", "1", "3", "4", "7", "8", "5"], ["1", "8", "4", "7", "9", "5", "6", "3", "2"], ["5", "3", "7", "2", "6", "8", "1", "9", "4"], ["2", "7", "5", "4", "1", "9", "8", "6", "3"], ["8", "4", "1", "3", "7", "6", "2", "5", "9"], ["9", "6", "3", "5", "8", "2", "4", "1", "7"], ["3", "1", "6", "9", "4", "7", "5", "2", "8"], ["4", "5", "8", "6", "2", "3", "9", "7", "1"], ["7", "9", "2", "8", "5", "1", "3", "4", "6"]]` ## Synthesized negative examples - invalid input: `board = [[".", ".", ".", ".", ".", ".", ".", ".", "."], [".", ".", ".", ".", ".", ".", ".", ".", "."], [".", ".", ".", ".", ".", ".", ".", ".", "."], [".", ".", ".", ".", ".", ".", ".", ".", "."], [".", ".", ".", ".", ".", ".", ".", ".", "."], [".", ".", ".", ".", ".", ".", ".", ".", "."], [".", ".", ".", ".", ".", ".", ".", ".", "."], [".", ".", ".", ".", ".", ".", ".", ".", "."]]` ([structural] a predicate that admits board.length == 9. one row short; a check of row widths alone accepts it) - invalid input: `board = [[".", ".", ".", ".", ".", ".", ".", "."], [".", ".", ".", ".", ".", ".", ".", ".", "."], [".", ".", ".", ".", ".", ".", ".", ".", "."], [".", ".", ".", ".", ".", ".", ".", ".", "."], [".", ".", ".", ".", ".", ".", ".", ".", "."], [".", ".", ".", ".", ".", ".", ".", ".", "."], [".", ".", ".", ".", ".", ".", ".", ".", "."], [".", ".", ".", ".", ".", ".", ".", ".", "."], [".", ".", ".", ".", ".", ".", ".", ".", "."]]` ([structural] a predicate that admits board[i].length == 9. one row has eight cells; row count and characters pass) - invalid input: `board = [["0", ".", ".", ".", ".", ".", ".", ".", "."], [".", ".", ".", ".", ".", ".", ".", ".", "."], [".", ".", ".", ".", ".", ".", ".", ".", "."], [".", ".", ".", ".", ".", ".", ".", ".", "."], [".", ".", ".", ".", ".", ".", ".", ".", "."], [".", ".", ".", ".", ".", ".", ".", ".", "."], [".", ".", ".", ".", ".", ".", ".", ".", "."], [".", ".", ".", ".", ".", ".", ".", ".", "."], [".", ".", ".", ".", ".", ".", ".", ".", "."]]` ([structural] a predicate that admits board[i][j] is a digit or '.'.. digit outside the Sudoku set; an isdigit check accepts it) - `board = [["5", "3", ".", ".", "7", ".", ".", ".", "."], ["6", ".", ".", "1", "9", "5", ".", ".", "."], [".", "9", "8", ".", ".", ".", ".", "6", "."], ["8", ".", ".", ".", "6", ".", ".", ".", "3"], ["4", ".", ".", "8", ".", "3", ".", ".", "1"], ["7", ".", ".", ".", "2", ".", ".", ".", "6"], [".", "6", ".", ".", ".", ".", "2", "8", "."], [".", ".", ".", "4", "1", "9", ".", ".", "5"], [".", ".", ".", ".", "8", ".", ".", "7", "9"]]` → `[["5", "3", ".", "6", "7", "8", "9", "1", "2"], ["6", "7", "2", "1", "9", "5", "3", "4", "8"], ["1", "9", "8", "3", "4", "2", "5", "6", "7"], ["8", "5", "9", "7", "6", "1", "4", "2", "3"], ["4", "2", "6", "8", "5", "3", "7", "9", "1"], ["7", "1", "3", "9", "2", "4", "8", "5", "6"], ["9", "6", "1", "5", "3", "7", "2", "8", "4"], ["2", "8", "7", "4", "1", "9", "6", "3", "5"], ["3", "4", "5", "2", "8", "6", "1", "7", "9"]]` is wrong ([structural] maximality stated as achievability alone. one empty cell remains; all filled digits are correct and conflict-free) - `board = [["5", "3", ".", ".", "7", ".", ".", ".", "."], ["6", ".", ".", "1", "9", "5", ".", ".", "."], [".", "9", "8", ".", ".", ".", ".", "6", "."], ["8", ".", ".", ".", "6", ".", ".", ".", "3"], ["4", ".", ".", "8", ".", "3", ".", ".", "1"], ["7", ".", ".", ".", "2", ".", ".", ".", "6"], [".", "6", ".", ".", ".", ".", "2", "8", "."], [".", ".", ".", "4", "1", "9", ".", ".", "5"], [".", ".", ".", ".", "8", ".", ".", "7", "9"]]` → `[["6", "7", "2", "1", "9", "5", "3", "4", "8"], ["5", "3", "4", "6", "7", "8", "9", "1", "2"], ["1", "9", "8", "3", "4", "2", "5", "6", "7"], ["8", "5", "9", "7", "6", "1", "4", "2", "3"], ["4", "2", "6", "8", "5", "3", "7", "9", "1"], ["7", "1", "3", "9", "2", "4", "8", "5", "6"], ["9", "6", "1", "5", "3", "7", "2", "8", "4"], ["2", "8", "7", "4", "1", "9", "6", "3", "5"], ["3", "4", "5", "2", "8", "6", "1", "7", "9"]]` is wrong ([structural] the result differs from the required one in at least one position. amended 2026-08-18: second mutation of a screened positive to reach quota) - `board = [["5", "3", ".", ".", "7", ".", ".", ".", "."], ["6", ".", ".", "1", "9", "5", ".", ".", "."], [".", "9", "8", ".", ".", ".", ".", "6", "."], ["8", ".", ".", ".", "6", ".", ".", ".", "3"], ["4", ".", ".", "8", ".", "3", ".", ".", "1"], ["7", ".", ".", ".", "2", ".", ".", ".", "6"], [".", "6", ".", ".", ".", ".", "2", "8", "."], [".", ".", ".", "4", "1", "9", ".", ".", "5"], [".", ".", ".", ".", "8", ".", ".", "7", "9"]]` → `[["5", "3", "4", "6", "7", "8", "9", "1", "2"], ["6", "7", "2", "1", "9", "5", "3", "4", "8"], ["1", "9", "8", "3", "4", "2", "5", "6", "7"], ["8", "5", "9", "7", "6", "1", "4", "2", "3"], ["4", "2", "6", "8", "5", "3", "7", "9", "1"], ["7", "1", "3", "9", "2", "4", "8", "5", "6"], ["9", "6", "1", "5", "3", "7", "2", "8", "4"], ["2", "8", "7", "4", "1", "9", "6", "3", "5"], ["3", "4", "5", "2", "8", "6", "1", "7", "b"]]` is wrong ([structural] the result differs from the required one in at least one position. amended 2026-08-18: second mutation of a screened positive to reach quota) -/ namespace PSudokuSolver abbrev Input := List (List String) abbrev Output := List (List String) /-! ### Specification helpers -/ /-- The nine digit strings that may fill a Sudoku cell. -/ def sudokuDigits : List String := ["1", "2", "3", "4", "5", "6", "7", "8", "9"] /-- The cell of `g` at row `i`, column `j`, defaulting to `""` outside the grid. -/ def cellAt (g : List (List String)) (i j : ℕ) : String := (((g[i]?).getD [])[j]?).getD "" /-- The nine cells of the 3x3 sub-box whose top-left corner is row `3 * p`, column `3 * q`. -/ def boxCells (g : List (List String)) (p q : ℕ) : List String := List.ofFn fun k : Fin 9 => cellAt g (3 * p + k.val / 3) (3 * q + k.val % 3) /-- `s` is a completed Sudoku solution of `b`: a 9x9 grid whose rows, columns and boxes are permutations of the digits and which keeps every given of `b`. -/ def IsSudokuSolution (b s : List (List String)) : Prop := s.length = 9 ∧ (∀ r ∈ s, r.length = 9) ∧ (∀ i : Fin 9, (List.ofFn fun j : Fin 9 => cellAt s i.val j.val).Perm sudokuDigits) ∧ (∀ j : Fin 9, (List.ofFn fun i : Fin 9 => cellAt s i.val j.val).Perm sudokuDigits) ∧ (∀ p q : Fin 3, (boxCells s p.val q.val).Perm sudokuDigits) ∧ (∀ i j : Fin 9, cellAt b i.val j.val ≠ "." → cellAt s i.val j.val = cellAt b i.val j.val) /-- Whether the filled cells of `cells` contain no repeated digit. -/ def noDupCells (cells : List String) : Bool := let filled := cells.filter fun c => c != "." filled.eraseDups.length == filled.length /-- Whether no row, column or 3x3 box of `b` already repeats a given digit. -/ def noConflicts (b : List (List String)) : Bool := ((List.range 9).all fun i => noDupCells ((b[i]?).getD [])) && ((List.range 9).all fun j => noDupCells ((List.range 9).map fun k => cellAt b k j)) && ((List.range 3).all fun p => (List.range 3).all fun q => noDupCells (boxCells b p q)) /-- Whether digit `d` may be placed at row `i`, column `j` of `b` without repeating a digit of its row, column or box. -/ def okToPlace (b : List (List String)) (i j : ℕ) (d : String) : Bool := (((b[i]?).getD []).all fun c => c != d) && ((List.range 9).all fun k => cellAt b k j != d) && ((boxCells b (i / 3) (j / 3)).all fun c => c != d) /-- The board obtained by writing `d` into the cell at row `i`, column `j` of `b`. -/ def setCell (b : List (List String)) (i j : ℕ) (d : String) : List (List String) := b.set i (((b[i]?).getD []).set j d) /-- The positions of the empty cells of `b`, in row-major order. -/ def emptiesOf (b : List (List String)) : List (ℕ × ℕ) := (List.range 9).flatMap fun i => ((List.range 9).filter fun j => cellAt b i j == ".").map fun j => (i, j) /-- The number of ways to fill the listed empty cells of `b` without repeating a digit in any row, column or box, capped at `2`. -/ def countSolutions (b : List (List String)) : List (ℕ × ℕ) → ℕ | [] => 1 | (i, j) :: rest => let a1 := if okToPlace b i j "1" then countSolutions (setCell b i j "1") rest else 0 let a2 := if 2 ≤ a1 then 0 else if okToPlace b i j "2" then countSolutions (setCell b i j "2") rest else 0 let a3 := if 2 ≤ a1 + a2 then 0 else if okToPlace b i j "3" then countSolutions (setCell b i j "3") rest else 0 let a4 := if 2 ≤ a1 + a2 + a3 then 0 else if okToPlace b i j "4" then countSolutions (setCell b i j "4") rest else 0 let a5 := if 2 ≤ a1 + a2 + a3 + a4 then 0 else if okToPlace b i j "5" then countSolutions (setCell b i j "5") rest else 0 let a6 := if 2 ≤ a1 + a2 + a3 + a4 + a5 then 0 else if okToPlace b i j "6" then countSolutions (setCell b i j "6") rest else 0 let a7 := if 2 ≤ a1 + a2 + a3 + a4 + a5 + a6 then 0 else if okToPlace b i j "7" then countSolutions (setCell b i j "7") rest else 0 let a8 := if 2 ≤ a1 + a2 + a3 + a4 + a5 + a6 + a7 then 0 else if okToPlace b i j "8" then countSolutions (setCell b i j "8") rest else 0 let a9 := if 2 ≤ a1 + a2 + a3 + a4 + a5 + a6 + a7 + a8 then 0 else if okToPlace b i j "9" then countSolutions (setCell b i j "9") rest else 0 min 2 (a1 + a2 + a3 + a4 + a5 + a6 + a7 + a8 + a9) /-! ### Validity predicate (V) -/ /-- Valid input: a 9x9 board of digits and `'.'` cells whose givens do not conflict and which admits exactly one completion. -/ def isValidInput (input : Input) : Bool := input.length == 9 && input.all (fun r => r.length == 9) && input.all (fun r => r.all fun c => c == "." || sudokuDigits.contains c) && noConflicts input && countSolutions input (emptiesOf input) == 1 /-! ### Ideal specification (P_spec) -/ /-- `result` is a completed Sudoku solution of `input`, and it is the only one. -/ def solveSudoku_spec (input : Input) (result : Output) : Prop := IsSudokuSolution input result ∧ ∀ g : List (List String), IsSudokuSolution input g → g = result /-! ### Decidable specification (P_check) -/ /-- Executable checker for `solveSudoku_spec`, with validity's unique-solution condition discharging the universal clause. -/ def solveSudoku_check (input : Input) (result : Output) : Bool := result.length == 9 && result.all (fun r => r.length == 9) && (List.range 9).all (fun i => let row := (List.range 9).map (fun j => cellAt result i j) row.length == 9 && sudokuDigits.all (fun d => row.contains d)) && (List.range 9).all (fun j => let col := (List.range 9).map (fun i => cellAt result i j) col.length == 9 && sudokuDigits.all (fun d => col.contains d)) && (List.range 3).all (fun p => (List.range 3).all (fun q => let box := boxCells result p q box.length == 9 && sudokuDigits.all (fun d => box.contains d))) && (List.range 9).all (fun i => (List.range 9).all (fun j => cellAt input i j == "." || cellAt result i j == cellAt input i j)) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem solveSudoku_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : solveSudoku_check input result ↔ solveSudoku_spec input result := by set_option maxHeartbeats 3000000 in have cell_get (b : List (List String)) (i j : Nat) (hi : i cellAt s r c) := List.nodup_ofFn.mp ((hs.2.2.1 r).nodup_iff.mpr digits) have colinj (c : Fin 9) : Function.Injective (fun r : Fin 9 => cellAt s r c) := List.nodup_ofFn.mp ((hs.2.2.2.1 c).nodup_iff.mpr digits) have boxinj (p q : Fin 3) : Function.Injective (fun k : Fin 9 => cellAt s (3*p.val+k.val/3) (3*q.val+k.val%3)) := List.nodup_ofFn.mp ((hs.2.2.2.2.1 p q).nodup_iff.mpr digits) have dmem : cellAt s i j ∈ sudokuDigits := (hs.2.2.1 i).mem_iff.mp (List.mem_ofFn.mpr ⟨j,rfl⟩) have dne : cellAt s i j ≠ "." := by simp only [sudokuDigits,List.mem_cons,List.mem_nil_iff,or_false] at dmem; rcases dmem with h|h|h|h|h|h|h|h|h <;> simp [h] have given (r c : Fin 9) (he : cellAt b r c=cellAt s i j) : cellAt s r c=cellAt s i j := by have hh : cellAt b r c ≠ "." := by rw [he]; exact dne exact (hs.2.2.2.2.2 r c hh).trans he simp only [okToPlace,Bool.and_eq_true,List.all_eq_true,bne_iff_ne,List.mem_range] refine ⟨⟨?_,?_⟩,?_⟩ · intro x hx he have hi : i.val simp at ha | cons x xs ih => simp only [List.map_cons,List.sum_cons] at hs rcases List.mem_cons.mp ha with hax|hat · subst a rcases List.mem_cons.mp hb with hbx|hbt · subst b; exact ⟨rfl,by omega⟩ · have := term_le xs b hbt; omega · rcases List.mem_cons.mp hb with hbx|hbt · subst b; have := term_le xs a hat; omega · exact ih hat hbt (by have := term_le xs a hat; omega) have count_eq_sum (b : List (List String)) (i j : Nat) (rest : List (Nat × Nat)) : countSolutions b ((i,j)::rest) = min 2 ((sudokuDigits.map (fun d => if okToPlace b i j d then countSolutions (setCell b i j d) rest else 0)).sum) := by have cap_step (a b : Nat) : min 2 (a+(if 2≤a then 0 else b)) = min 2 (min 2 a+b) := by split_ifs <;> omega have cap_norm (a b : Nat) : min 2 (min 2 a+b) = min 2 (a+b) := by omega rw [countSolutions] simp only [sudokuDigits,List.map_cons,List.map_nil,List.sum_cons,List.sum_nil] simp only [cap_step,cap_norm] congr 1 <;> omega let Pending (b : List (List String)) (ps : List (Nat × Nat)) : Prop := ps.Nodup ∧ (∀p∈ps,p.1<9 ∧ p.2<9 ∧ cellAt b p.1 p.2=".") ∧ ∀i j : Fin 9, cellAt b i j="." → (i.val,j.val)∈ps have pending_next (b : List (List String)) (hb : b.length=9) (hr : ∀r∈b,r.length=9) (i j : Fin 9) (ps : List (Nat × Nat)) (hp : Pending b ((i.val,j.val)::ps)) (d : String) (hd : d≠".") : Pending (setCell b i j d) ps := by refine ⟨hp.1.of_cons,?_,?_⟩ · intro p hm obtain ⟨hi,hj,he⟩ := hp.2.1 p (by simp [hm]) refine ⟨hi,hj,?_⟩ rw [cell_set b hb hr] have hn : ¬(i.val=p.1 ∧ j.val=p.2) := by intro hh have heq : p=(i.val,j.val) := Prod.ext hh.1.symm hh.2.symm exact (List.nodup_cons.mp hp.1).1 (heq ▸ hm) simpa [hn] using he · intro r c he rw [cell_set b hb hr] at he by_cases hh : i.val=r.val ∧ j.val=c.val · rw [if_pos hh] at he; exact False.elim (hd he) · rw [if_neg hh] at he rcases List.mem_cons.mp (hp.2.2 r c he) with heq|hm · exact False.elim (hh ⟨(Prod.mk.inj heq).1.symm,(Prod.mk.inj heq).2.symm⟩) · exact hm have solution_digit (b s : List (List String)) (hs : IsSudokuSolution b s) (i j : Fin 9) : cellAt s i j∈sudokuDigits ∧ cellAt s i j≠"." := by have hm : cellAt s i j∈sudokuDigits := (hs.2.2.1 i).mem_iff.mp (List.mem_ofFn.mpr ⟨j,rfl⟩) refine ⟨hm,?_⟩ simp only [sudokuDigits,List.mem_cons,List.mem_nil_iff,or_false] at hm rcases hm with h|h|h|h|h|h|h|h|h <;> simp [h] have count_positive (ps : List (Nat × Nat)) (b s : List (List String)) (hb : b.length=9) (hr : ∀r∈b,r.length=9) (hp : Pending b ps) (hs : IsSudokuSolution b s) : 0 simp [countSolutions] | cons p ps ih => obtain ⟨i,j⟩ := p obtain ⟨hi,hj,he⟩ := hp.2.1 (i,j) (by simp) let fi : Fin 9 := ⟨i,hi⟩ let fj : Fin 9 := ⟨j,hj⟩ have hd := solution_digit b s hs fi fj have hlegal := place_legal b s hb hr hs fi fj he have hshape := set_shape b hb hr fi fj (cellAt s i j) have hnext := pending_next b hb hr fi fj ps hp (cellAt s i j) hd.2 have hsol := solution_set b s hb hr hs fi fj have hpos := ih _ _ hshape.1 hshape.2 hnext hsol dsimp only [fi,fj] at * rw [count_eq_sum] have hterm : (if okToPlace b i j (cellAt s i j) then countSolutions (setCell b i j (cellAt s i j)) ps else 0) ∈ sudokuDigits.map (fun d => if okToPlace b i j d then countSolutions (setCell b i j d) ps else 0) := List.mem_map.mpr ⟨_,hd.1,rfl⟩ have hle := List.single_le_sum (by intros; omega) _ hterm rw [if_pos hlegal] at hle omega have solutions_equal_end (b s t : List (List String)) (hp : Pending b []) (hs : IsSudokuSolution b s) (ht : IsSudokuSolution b t) : s=t := by apply List.ext_getElem (hs.1.trans ht.1.symm) intro i hi hit have his : i<9 := by have hslen := hs.1; omega have hls := hs.2.1 _ (List.getElem_mem hi) have hlt := ht.2.1 _ (List.getElem_mem hit) apply List.ext_getElem (hls.trans hlt.symm) intro j hj hjt have hjs : j<9 := by omega have hn : cellAt b i j≠"." := by intro hh; exact List.not_mem_nil (hp.2.2 ⟨i,his⟩ ⟨j,hjs⟩ hh) have he := (hs.2.2.2.2.2 ⟨i,his⟩ ⟨j,hjs⟩ hn).trans (ht.2.2.2.2.2 ⟨i,his⟩ ⟨j,hjs⟩ hn).symm simpa only [cell_get s i j hi hj,cell_get t i j hit hjt] using he have count_unique (ps : List (Nat × Nat)) (b s t : List (List String)) (hb : b.length=9) (hr : ∀r∈b,r.length=9) (hp : Pending b ps) (hs : IsSudokuSolution b s) (ht : IsSudokuSolution b t) (hcount : countSolutions b ps=1) : s=t := by induction ps generalizing b s t with | nil => exact solutions_equal_end b s t hp hs ht | cons p ps ih => obtain ⟨i,j⟩ := p obtain ⟨hi,hj,he⟩ := hp.2.1 (i,j) (by simp) let fi : Fin 9 := ⟨i,hi⟩ let fj : Fin 9 := ⟨j,hj⟩ have hds := solution_digit b s hs fi fj have hdt := solution_digit b t ht fi fj have hls := place_legal b s hb hr hs fi fj he have hlt := place_legal b t hb hr ht fi fj he have shapes := set_shape b hb hr fi fj (cellAt s i j) have shapet := set_shape b hb hr fi fj (cellAt t i j) have nexts := pending_next b hb hr fi fj ps hp (cellAt s i j) hds.2 have nextt := pending_next b hb hr fi fj ps hp (cellAt t i j) hdt.2 have sols := solution_set b s hb hr hs fi fj have solt := solution_set b t hb hr ht fi fj have hps := count_positive ps _ _ shapes.1 shapes.2 nexts sols have hpt := count_positive ps _ _ shapet.1 shapet.2 nextt solt dsimp only [fi,fj] at * let f := fun d => if okToPlace b i j d then countSolutions (setCell b i j d) ps else 0 have hsum : (sudokuDigits.map f).sum=1 := by rw [count_eq_sum] at hcount; dsimp [f]; omega have hfs : 0 (i,j)) from fun a b hh => (Prod.mk.inj hh).2)).mpr exact List.nodup_range.filter _ · apply List.pairwise_lt_range.imp intro i j hij apply List.disjoint_left.mpr intro p hp hq simp only [List.mem_map] at hp hq obtain ⟨a,ha,hpa⟩ := hp obtain ⟨c,hc,hpc⟩ := hq have he : i=j := congrArg Prod.fst (hpa.trans hpc.symm) omega · intro p hp; exact (member p.1 p.2).mp hp · intro i j he; exact (member i j).mpr ⟨i.isLt,j.isLt,he⟩ have checker_solution (b s : List (List String)) : solveSudoku_check b s=true ↔ IsSudokuSolution b s := by have perm_digits (xs : List String) : xs.Perm sudokuDigits ↔ xs.length=9 ∧ ∀d∈sudokuDigits,d∈xs := by constructor · intro hp; exact ⟨by simpa [sudokuDigits] using hp.length_eq,fun d hd => hp.mem_iff.mpr hd⟩ · rintro ⟨hl,hm⟩ have hn : sudokuDigits.Nodup := by decide exact ((hn.subperm hm).perm_of_length_le (by simpa [sudokuDigits] using Nat.le_of_eq hl)).symm have map_ofFn (f : Nat → String) : (List.range 9).map f = List.ofFn (fun i : Fin 9 => f i.val) := by apply List.ext_getElem (by simp) intro i hi hj simp only [List.getElem_map,List.getElem_range,List.getElem_ofFn] simp only [solveSudoku_check,IsSudokuSolution,perm_digits,Bool.and_eq_true,List.all_eq_true, beq_iff_eq,List.mem_range,List.contains_iff_mem,Bool.or_eq_true,Fin.forall_iff,map_ofFn] simp only [List.length_ofFn,and_assoc] simp only [← or_iff_not_imp_left] rw [checker_solution] constructor · intro hs refine ⟨hs,?_⟩ intro s ht have hv := h simp only [isValidInput,Bool.and_eq_true,beq_iff_eq,List.all_eq_true] at hv exact count_unique _ _ _ _ hv.1.1.1.1 hv.1.1.1.2 (pending_initial input) ht hs hv.2 · exact And.left /-! ### Implementation helpers -/ /-- The digits of `sudokuDigits` that can be written at row `i`, column `j` of `board` without repeating a digit of its row, column or box. -/ def legalCandidates (board : List (List String)) (i j : ℕ) : List String := sudokuDigits.filter fun d => okToPlace board i j d /-- Backtracking search over the empty cells `empties` of `board`, branching on the most constrained cell and returning the first completed board found. -/ def solveSudokuFrom (board : List (List String)) (empties : List (ℕ × ℕ)) : Option (List (List String)) := match h : empties.mergeSort (fun p q => Nat.ble (legalCandidates board p.1 p.2).length (legalCandidates board q.1 q.2).length) with | [] => some board | (i, j) :: rest => (legalCandidates board i j).findSome? fun d => solveSudokuFrom (setCell board i j d) rest termination_by empties.length decreasing_by simp_wf have hl := congrArg List.length h simp only [List.length_mergeSort, List.length_cons] at hl omega /-! ### Main algorithm (impl) -/ /-- Solves the board by backtracking search with pruning and a minimum-remaining-values choice of the next empty cell. -/ def solveSudokuImpl (input : Input) : Output := (solveSudokuFrom input (emptiesOf input)).getD input /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem solveSudokuImpl_correct (input : Input) (h : isValidInput input) : solveSudoku_spec input (solveSudokuImpl input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput [["5", "3", ".", ".", "7", ".", ".", ".", "."], ["6", ".", ".", "1", "9", "5", ".", ".", "."], [".", "9", "8", ".", ".", ".", ".", "6", "."], ["8", ".", ".", ".", "6", ".", ".", ".", "3"], ["4", ".", ".", "8", ".", "3", ".", ".", "1"], ["7", ".", ".", ".", "2", ".", ".", ".", "6"], [".", "6", ".", ".", ".", ".", "2", "8", "."], [".", ".", ".", "4", "1", "9", ".", ".", "5"], [".", ".", ".", ".", "8", ".", ".", "7", "9"]] #guard isValidInput [["8", ".", ".", ".", "4", ".", "6", "7", "."], ["6", ".", ".", "8", ".", "3", ".", "2", "."], [".", "7", ".", ".", ".", ".", ".", ".", "."], ["1", ".", "6", ".", ".", ".", "7", "5", "9"], [".", "9", ".", "5", ".", "7", "3", "1", "."], ["7", "5", "3", ".", ".", ".", "2", ".", "4"], [".", "4", ".", ".", ".", ".", ".", "6", "."], [".", "3", ".", "9", ".", "8", ".", ".", "7"], [".", ".", "7", ".", "1", ".", ".", ".", "8"]] #guard isValidInput [[".", "2", ".", "1", ".", "4", ".", ".", "."], [".", ".", "4", ".", ".", ".", "6", "3", "."], ["5", ".", ".", ".", "6", ".", ".", "9", "."], ["2", ".", ".", ".", ".", "9", ".", ".", "."], [".", ".", "1", "3", ".", ".", "2", ".", "."], [".", ".", ".", "5", ".", ".", ".", ".", "7"], [".", "1", "6", ".", "4", ".", ".", "2", "."], [".", "5", ".", ".", ".", ".", "9", ".", "."], ["7", ".", ".", "8", ".", "1", ".", "4", "."]] /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput [[".", ".", ".", ".", ".", ".", ".", ".", "."], [".", ".", ".", ".", ".", ".", ".", ".", "."], [".", ".", ".", ".", ".", ".", ".", ".", "."], [".", ".", ".", ".", ".", ".", ".", ".", "."], [".", ".", ".", ".", ".", ".", ".", ".", "."], [".", ".", ".", ".", ".", ".", ".", ".", "."], [".", ".", ".", ".", ".", ".", ".", ".", "."], [".", ".", ".", ".", ".", ".", ".", ".", "."]]) #guard !(isValidInput [[".", ".", ".", ".", ".", ".", ".", "."], [".", ".", ".", ".", ".", ".", ".", ".", "."], [".", ".", ".", ".", ".", ".", ".", ".", "."], [".", ".", ".", ".", ".", ".", ".", ".", "."], [".", ".", ".", ".", ".", ".", ".", ".", "."], [".", ".", ".", ".", ".", ".", ".", ".", "."], [".", ".", ".", ".", ".", ".", ".", ".", "."], [".", ".", ".", ".", ".", ".", ".", ".", "."], [".", ".", ".", ".", ".", ".", ".", ".", "."]]) #guard !(isValidInput [["0", ".", ".", ".", ".", ".", ".", ".", "."], [".", ".", ".", ".", ".", ".", ".", ".", "."], [".", ".", ".", ".", ".", ".", ".", ".", "."], [".", ".", ".", ".", ".", ".", ".", ".", "."], [".", ".", ".", ".", ".", ".", ".", ".", "."], [".", ".", ".", ".", ".", ".", ".", ".", "."], [".", ".", ".", ".", ".", ".", ".", ".", "."], [".", ".", ".", ".", ".", ".", ".", ".", "."], [".", ".", ".", ".", ".", ".", ".", ".", "."]]) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard solveSudoku_check [["5", "3", ".", ".", "7", ".", ".", ".", "."], ["6", ".", ".", "1", "9", "5", ".", ".", "."], [".", "9", "8", ".", ".", ".", ".", "6", "."], ["8", ".", ".", ".", "6", ".", ".", ".", "3"], ["4", ".", ".", "8", ".", "3", ".", ".", "1"], ["7", ".", ".", ".", "2", ".", ".", ".", "6"], [".", "6", ".", ".", ".", ".", "2", "8", "."], [".", ".", ".", "4", "1", "9", ".", ".", "5"], [".", ".", ".", ".", "8", ".", ".", "7", "9"]] [["5", "3", "4", "6", "7", "8", "9", "1", "2"], ["6", "7", "2", "1", "9", "5", "3", "4", "8"], ["1", "9", "8", "3", "4", "2", "5", "6", "7"], ["8", "5", "9", "7", "6", "1", "4", "2", "3"], ["4", "2", "6", "8", "5", "3", "7", "9", "1"], ["7", "1", "3", "9", "2", "4", "8", "5", "6"], ["9", "6", "1", "5", "3", "7", "2", "8", "4"], ["2", "8", "7", "4", "1", "9", "6", "3", "5"], ["3", "4", "5", "2", "8", "6", "1", "7", "9"]] #guard solveSudoku_check [["8", ".", ".", ".", "4", ".", "6", "7", "."], ["6", ".", ".", "8", ".", "3", ".", "2", "."], [".", "7", ".", ".", ".", ".", ".", ".", "."], ["1", ".", "6", ".", ".", ".", "7", "5", "9"], [".", "9", ".", "5", ".", "7", "3", "1", "."], ["7", "5", "3", ".", ".", ".", "2", ".", "4"], [".", "4", ".", ".", ".", ".", ".", "6", "."], [".", "3", ".", "9", ".", "8", ".", ".", "7"], [".", ".", "7", ".", "1", ".", ".", ".", "8"]] [["8", "2", "5", "1", "4", "9", "6", "7", "3"], ["6", "1", "9", "8", "7", "3", "4", "2", "5"], ["3", "7", "4", "2", "5", "6", "8", "9", "1"], ["1", "8", "6", "3", "2", "4", "7", "5", "9"], ["4", "9", "2", "5", "8", "7", "3", "1", "6"], ["7", "5", "3", "6", "9", "1", "2", "8", "4"], ["9", "4", "8", "7", "3", "5", "1", "6", "2"], ["2", "3", "1", "9", "6", "8", "5", "4", "7"], ["5", "6", "7", "4", "1", "2", "9", "3", "8"]] #guard solveSudoku_check [[".", "2", ".", "1", ".", "4", ".", ".", "."], [".", ".", "4", ".", ".", ".", "6", "3", "."], ["5", ".", ".", ".", "6", ".", ".", "9", "."], ["2", ".", ".", ".", ".", "9", ".", ".", "."], [".", ".", "1", "3", ".", ".", "2", ".", "."], [".", ".", ".", "5", ".", ".", ".", ".", "7"], [".", "1", "6", ".", "4", ".", ".", "2", "."], [".", "5", ".", ".", ".", ".", "9", ".", "."], ["7", ".", ".", "8", ".", "1", ".", "4", "."]] [["6", "2", "9", "1", "3", "4", "7", "8", "5"], ["1", "8", "4", "7", "9", "5", "6", "3", "2"], ["5", "3", "7", "2", "6", "8", "1", "9", "4"], ["2", "7", "5", "4", "1", "9", "8", "6", "3"], ["8", "4", "1", "3", "7", "6", "2", "5", "9"], ["9", "6", "3", "5", "8", "2", "4", "1", "7"], ["3", "1", "6", "9", "4", "7", "5", "2", "8"], ["4", "5", "8", "6", "2", "3", "9", "7", "1"], ["7", "9", "2", "8", "5", "1", "3", "4", "6"]] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(solveSudoku_check [["5", "3", ".", ".", "7", ".", ".", ".", "."], ["6", ".", ".", "1", "9", "5", ".", ".", "."], [".", "9", "8", ".", ".", ".", ".", "6", "."], ["8", ".", ".", ".", "6", ".", ".", ".", "3"], ["4", ".", ".", "8", ".", "3", ".", ".", "1"], ["7", ".", ".", ".", "2", ".", ".", ".", "6"], [".", "6", ".", ".", ".", ".", "2", "8", "."], [".", ".", ".", "4", "1", "9", ".", ".", "5"], [".", ".", ".", ".", "8", ".", ".", "7", "9"]] [["5", "3", ".", "6", "7", "8", "9", "1", "2"], ["6", "7", "2", "1", "9", "5", "3", "4", "8"], ["1", "9", "8", "3", "4", "2", "5", "6", "7"], ["8", "5", "9", "7", "6", "1", "4", "2", "3"], ["4", "2", "6", "8", "5", "3", "7", "9", "1"], ["7", "1", "3", "9", "2", "4", "8", "5", "6"], ["9", "6", "1", "5", "3", "7", "2", "8", "4"], ["2", "8", "7", "4", "1", "9", "6", "3", "5"], ["3", "4", "5", "2", "8", "6", "1", "7", "9"]]) #guard !(solveSudoku_check [["5", "3", ".", ".", "7", ".", ".", ".", "."], ["6", ".", ".", "1", "9", "5", ".", ".", "."], [".", "9", "8", ".", ".", ".", ".", "6", "."], ["8", ".", ".", ".", "6", ".", ".", ".", "3"], ["4", ".", ".", "8", ".", "3", ".", ".", "1"], ["7", ".", ".", ".", "2", ".", ".", ".", "6"], [".", "6", ".", ".", ".", ".", "2", "8", "."], [".", ".", ".", "4", "1", "9", ".", ".", "5"], [".", ".", ".", ".", "8", ".", ".", "7", "9"]] [["6", "7", "2", "1", "9", "5", "3", "4", "8"], ["5", "3", "4", "6", "7", "8", "9", "1", "2"], ["1", "9", "8", "3", "4", "2", "5", "6", "7"], ["8", "5", "9", "7", "6", "1", "4", "2", "3"], ["4", "2", "6", "8", "5", "3", "7", "9", "1"], ["7", "1", "3", "9", "2", "4", "8", "5", "6"], ["9", "6", "1", "5", "3", "7", "2", "8", "4"], ["2", "8", "7", "4", "1", "9", "6", "3", "5"], ["3", "4", "5", "2", "8", "6", "1", "7", "9"]]) #guard !(solveSudoku_check [["5", "3", ".", ".", "7", ".", ".", ".", "."], ["6", ".", ".", "1", "9", "5", ".", ".", "."], [".", "9", "8", ".", ".", ".", ".", "6", "."], ["8", ".", ".", ".", "6", ".", ".", ".", "3"], ["4", ".", ".", "8", ".", "3", ".", ".", "1"], ["7", ".", ".", ".", "2", ".", ".", ".", "6"], [".", "6", ".", ".", ".", ".", "2", "8", "."], [".", ".", ".", "4", "1", "9", ".", ".", "5"], [".", ".", ".", ".", "8", ".", ".", "7", "9"]] [["5", "3", "4", "6", "7", "8", "9", "1", "2"], ["6", "7", "2", "1", "9", "5", "3", "4", "8"], ["1", "9", "8", "3", "4", "2", "5", "6", "7"], ["8", "5", "9", "7", "6", "1", "4", "2", "3"], ["4", "2", "6", "8", "5", "3", "7", "9", "1"], ["7", "1", "3", "9", "2", "4", "8", "5", "6"], ["9", "6", "1", "5", "3", "7", "2", "8", "4"], ["2", "8", "7", "4", "1", "9", "6", "3", "5"], ["3", "4", "5", "2", "8", "6", "1", "7", "b"]]) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard solveSudokuImpl [["5", "3", ".", ".", "7", ".", ".", ".", "."], ["6", ".", ".", "1", "9", "5", ".", ".", "."], [".", "9", "8", ".", ".", ".", ".", "6", "."], ["8", ".", ".", ".", "6", ".", ".", ".", "3"], ["4", ".", ".", "8", ".", "3", ".", ".", "1"], ["7", ".", ".", ".", "2", ".", ".", ".", "6"], [".", "6", ".", ".", ".", ".", "2", "8", "."], [".", ".", ".", "4", "1", "9", ".", ".", "5"], [".", ".", ".", ".", "8", ".", ".", "7", "9"]] == [["5", "3", "4", "6", "7", "8", "9", "1", "2"], ["6", "7", "2", "1", "9", "5", "3", "4", "8"], ["1", "9", "8", "3", "4", "2", "5", "6", "7"], ["8", "5", "9", "7", "6", "1", "4", "2", "3"], ["4", "2", "6", "8", "5", "3", "7", "9", "1"], ["7", "1", "3", "9", "2", "4", "8", "5", "6"], ["9", "6", "1", "5", "3", "7", "2", "8", "4"], ["2", "8", "7", "4", "1", "9", "6", "3", "5"], ["3", "4", "5", "2", "8", "6", "1", "7", "9"]] #guard solveSudokuImpl [["8", ".", ".", ".", "4", ".", "6", "7", "."], ["6", ".", ".", "8", ".", "3", ".", "2", "."], [".", "7", ".", ".", ".", ".", ".", ".", "."], ["1", ".", "6", ".", ".", ".", "7", "5", "9"], [".", "9", ".", "5", ".", "7", "3", "1", "."], ["7", "5", "3", ".", ".", ".", "2", ".", "4"], [".", "4", ".", ".", ".", ".", ".", "6", "."], [".", "3", ".", "9", ".", "8", ".", ".", "7"], [".", ".", "7", ".", "1", ".", ".", ".", "8"]] == [["8", "2", "5", "1", "4", "9", "6", "7", "3"], ["6", "1", "9", "8", "7", "3", "4", "2", "5"], ["3", "7", "4", "2", "5", "6", "8", "9", "1"], ["1", "8", "6", "3", "2", "4", "7", "5", "9"], ["4", "9", "2", "5", "8", "7", "3", "1", "6"], ["7", "5", "3", "6", "9", "1", "2", "8", "4"], ["9", "4", "8", "7", "3", "5", "1", "6", "2"], ["2", "3", "1", "9", "6", "8", "5", "4", "7"], ["5", "6", "7", "4", "1", "2", "9", "3", "8"]] #guard solveSudokuImpl [[".", "2", ".", "1", ".", "4", ".", ".", "."], [".", ".", "4", ".", ".", ".", "6", "3", "."], ["5", ".", ".", ".", "6", ".", ".", "9", "."], ["2", ".", ".", ".", ".", "9", ".", ".", "."], [".", ".", "1", "3", ".", ".", "2", ".", "."], [".", ".", ".", "5", ".", ".", ".", ".", "7"], [".", "1", "6", ".", "4", ".", ".", "2", "."], [".", "5", ".", ".", ".", ".", "9", ".", "."], ["7", ".", ".", "8", ".", "1", ".", "4", "."]] == [["6", "2", "9", "1", "3", "4", "7", "8", "5"], ["1", "8", "4", "7", "9", "5", "6", "3", "2"], ["5", "3", "7", "2", "6", "8", "1", "9", "4"], ["2", "7", "5", "4", "1", "9", "8", "6", "3"], ["8", "4", "1", "3", "7", "6", "2", "5", "9"], ["9", "6", "3", "5", "8", "2", "4", "1", "7"], ["3", "1", "6", "9", "4", "7", "5", "2", "8"], ["4", "5", "8", "6", "2", "3", "9", "7", "1"], ["7", "9", "2", "8", "5", "1", "3", "4", "6"]] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard solveSudoku_check [["5", "3", ".", ".", "7", ".", ".", ".", "."], ["6", ".", ".", "1", "9", "5", ".", ".", "."], [".", "9", "8", ".", ".", ".", ".", "6", "."], ["8", ".", ".", ".", "6", ".", ".", ".", "3"], ["4", ".", ".", "8", ".", "3", ".", ".", "1"], ["7", ".", ".", ".", "2", ".", ".", ".", "6"], [".", "6", ".", ".", ".", ".", "2", "8", "."], [".", ".", ".", "4", "1", "9", ".", ".", "5"], [".", ".", ".", ".", "8", ".", ".", "7", "9"]] (solveSudokuImpl [["5", "3", ".", ".", "7", ".", ".", ".", "."], ["6", ".", ".", "1", "9", "5", ".", ".", "."], [".", "9", "8", ".", ".", ".", ".", "6", "."], ["8", ".", ".", ".", "6", ".", ".", ".", "3"], ["4", ".", ".", "8", ".", "3", ".", ".", "1"], ["7", ".", ".", ".", "2", ".", ".", ".", "6"], [".", "6", ".", ".", ".", ".", "2", "8", "."], [".", ".", ".", "4", "1", "9", ".", ".", "5"], [".", ".", ".", ".", "8", ".", ".", "7", "9"]]) #guard solveSudoku_check [["8", ".", ".", ".", "4", ".", "6", "7", "."], ["6", ".", ".", "8", ".", "3", ".", "2", "."], [".", "7", ".", ".", ".", ".", ".", ".", "."], ["1", ".", "6", ".", ".", ".", "7", "5", "9"], [".", "9", ".", "5", ".", "7", "3", "1", "."], ["7", "5", "3", ".", ".", ".", "2", ".", "4"], [".", "4", ".", ".", ".", ".", ".", "6", "."], [".", "3", ".", "9", ".", "8", ".", ".", "7"], [".", ".", "7", ".", "1", ".", ".", ".", "8"]] (solveSudokuImpl [["8", ".", ".", ".", "4", ".", "6", "7", "."], ["6", ".", ".", "8", ".", "3", ".", "2", "."], [".", "7", ".", ".", ".", ".", ".", ".", "."], ["1", ".", "6", ".", ".", ".", "7", "5", "9"], [".", "9", ".", "5", ".", "7", "3", "1", "."], ["7", "5", "3", ".", ".", ".", "2", ".", "4"], [".", "4", ".", ".", ".", ".", ".", "6", "."], [".", "3", ".", "9", ".", "8", ".", ".", "7"], [".", ".", "7", ".", "1", ".", ".", ".", "8"]]) #guard solveSudoku_check [[".", "2", ".", "1", ".", "4", ".", ".", "."], [".", ".", "4", ".", ".", ".", "6", "3", "."], ["5", ".", ".", ".", "6", ".", ".", "9", "."], ["2", ".", ".", ".", ".", "9", ".", ".", "."], [".", ".", "1", "3", ".", ".", "2", ".", "."], [".", ".", ".", "5", ".", ".", ".", ".", "7"], [".", "1", "6", ".", "4", ".", ".", "2", "."], [".", "5", ".", ".", ".", ".", "9", ".", "."], ["7", ".", ".", "8", ".", "1", ".", "4", "."]] (solveSudokuImpl [[".", "2", ".", "1", ".", "4", ".", ".", "."], [".", ".", "4", ".", ".", ".", "6", "3", "."], ["5", ".", ".", ".", "6", ".", ".", "9", "."], ["2", ".", ".", ".", ".", "9", ".", ".", "."], [".", ".", "1", "3", ".", ".", "2", ".", "."], [".", ".", ".", "5", ".", ".", ".", ".", "7"], [".", "1", "6", ".", "4", ".", ".", "2", "."], [".", "5", ".", ".", ".", ".", "9", ".", "."], ["7", ".", ".", "8", ".", "1", ".", "4", "."]]) end PSudokuSolver