Observation 6 — the properties of Q₁₉
ProvedNQueensComp.NPC.observation_6n-queensp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Observation 6. The set of Definition 5 satisfies:
- it is a solution to the 19-Queens problem;
- it has no queen on difference-diagonals , or ;
- for its queens and consider the squares and : their sum-diagonals are not within of each other, of or of any queen of , and the same holds for their difference-diagonals:
and , .
These are the properties of the 19-queens frame that the reduction of Definition 10 uses through Lemma 9.
Differences from the source:
- reading: “their sum-/difference-diagonals are not within 1 of each other, (0, 0) or any queen in Q₁₉” → sum-diagonals are compared with sum-diagonals and difference-diagonals with difference-diagonals, each difference at least 2 in absolute value; reason: the “sum-/difference-” notation is used respectively throughout the paper (Lemma 9)
Preamble
import Mathlib import Definitions.Def_NQueensComp_NPC_Queens
Formal statement
namespace NQueensComp.NPC
/-- Observation 6, p. 822: `Q₁₉` is a solution to the 19-Queens problem; it has no queen on
difference-diagonals `1, 0, −1`; for its queens `(0, 8)` and `(17, 0)` consider `(19, 8)` and
`(17, 19)`: their sum-diagonals (respectively difference-diagonals) are not within `1` of each
other, of `(0, 0)` or of any queen of `Q₁₉`. -/
theorem observation_6 :
IsNQueensSol 19 Q19 ∧
(∀ q ∈ Q19, diffDiag q ≠ 1 ∧ diffDiag q ≠ 0 ∧ diffDiag q ≠ -1) ∧
((0, 8) ∈ Q19 ∧ (17, 0) ∈ Q19) ∧
(1 < |((sumDiag (19, 8) : ℕ) : ℤ) - ((sumDiag (17, 19) : ℕ) : ℤ)| ∧
1 < |diffDiag (19, 8) - diffDiag (17, 19)|) ∧
∀ m ∈ ({(19, 8), (17, 19)} : Finset Queen), ∀ p ∈ insert ((0, 0) : Queen) Q19,
1 < |((sumDiag m : ℕ) : ℤ) - ((sumDiag p : ℕ) : ℤ)| ∧
1 < |diffDiag m - diffDiag p| := by sorry
end NQueensComp.NPC
Source
Gent, Jefferson & Nightingale, Complexity of n-Queens Completion, J. Artif. Intell. Res. 59 (2017), p. 822, Observation 6 (Definition 5)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.