Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 11 — a solution of M₂ restricts to a solution of M₃ (Definition 10)

Proved
NQueensComp.NPC.lemma_11

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 11. If S2S_2S2​ is a solution to M2M_2M2​, then

S3={q∣q∈S2, ∥q∥<n3}S_3=\{q\mid q\in S_2,\ \|q\|<n_3\}S3​={q∣q∈S2​, ∥q∥<n3​}

is a solution to M3M_3M3​.

Together with Lemma 12 this gives the bijection between solutions behind Theorem 13.

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 11, p. 825: for an instance `M₃ = ⟨n₃, P₃, C, R⟩` of Problem 3 and `M₂` its image under
Definition 10, if `S₂` is a solution to `M₂` then `S₃ = {q ∈ S₂ | ‖q‖ < n₃}` is a solution to
`M₃`. -/
theorem lemma_11 (M : Inst3) (hM : M.Valid) (S₂ : Finset Queen) (hS : (def10 M).IsSol S₂) :
    M.IsSol (S₂.filter (fun q => size q < M.n)) := by sorry

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