Observation 29 — 21(c₁−c₂) ± 7(a₁−a₂) ± (d₁−d₂) = 0 forces c₁ = c₂, a₁ = a₂, d₁ = d₂
ProvedNQueensComp.NPC.observation_29arithmeticgadgetsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Observation 29. Let be integers with and , and let . If
then , and .
The column spacing between variable gadgets and the row spacing inside clause gadgets were chosen so that this holds; it is what makes the diagonals of different gadgets in the reduction from Restricted 1-in-3-SAT distinct (Lemmas 30 and 32).
Formalization Note The two printed signs are independent; they are the parameters .
Differences from the source:
- encoding: the two signs ± in 21(c₁ − c₂) ± 7(a₁ − a₂) ± (d₁ − d₂) → independent sign parameters s₁, s₂ ∈ {1, −1}; reason: the four sign choices are exactly the four instances
Preamble
import Mathlib import Definitions.Def_NQueensComp_NPC_Queens
Formal statement
namespace NQueensComp.NPC
/-- Observation 29, p. 834: for integers `a₁, a₂, c₁, c₂, d₁, d₂` with `0 ≤ a₁, a₂ ≤ 2` and
`0 ≤ d₁, d₂ ≤ 6`, if `21(c₁ − c₂) ± 7(a₁ − a₂) ± (d₁ − d₂) = 0` (either choice of each sign) then
`c₁ = c₂`, `a₁ = a₂` and `d₁ = d₂`. -/
theorem observation_29 (a₁ a₂ c₁ c₂ d₁ d₂ s₁ s₂ : ℤ)
(ha₁ : 0 ≤ a₁ ∧ a₁ ≤ 2) (ha₂ : 0 ≤ a₂ ∧ a₂ ≤ 2) (hd₁ : 0 ≤ d₁ ∧ d₁ ≤ 6)
(hd₂ : 0 ≤ d₂ ∧ d₂ ≤ 6) (hs₁ : s₁ = 1 ∨ s₁ = -1) (hs₂ : s₂ = 1 ∨ s₂ = -1)
(h : 21 * (c₁ - c₂) + s₁ * (7 * (a₁ - a₂)) + s₂ * (d₁ - d₂) = 0) :
c₁ = c₂ ∧ a₁ = a₂ ∧ d₁ = d₂ := by sorry
end NQueensComp.NPC
Source
Gent, Jefferson & Nightingale, Complexity of n-Queens Completion, J. Artif. Intell. Res. 59 (2017), p. 834, Observation 29
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.