Lemma 7 — Aₙ and Bₙ are modular solutions with the same diagonals for n ≡ 1, 5 (mod 6)
ProvedNQueensComp.NPC.lemma_7modular-n-queensn-queensp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Lemma 7. If or , then and are modular solutions to the -Queens problem, and
The first part is due to Bell and Stevens (2009, Thm. 9). The second part is what lets Definition 10 swap one copy of for via Lemma 8.
Differences from the source:
- reading: “use the same sets of sum-/difference-diagonals as each other” → equal sets of the integers α + β, and equal sets of the integers α − β; reason: the proof computes the integer values, not residues mod n
Preamble
import Mathlib import Definitions.Def_NQueensComp_NPC_Queens
Formal statement
namespace NQueensComp.NPC
/-- Lemma 7, p. 823: if `n ≡ 1 (mod 6)` or `n ≡ 5 (mod 6)` then `Aₙ` and `Bₙ` are modular
solutions to the `n`-Queens problem, and they use the same set of sum-diagonals and the same set of
difference-diagonals. -/
theorem lemma_7 (n : ℕ) (hn : n % 6 = 1 ∨ n % 6 = 5) :
IsModularSol n (A n) ∧ IsModularSol n (B n) ∧
(A n).image sumDiag = (B n).image sumDiag ∧
(A n).image diffDiag = (B n).image diffDiag := by sorry
end NQueensComp.NPC
Source
Gent, Jefferson & Nightingale, Complexity of n-Queens Completion, J. Artif. Intell. Res. 59 (2017), p. 823, Lemma 7
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.