Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 33 — M₅,c has exactly three solutions, one for each choice of the red variable gadget

Proved
NQueensComp.NPC.lemma_33

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

gadgetsn-queensone-in-three-satp2o-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. M5,cM_{5,c}M5,c​ is the family of six Problem 4 gadgets Gi0,Gj0,Gk0,Gc1,Gc2,Gc3G^0_i,G^0_j,G^0_k,G^1_c,G^2_c,G^3_cGi0​,Gj0​,Gk0​,Gc1​,Gc2​,Gc3​ of Definitions 26–28 and 31. Each Gv0=G0⊕δvG^0_v=G^0\oplus\delta_vGv0​=G0⊕δv​ has a red solution {(0,0),(1,3),(3,2)}+(δv,0)\{(0,0),(1,3),(3,2)\}+(\delta_v,0){(0,0),(1,3),(3,2)}+(δv​,0) and a blue solution {(0,2),(1,0),(3,3)}+(δv,0)\{(0,2),(1,0),(3,3)\}+(\delta_v,0){(0,2),(1,0),(3,3)}+(δv​,0).

Lemma 33. M5,cM_{5,c}M5,c​, as an instance of Problem 5, has exactly three solutions:

∣{S5:S5 solves M5,c}∣=3,\bigl|\{S_5 : S_5 \text{ solves } M_{5,c}\}\bigr|=3,​{S5​:S5​ solves M5,c​}​=3,
  1. in one, Gi0G^0_iGi0​ takes its red solution and Gj0,Gk0G^0_j,G^0_kGj0​,Gk0​ their blue solutions;
  2. in a second, Gj0G^0_jGj0​ is red and Gi0,Gk0G^0_i,G^0_kGi0​,Gk0​ are blue;
  3. in the third, Gk0G^0_kGk0​ is red and Gi0,Gj0G^0_i,G^0_jGi0​,Gj0​ are blue.

Thus the clause gadgets force exactly one variable of each clause to be true, which is what makes the reduction from Restricted 1-in-3-SAT parsimonious.

Formalization Note M5,cM_{5,c}M5,c​ is the list [G⁰ᵢ, G⁰ⱼ, G⁰ₖ, G¹_c, G²_c, G³_c], so positions 0, 1, 2 of a solution are the parts on Gi0,Gj0,Gk0G^0_i,G^0_j,G^0_kGi0​,Gj0​,Gk0​. The clause is taken inside a fixed instance, because the diagonals dv,cxd^x_{v,c}dv,cx​ depend on the rank of ccc among the clauses of vvv.

Differences from the source:

  • encoding: an instance of Problem 5 is a set M₅ = {M₄,ₐ | 0 ≤ a < |M₅|} and a solution a set S₅ = {S₄,ₐ}; the sum-diagonal condition for any {S₄,ₐ, S₄,b} ⊆ S₅ → an instance is a list [M₄,₀, …, M₄,ₖ₋₁], a solution a list [S₄,₀, …] of the same length, and the sum-diagonal condition is imposed for indices a ≠ b; reason: the paper indexes the family itself; read with a = b the condition would forbid every non-empty solution
  • 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 33, p. 835: for a clause `c = c_j = {vᵢ, vⱼ, vₖ}` (`i < j < k`) of an instance `M₆`,
the six-gadget family `M₅,c = [G⁰ᵢ, G⁰ⱼ, G⁰ₖ, G¹_c, G²_c, G³_c]` has exactly three solutions: in
one `G⁰ᵢ` takes its red solution and `G⁰ⱼ, G⁰ₖ` their blue ones; in a second `G⁰ⱼ` is red and
`G⁰ᵢ, G⁰ₖ` blue; in the third `G⁰ₖ` is red and `G⁰ᵢ, G⁰ⱼ` blue. -/
theorem lemma_33 (cs : Inst6) (hcs : Inst6Valid cs) (j : ℕ) (hj : j < cs.length) :
    _root_.Set.ncard {Ss : List (Finset Queen) | Inst5IsSol (M5c cs j) Ss} = 3 ∧
    (∃ Ss, Inst5IsSol (M5c cs j) Ss ∧
      Ss.getD 0 ∅ = redSol (delta cs (clauseVar cs j 0)) ∧
      Ss.getD 1 ∅ = blueSol (delta cs (clauseVar cs j 1)) ∧
      Ss.getD 2 ∅ = blueSol (delta cs (clauseVar cs j 2))) ∧
    (∃ Ss, Inst5IsSol (M5c cs j) Ss ∧
      Ss.getD 0 ∅ = blueSol (delta cs (clauseVar cs j 0)) ∧
      Ss.getD 1 ∅ = redSol (delta cs (clauseVar cs j 1)) ∧
      Ss.getD 2 ∅ = blueSol (delta cs (clauseVar cs j 2))) ∧
    (∃ Ss, Inst5IsSol (M5c cs j) Ss ∧
      Ss.getD 0 ∅ = blueSol (delta cs (clauseVar cs j 0)) ∧
      Ss.getD 1 ∅ = blueSol (delta cs (clauseVar cs j 1)) ∧
      Ss.getD 2 ∅ = redSol (delta cs (clauseVar cs j 2))) := by sorry

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