Lemma 25 — Q solves G iff Q + (δ, 0) solves G ⊕ δ
ProvedNQueensComp.NPC.lemma_25gadgetsn-queensp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
For an instance of Problem 4 with no excluded sum-diagonals and an integer , Definition 24 sets .
Lemma 25. A set of queens is a solution to iff is a solution to :
This lets every variable gadget be a shifted copy of the single gadget , with its two solutions shifted along.
Formalization Note The statement is made for every quadruple with , without requiring it to be a valid instance of Problem 4.
Differences from the source:
- generalization: G an instance of Problem 4 with D⁺ = {} (a gadget) → any G with D⁺ = {}, valid or not; reason: the proof uses only that translation by (δ, 0) preserves attacks and shifts columns and difference-diagonals by δ; every source instance is covered
Preamble
import Mathlib import Definitions.Def_NQueensComp_NPC_Reductions
Formal statement
namespace NQueensComp.NPC
/-- Lemma 25, p. 831: for a gadget `G = ⟨n, C, R, D⁻, {}⟩` and `δ ≥ 0`, a set of queens `Q` is a
solution to `G` iff `Q + (δ, 0)` is a solution to `G ⊕ δ`. -/
theorem lemma_25 (G : Inst4) (hG : G.Dp = ∅) (δ : ℕ) (Q : Finset Queen) :
G.IsSol Q ↔ (G.shift δ).IsSol (shiftSet Q (δ, 0)) := by sorry
end NQueensComp.NPC
Source
Gent, Jefferson & Nightingale, Complexity of n-Queens Completion, J. Artif. Intell. Res. 59 (2017), p. 831, Definition 24 and Lemma 25
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.