Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 17 — a solution of M₄ gives a solution of M₃ (Definition 16)

Proved
NQueensComp.NPC.lemma_17

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

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

Let M4=⟨n,C,R,D−,D+⟩M_4=\langle n,C,R,D^-,D^+\rangleM4​=⟨n,C,R,D−,D+⟩ be an instance of Problem 4 and M3M_3M3​ its image under Definition 16, with QD−={(6n−3−d,3n−1−2d)∣d∈D−}Q_{D^-}=\{(6n-3-d,3n-1-2d)\mid d\in D^-\}QD−​={(6n−3−d,3n−1−2d)∣d∈D−} and QD+={(2n−2−d,n+2d)∣d∈D+}Q_{D^+}=\{(2n-2-d,n+2d)\mid d\in D^+\}QD+​={(2n−2−d,n+2d)∣d∈D+}.

Lemma 17. If S4S_4S4​ is a solution to M4M_4M4​, then

S3=(S4+(3n−2,0))∪QD−∪QD+S_3=\bigl(S_4+(3n-2,0)\bigr)\cup Q_{D^-}\cup Q_{D^+}S3​=(S4​+(3n−2,0))∪QD−​∪QD+​

is a solution to M3M_3M3​.

Together with Lemma 18 this gives the bijection between solutions behind Theorem 19.

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 16: Q_{D⁻} = {(6n − 3 − d, 3n − 1 − 2d)}, Q_{D⁺} = {(2n − 2 − d, n + 2d)}, the shift 3n − 2 and the board 7n − 3 → coordinates computed in ℤ and converted with Int.toNat; 3n − 2 and 7n − 3 in ℕ; reason: for valid instances (n ≥ 1, d in range) every value is ≥ 0, so nothing is truncated
Preamble
import Mathlib
import Definitions.Def_NQueensComp_NPC_Reductions
Formal statement
namespace NQueensComp.NPC

/-- Lemma 17, p. 827: for an instance `M₄ = ⟨n, C, R, D⁻, D⁺⟩` of Problem 4 and `M₃` its image
under Definition 16, if `S₄` is a solution to `M₄` then `S₃ = (S₄ + (3n − 2, 0)) ∪ Q_{D⁻} ∪ Q_{D⁺}`
is a solution to `M₃`. -/
theorem lemma_17 (M : Inst4) (hM : M.Valid) (S₄ : Finset Queen) (hS : M.IsSol S₄) :
    (def16 M).IsSol (lemma17_map M S₄) := by sorry

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