Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 12 — a solution of M₃ extends by P₂ to a solution of M₂ (Definition 10)

Proved
NQueensComp.NPC.lemma_12

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

n-queensp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1parsimonious-reduction

Let M3=⟨n3,P3,C,R⟩M_3=\langle n_3,P_3,C,R\rangleM3​=⟨n3​,P3​,C,R⟩ be an instance of Problem 3 and M2=⟨n2,P2⟩M_2=\langle n_2,P_2\rangleM2​=⟨n2​,P2​⟩ its image under Definition 10.

Lemma 12. If S3S_3S3​ is a solution to M3M_3M3​, then

S2=S3∪P2S_2=S_3\cup P_2S2​=S3​∪P2​

is a solution to M2M_2M2​.

This is the inverse direction of Lemma 11; it also yields the paper's Corollary 15 on including partial solutions.

Differences from the source:

  • reading: Problem 3 (p. 819) only asks |R| = |C| and α ∉ C, β ∉ R for (α, β) ∈ P → an instance of Problem 3 (and so of Problems 4 and 5) also has C, R ⊆ {0, …, n − 1}; reason: the proofs of Lemmas 11 and 22 use it (“we have α < n₃”, “each max(Cₐ ∪ Rₐ) < nₐ”); without it Theorem 13 is false: ⟨1, {}, {5}, {0}⟩ has the solution {(5, 0)} but Definition 10 outputs a P₂ with (11, 18) and (19, 18) on one row
  • reading: Problems 3 and 4 take n an integer → board size n ≥ 1; reason: Problem 2 instances are built on n-Queens (Problem 1, n ≥ 1); Definition 10 is undefined at n₃ = 0 (n′ = −1)
  • encoding: Definition 10, step 1: n′ = 2n₃ − 1 when n₃ mod 3 ≠ 2 → ℕ subtraction 2 * n₃ - 1; reason: exact because n₃ ≥ 1
Preamble
import Mathlib
import Definitions.Def_NQueensComp_NPC_Reductions
Formal statement
namespace NQueensComp.NPC

/-- Lemma 12, p. 825: for an instance `M₃` of Problem 3 and `M₂ = ⟨n₂, P₂⟩` its image under
Definition 10, if `S₃` is a solution to `M₃` then `S₂ = S₃ ∪ P₂` is a solution to `M₂`. -/
theorem lemma_12 (M : Inst3) (hM : M.Valid) (S₃ : Finset Queen) (hS : M.IsSol S₃) :
    (def10 M).IsSol (S₃ ∪ (def10 M).P) := by sorry

end NQueensComp.NPC
Source
Gent, Jefferson & Nightingale, Complexity of n-Queens Completion, J. Artif. Intell. Res. 59 (2017), p. 825, Lemma 12 (Definition 10, pp. 824–825)
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