Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 9 — n-scaled queens whose offsets differ enough do not attack

Proved
NQueensComp.NPC.lemma_9

by mikedeng1 · Oct 24, 2026 · Mathlib 0df444a (Lean v4.33.1)

combinatoricsn-queensp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1

Let n≥1n\ge1n≥1, let q1,q2q_1,q_2q1​,q2​ be queens that fit on board size nnn, and let q3,q4q_3,q_4q3​,q4​ be queens of any size.

Lemma 9.

  1. If col(q3)≠col(q4)\mathrm{col}(q_3)\ne\mathrm{col}(q_4)col(q3​)=col(q4​), then col(q1+nq3)≠col(q2+nq4)\mathrm{col}(q_1+nq_3)\ne\mathrm{col}(q_2+nq_4)col(q1​+nq3​)=col(q2​+nq4​).
  2. If row(q3)≠row(q4)\mathrm{row}(q_3)\ne\mathrm{row}(q_4)row(q3​)=row(q4​), then row(q1+nq3)≠row(q2+nq4)\mathrm{row}(q_1+nq_3)\ne\mathrm{row}(q_2+nq_4)row(q1​+nq3​)=row(q2​+nq4​).
  3. If the sum-diagonals of q3,q4q_3,q_4q3​,q4​ differ by more than one, then the sum-diagonals of q1+nq3q_1+nq_3q1​+nq3​ and q2+nq4q_2+nq_4q2​+nq4​ differ.
  4. If the difference-diagonals of q3,q4q_3,q_4q3​,q4​ differ by more than one, then the difference-diagonals of q1+nq3q_1+nq_3q1​+nq3​ and q2+nq4q_2+nq_4q2​+nq4​ differ.
  5. If all four hypotheses hold, then q1+nq3q_1+nq_3q1​+nq3​ does not attack q2+nq4q_2+nq_4q2​+nq4​:
col≠, row≠, ∣Σ3−Σ4∣>1, ∣Δ3−Δ4∣>1 ⟹ q1+nq3 does not attack q2+nq4,\mathrm{col}\ne,\ \mathrm{row}\ne,\ |\Sigma_3-\Sigma_4|>1,\ |\Delta_3-\Delta_4|>1\ \Longrightarrow\ q_1+nq_3 \text{ does not attack } q_2+nq_4,col=, row=, ∣Σ3​−Σ4​∣>1, ∣Δ3​−Δ4​∣>1 ⟹ q1​+nq3​ does not attack q2​+nq4​,

where Σ\SigmaΣ and Δ\DeltaΔ denote sum- and difference-diagonals.

This is the basic tool for embedding sub-boards of size nnn into a coarser grid without interference (Definitions 10 and 20).

Differences from the source: none.

Preamble
import Mathlib
import Definitions.Def_NQueensComp_NPC_Queens
Formal statement
namespace NQueensComp.NPC

/-- Lemma 9, p. 824: let `q₁, q₂` fit on board size `n` and let `q₃, q₄` be any queens.  If the
columns (rows) of `q₃, q₄` differ, so do the columns (rows) of `q₁ + nq₃` and `q₂ + nq₄`; if the
sum-diagonals (difference-diagonals) of `q₃, q₄` differ by more than one, then the sum-diagonals
(difference-diagonals) of `q₁ + nq₃` and `q₂ + nq₄` differ; if all four hold, `q₁ + nq₃` does not
attack `q₂ + nq₄`. -/
theorem lemma_9 (n : ℕ) (q₁ q₂ q₃ q₄ : Queen) (h₁ : FitsOn n q₁) (h₂ : FitsOn n q₂) :
    (col q₃ ≠ col q₄ → col (q₁ + n • q₃) ≠ col (q₂ + n • q₄)) ∧
    (row q₃ ≠ row q₄ → row (q₁ + n • q₃) ≠ row (q₂ + n • q₄)) ∧
    (1 < |((sumDiag q₃ : ℕ) : ℤ) - ((sumDiag q₄ : ℕ) : ℤ)| →
      sumDiag (q₁ + n • q₃) ≠ sumDiag (q₂ + n • q₄)) ∧
    (1 < |diffDiag q₃ - diffDiag q₄| → diffDiag (q₁ + n • q₃) ≠ diffDiag (q₂ + n • q₄)) ∧
    (col q₃ ≠ col q₄ → row q₃ ≠ row q₄ →
      1 < |((sumDiag q₃ : ℕ) : ℤ) - ((sumDiag q₄ : ℕ) : ℤ)| →
      1 < |diffDiag q₃ - diffDiag q₄| → ¬ Attacks (q₁ + n • q₃) (q₂ + n • q₄)) := by sorry

end NQueensComp.NPC
Source
Gent, Jefferson & Nightingale, Complexity of n-Queens Completion, J. Artif. Intell. Res. 59 (2017), p. 824, Lemma 9
Human review
  • Endorsed by Shuze Chen · Oct 24, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 24, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me