Lemma 8 (Rivin–Zabih) — exchanging a subset for one with the same lines (corrected: |P₁| = |P| added)
ProvedNQueensComp.NPC.lemma_8n-queensp2o-batch-pfp2ap2o-correctedp2o-gran-per-chapterp2o-plan-paperp2o-v1
Lemma 8 (Rivin and Zabih), corrected. Let be a solution to the -Queens problem and . If is a set of queens with that uses the same set of rows, the same set of columns, the same set of sum-diagonals and the same set of difference-diagonals as , then
is also a solution to the -Queens problem.
Definition 10 uses it to replace the copy by in Lemma 12.
Differences from the source:
- correction: Lemma 8 has no hypothesis on the size of P₁ → adds |P₁| = |P|; reason: false as printed: n = 4, Q = P = {(1,0), (3,1), (0,2), (2,3)} and P₁ = Q ∪ {(2,0), (0,1), (3,2), (1,3)} use the same rows, columns, sum-diagonals {1, 2, 4, 5} and difference-diagonals {−2, −1, 1, 2}, but (Q \ P) ∪ P₁ has 8 queens; the paper's use (Lemma 12) has |P₁| = |P| = n′
Preamble
import Mathlib import Definitions.Def_NQueensComp_NPC_Queens
Formal statement
namespace NQueensComp.NPC
/-- Lemma 8 (Rivin and Zabih), p. 823, corrected: if `Q` is a solution to the `n`-Queens
problem, `P ⊆ Q`, and `P₁` is a set of queens with `|P₁| = |P|` (added; the printed lemma is false
without it) that uses the same sets of rows, columns, sum-diagonals and difference-diagonals as `P`,
then `(Q \ P) ∪ P₁` is a solution to the `n`-Queens problem. -/
theorem lemma_8 (n : ℕ) (Q P P₁ : Finset Queen) (hQ : IsNQueensSol n Q) (hPQ : P ⊆ Q)
(hcard : P₁.card = P.card)
(hrow : P₁.image row = P.image row) (hcol : P₁.image col = P.image col)
(hsum : P₁.image sumDiag = P.image sumDiag) (hdiff : P₁.image diffDiag = P.image diffDiag) :
IsNQueensSol n ((Q \ P) ∪ P₁) := by sorry
end NQueensComp.NPC
Source
Gent, Jefferson & Nightingale, Complexity of n-Queens Completion, J. Artif. Intell. Res. 59 (2017), p. 823, Lemma 8 (Rivin & Zabih 1992, Thm. 2.4)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.