import Mathlib /-! # N Queens The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other. Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order. Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space, respectively. ## Constraints - 1 <= n <= 9 ## Provided examples - `n = 1` → `[["Q"]]` - `n = 3` → `[]` - `n = 2` → `[]` ## Synthesized negative examples - invalid input: `n = 0` ([structural] a predicate that admits 1 <= n <= 9. below the stated minimum) - invalid input: `n = 10` ([structural] a predicate that admits 1 <= n <= 9. past the stated maximum) - invalid input: `n = 100` ([structural] a predicate that admits 1 <= n <= 9. an order of magnitude past the maximum) - `n = 1` → `[]` is wrong ([structural] nothing requires every solution to appear. empty list does no placement work) - `n = 3` → `[["...", "...", "..."], ["Q..", "...", "..."], [".Q.", "...", "..."], ["..Q", "...", "..."], ["...", "Q..", "..."], ["...", ".Q.", "..."], ["...", "..Q", "..."], ["...", "...", "Q.."], ["...", "...", ".Q."], ["...", "...", "..Q"], ["Q..", "..Q", "..."], ["Q..", "...", ".Q."], [".Q.", "...", "Q.."], [".Q.", "...", "..Q"], ["..Q", "Q..", "..."], ["..Q", "...", ".Q."], ["...", "Q..", "..Q"], ["...", "..Q", "Q.."]]` is wrong ([structural] solution boards are not required to contain exactly n queens. non-attacking placements with fewer than n queens are listed as solutions) - `n = 2` → `[["Q.", ".."], [".Q", ".."], ["..", "Q."], ["..", ".Q"]]` is wrong ([structural] queen count is n-1 instead of n. solutions with n-1 queens satisfy a spec with an off-by-one in the count) -/ namespace PNQueens abbrev Input := Nat abbrev Output := List (List String) /-! ### Specification helpers -/ /-- The character at row `i`, column `j` of board `b`, or `none` if either index is out of range. -/ def cellAt (b : List String) (i j : Nat) : Option Char := (b[i]?).bind (fun s => s.toList[j]?) /-- `b` is a valid `n`-queens board: `n` rows of `n` cells over `{'.', 'Q'}` holding exactly `n` queens, no two sharing a row, column, or diagonal. -/ def IsNQueensSolution (n : Nat) (b : List String) : Prop := b.length = n ∧ (∀ row ∈ b, row.toList.length = n ∧ ∀ c ∈ row.toList, c = '.' ∨ c = 'Q') ∧ (b.map String.toList).flatten.count 'Q' = n ∧ ∀ i < n, ∀ j < n, ∀ i' < n, ∀ j' < n, cellAt b i j = some 'Q' → cellAt b i' j' = some 'Q' → (i ≠ i' ∨ j ≠ j') → i ≠ i' ∧ j ≠ j' ∧ i + j' ≠ i' + j ∧ i + j ≠ i' + j' /-! ### Validity predicate (V) -/ /-- Valid input: a board dimension `n` with `1 ≤ n ≤ 9`. -/ def isValidInput (input : Input) : Bool := 1 ≤ input && input ≤ 9 /-! ### Ideal specification (P_spec) -/ /-- `result` lists exactly the valid `n`-queens solutions: every entry is a solution, the entries are pairwise distinct, and every solution appears in `result`. -/ def nQueensSolutions_spec (input : Input) (result : Output) : Prop := (∀ b ∈ result, IsNQueensSolution input b) ∧ result.Nodup ∧ ∀ b : List String, IsNQueensSolution input b → b ∈ result /-! ### Decidable specification (P_check) -/ /-- All length-`n` strings over the alphabet `{'.', 'Q'}`. -/ def dotQStrings : Nat → List String | 0 => [""] | n + 1 => (dotQStrings n).flatMap fun s => [s.push '.', s.push 'Q'] /-- All `k`-row boards whose rows are drawn from `rows`. -/ def boardsOver (rows : List String) : Nat → List (List String) | 0 => [[]] | k + 1 => (boardsOver rows k).flatMap fun b => rows.map fun r => r :: b /-- Every board of `n` rows, each a length-`n` string over `{'.', 'Q'}`; covers all valid `n`-queens solutions. -/ def candidateBoards (n : Nat) : List (List String) := boardsOver (dotQStrings n) n /-- The positions `(row, column)` of the queens on board `b`. -/ def queenCellsOf (b : List String) : List (Nat × Nat) := b.zipIdx.flatMap fun (row, i) => row.toList.zipIdx.filterMap fun (c, j) => if c == 'Q' then some (i, j) else none /-- No two queens on `b` share a row, column, or diagonal. -/ def queensSafe (b : List String) : Bool := let ps := queenCellsOf b ps.all fun p => ps.all fun q => (p.1 == q.1 && p.2 == q.2) || (p.1 != q.1 && p.2 != q.2 && p.1 + q.2 != q.1 + p.2 && p.1 + p.2 != q.1 + q.2) /-- Boolean form of `IsNQueensSolution`: shape, alphabet, queen count, and placement safety. -/ def isSolutionBoard (n : Nat) (b : List String) : Bool := b.length == n && b.all (fun row => row.toList.length == n && row.toList.all (fun c => c == '.' || c == 'Q')) && (b.map String.toList).flatten.count 'Q' == n && queensSafe b /-- Executable checker for `nQueensSolutions_spec`: the completeness clause ranges over the finite `candidateBoards`. -/ def nQueensSolutions_check (input : Input) (result : Output) : Bool := result.all (isSolutionBoard input) && result.eraseDups.length == result.length && (candidateBoards input).all fun b => !(isSolutionBoard input b) || result.contains b theorem root_of_bridges (sb : ∀ n b, isSolutionBoard n b = true ↔ IsNQueensSolution n b) (en : ∀ n b, IsNQueensSolution n b → b ∈ candidateBoards n) (du : ∀ r : Output, r.eraseDups.length = r.length ↔ r.Nodup) (n : Nat) (r : Output) : nQueensSolutions_check n r = true ↔ nQueensSolutions_spec n r := by simp only [nQueensSolutions_check, Bool.and_eq_true, List.all_eq_true, beq_iff_eq, Bool.or_eq_true, Bool.not_eq_true', Bool.eq_false_iff, List.contains_iff_mem, sb, du, nQueensSolutions_spec] constructor · rintro ⟨⟨hs, hd⟩, hc⟩ refine ⟨hs, hd, ?_⟩ intro b hb have hh := hc b (en n b hb) rcases hh with hh | hh · exact False.elim (hh ((sb n b).mpr hb)) · exact hh · rintro ⟨hs, hd, hc⟩ exact ⟨⟨hs, hd⟩, fun b _ => Classical.em (IsNQueensSolution n b) |>.elim (fun h => Or.inr (hc b h)) (fun h => Or.inl (fun ht => h ((sb n b).mp ht)))⟩ theorem queen_mem (b : List String) (i j : Nat) : (i,j) ∈ queenCellsOf b ↔ cellAt b i j = some 'Q' := by simp only [queenCellsOf, List.mem_flatMap, List.mem_filterMap, Prod.exists, List.mk_mem_zipIdx_iff_getElem?] simp only [cellAt, Option.bind_eq_some_iff] constructor · rintro ⟨row, k, hk, c, l, hl, hc⟩ split at hc · rename_i h simp only [beq_iff_eq] at h simp only [Option.some.injEq, Prod.mk.injEq] at hc rcases hc with ⟨rfl, rfl⟩ exact ⟨row, hk, h ▸ hl⟩ · cases hc · rintro ⟨row, hr, hc⟩ exact ⟨row, i, hr, 'Q', j, hc, by simp⟩ theorem cell_bounds (n : Nat) (b : List String) (hb : b.length = n) (hr : ∀ row ∈ b, row.toList.length = n) (i j : Nat) (hq : cellAt b i j = some 'Q') : i < n ∧ j < n := by simp only [cellAt, Option.bind_eq_some_iff] at hq rcases hq with ⟨row, hi, hj⟩ have hm := List.mem_of_getElem? hi have hi' := (List.getElem?_eq_some_iff.mp hi).1 have hj' := (List.getElem?_eq_some_iff.mp hj).1 exact ⟨hb ▸ hi', hr row hm ▸ hj'⟩ theorem safe_bridge (n : Nat) (b : List String) (hb : b.length = n) (hr : ∀ row ∈ b, row.toList.length = n) : queensSafe b = true ↔ ∀ i < n, ∀ j < n, ∀ i' < n, ∀ j' < n, cellAt b i j = some 'Q' → cellAt b i' j' = some 'Q' → (i ≠ i' ∨ j ≠ j') → i ≠ i' ∧ j ≠ j' ∧ i + j' ≠ i' + j ∧ i + j ≠ i' + j' := by simp only [queensSafe, List.all_eq_true, Prod.forall, queen_mem, Bool.or_eq_true, Bool.and_eq_true, beq_iff_eq, bne_iff_ne] constructor · intro hs i hi j hj i' hi' j' hj' hq hq' hn have := hs i j hq i' j' hq' tauto · intro hs i j hq i' j' hq' have ha := cell_bounds n b hb hr i j hq have hc := cell_bounds n b hb hr i' j' hq' have := hs i ha.1 j ha.2 i' hc.1 j' hc.2 hq hq' tauto theorem solution_bridge (n : Nat) (b : List String) : isSolutionBoard n b = true ↔ IsNQueensSolution n b := by simp only [isSolutionBoard, Bool.and_eq_true, List.all_eq_true, beq_iff_eq, Bool.or_eq_true, IsNQueensSolution] constructor · rintro ⟨⟨⟨hb, hr⟩, hc⟩, hs⟩ exact ⟨hb, hr, hc, (safe_bridge n b hb (fun row hm => (hr row hm).1)).mp hs⟩ · rintro ⟨hb, hr, hc, hs⟩ exact ⟨⟨⟨hb, hr⟩, hc⟩, (safe_bridge n b hb (fun row hm => (hr row hm).1)).mpr hs⟩ theorem root_with_solution (en : ∀ n b, IsNQueensSolution n b → b ∈ candidateBoards n) (du : ∀ r : Output, r.eraseDups.length = r.length ↔ r.Nodup) (n : Nat) (r : Output) : nQueensSolutions_check n r = true ↔ nQueensSolutions_spec n r := root_of_bridges solution_bridge en du n r theorem dotQStrings_ofList_mem (l : List Char) (h : ∀ c ∈ l, c = '.' ∨ c = 'Q') : String.ofList l ∈ dotQStrings l.length := by induction l using List.reverseRecOn with | nil => simp [dotQStrings] | append_singleton l c ih => have hl : ∀ d ∈ l, d = '.' ∨ d = 'Q' := by intro d hd exact h d (by simp [hd]) have hc : c = '.' ∨ c = 'Q' := h c (by simp) have him := ih hl rcases hc with rfl | rfl · have heq : String.ofList (l ++ ['.']) = (String.ofList l).push '.' := by apply String.toList_injective simp rw [heq] simp [dotQStrings, him] · have heq : String.ofList (l ++ ['Q']) = (String.ofList l).push 'Q' := by apply String.toList_injective simp rw [heq] simp [dotQStrings, him] theorem dotQStrings_complete (n : Nat) (s : String) (hlen : s.toList.length = n) (halpha : ∀ c ∈ s.toList, c = '.' ∨ c = 'Q') : s ∈ dotQStrings n := by have hm := dotQStrings_ofList_mem s.toList halpha rw [hlen] at hm simpa using hm theorem boardsOver_complete (rows : List String) (b : List String) (hrows : ∀ r ∈ b, r ∈ rows) : b ∈ boardsOver rows b.length := by induction b with | nil => simp [boardsOver] | cons r b ih => have hr : r ∈ rows := hrows r (by simp) have hb : ∀ s ∈ b, s ∈ rows := by intro s hs exact hrows s (by simp [hs]) have hi := ih hb simp [boardsOver, hi, hr] theorem enumeration_bridge : ∀ n b, IsNQueensSolution n b → b ∈ candidateBoards n := by intro n b hb rcases hb with ⟨hlen, hrows, _⟩ have hm : b ∈ boardsOver (dotQStrings n) b.length := by apply boardsOver_complete intro row hrow exact dotQStrings_complete n row (hrows row hrow).1 (hrows row hrow).2 simpa [candidateBoards, hlen] using hm theorem dedup_properties {α : Type} [BEq α] [LawfulBEq α] (l : List α) : List.Sublist l.eraseDups l ∧ l.eraseDups.Nodup := by cases l with | nil => simp | cons a as => rw [List.eraseDups_cons] have ih := dedup_properties (as.filter fun b => !b == a) constructor · exact List.Sublist.cons_cons a (ih.1.trans (List.filter_sublist)) · apply List.nodup_cons.mpr exact ⟨by simp, ih.2⟩ termination_by l.length decreasing_by have := List.length_filter_le (fun b => !b == a) as simp only [List.length_cons] omega theorem dedup_self {α : Type} [BEq α] [LawfulBEq α] (l : List α) (h : l.Nodup) : l.eraseDups = l := by induction l with | nil => simp | cons a as ih => rcases List.nodup_cons.mp h with ⟨hna, hnd⟩ have hf : (as.filter fun b => !b == a) = as := by apply List.filter_eq_self.mpr intro b hb have hn : b ≠ a := fun he => hna (he ▸ hb) simpa using hn rw [List.eraseDups_cons, hf, ih hnd] theorem dedup_bridge (r : Output) : r.eraseDups.length = r.length ↔ r.Nodup := by constructor · intro h have hp := dedup_properties r exact (hp.1.eq_of_length h) ▸ hp.2 · intro h rw [dedup_self r h] theorem root_with_dedup (en : ∀ n b, IsNQueensSolution n b → b ∈ candidateBoards n) (n : Nat) (r : Output) : nQueensSolutions_check n r = true ↔ nQueensSolutions_spec n r := root_with_solution en dedup_bridge n r /-- On valid input the checker accepts exactly the specified outputs. -/ theorem nQueensSolutions_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : nQueensSolutions_check input result ↔ nQueensSolutions_spec input result := by exact root_with_dedup enumeration_bridge input result /-! ### Implementation helpers -/ /-- The length-`n` row string with a queen at column `j` and `'.'` elsewhere. -/ def makeRow (n j : Nat) : String := String.mk ((List.range n).map fun k => if k = j then 'Q' else '.') /-- All completions of the partial board `board` from row `i` onward, keeping only branches whose partial board stays safe. -/ def search (n i : Nat) (board : List String) : List (List String) := if h : i ≥ n then [board] else (List.range n).flatMap fun j => let next := board ++ [makeRow n j] if queensSafe next then search n (i + 1) next else [] termination_by n - i decreasing_by simp_wf <;> omega /-! ### Main algorithm (impl) -/ /-- All `n`-queens solutions by depth-first backtracking over rows, pruning unsafe partial boards. -/ def solveNQueens (input : Input) : Output := search input 0 [] /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem solveNQueens_correct (input : Input) (h : isValidInput input) : nQueensSolutions_spec input (solveNQueens input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput 1 #guard isValidInput 3 #guard isValidInput 2 /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput 0) #guard !(isValidInput 10) #guard !(isValidInput 100) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard nQueensSolutions_check 1 [["Q"]] #guard nQueensSolutions_check 3 [] #guard nQueensSolutions_check 2 [] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(nQueensSolutions_check 1 []) #guard !(nQueensSolutions_check 3 [["...", "...", "..."], ["Q..", "...", "..."], [".Q.", "...", "..."], ["..Q", "...", "..."], ["...", "Q..", "..."], ["...", ".Q.", "..."], ["...", "..Q", "..."], ["...", "...", "Q.."], ["...", "...", ".Q."], ["...", "...", "..Q"], ["Q..", "..Q", "..."], ["Q..", "...", ".Q."], [".Q.", "...", "Q.."], [".Q.", "...", "..Q"], ["..Q", "Q..", "..."], ["..Q", "...", ".Q."], ["...", "Q..", "..Q"], ["...", "..Q", "Q.."]]) #guard !(nQueensSolutions_check 2 [["Q.", ".."], [".Q", ".."], ["..", "Q."], ["..", ".Q"]]) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard solveNQueens 1 == [["Q"]] #guard solveNQueens 3 == [] #guard solveNQueens 2 == [] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard nQueensSolutions_check 1 (solveNQueens 1) #guard nQueensSolutions_check 3 (solveNQueens 3) #guard nQueensSolutions_check 2 (solveNQueens 2) end PNQueens