Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 30 — inside each clause gadget G¹_c, G²_c, G³_c the possible queens have distinct diagonals

Proved
NQueensComp.NPC.lemma_30

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

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

Let M6M_6M6​ be an instance of Restricted 1-in-3-SAT and c={vi,vj,vk}c=\{v_i,v_j,v_k\}c={vi​,vj​,vk​} (i<j<ki<j<ki<j<k) one of its clauses, with gadgets Gc1,Gc2,Gc3G^1_c,G^2_c,G^3_cGc1​,Gc2​,Gc3​ of Definitions 27 and 28.

Lemma 30. In each of Gc1,Gc2,Gc3G^1_c,G^2_c,G^3_cGc1​,Gc2​,Gc3​, with columns CiC_iCi​ and rows RiR_iRi​, the difference-diagonals α−β\alpha-\betaα−β of the positions (α,β)∈Ci×Ri(\alpha,\beta)\in C_i\times R_i(α,β)∈Ci​×Ri​ are pairwise distinct, and so are the sum-diagonals α+β\alpha+\betaα+β:

(α,β),(α′,β′)∈Ci×Ri,  α±β=α′±β′ ⟹ (α,β)=(α′,β′).(\alpha,\beta),(\alpha',\beta')\in C_i\times R_i,\ \ \alpha\pm\beta=\alpha'\pm\beta'\ \Longrightarrow\ (\alpha,\beta)=(\alpha',\beta').(α,β),(α′,β′)∈Ci​×Ri​,  α±β=α′±β′ ⟹ (α,β)=(α′,β′).

So inside a clause gadget two queens can only clash along a row or a column, which reduces the count of its solutions to a choice of rows for its columns.

Formalization Note The clause is cs.getD j ∅ for an index j below the length of the clause list; its variables vi<vj<vkv_i<v_j<v_kvi​<vj​<vk​ are its elements in increasing order.

Differences from the source:

  • encoding: V = {vᵢ}, C = {cᵢ}, an arbitrary order of variables and clauses fixed before the reduction (p. 831); a solution is a truth assignment S₆ : V → {true, false} → variables are natural numbers ordered increasingly (vᵢ is the i-th smallest element of V); the clauses form a duplicate-free list whose order is the clause order; a solution is the set T ⊆ V of true variables; reason: one admissible choice of the fixed orders; assignments V → {true, false} correspond bijectively to subsets T ⊆ V, so counts agree
Preamble
import Mathlib
import Definitions.Def_NQueensComp_NPC_Reductions
Formal statement
namespace NQueensComp.NPC

/-- Lemma 30, p. 834: within each of `G¹_c, G²_c, G³_c` (columns `Cᵢ`, rows `Rᵢ`), the
difference-diagonals `α − β` with `α ∈ Cᵢ, β ∈ Rᵢ` are all distinct, and so are the sum-diagonals
`α + β`. -/
theorem lemma_30 (cs : Inst6) (hcs : Inst6Valid cs) (j : ℕ) (hj : j < cs.length) :
    ∀ G ∈ [G1 cs j, G2 cs j, G3 cs j],
      (∀ p ∈ G.C ×ˢ G.R, ∀ p' ∈ G.C ×ˢ G.R, diffDiag p = diffDiag p' → p = p') ∧
      (∀ p ∈ G.C ×ˢ G.R, ∀ p' ∈ G.C ×ˢ G.R, sumDiag p = sumDiag p' → p = p') := by sorry

end NQueensComp.NPC
Source
Gent, Jefferson & Nightingale, Complexity of n-Queens Completion, J. Artif. Intell. Res. 59 (2017), p. 834, Lemma 30
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