Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 19, instance level — Definition 16 preserves validity and the number of solutions

Proved
NQueensComp.NPC.theorem_19_instances

by Victorized · Nov 3, 2026 · Mathlib 0df444a (Lean v4.33.1)

n-queensparsimonious-reduction

Let def16\mathrm{def16}def16 be the construction of Definition 16, which sends an instance of Problem 4 (Excluded Diagonals) to an instance of Problem 3.

Claim (instance-level half of Theorem 19, p. 827). For every valid instance M4M_4M4​ of Problem 4 (Excluded Diagonals), def16(M4)\mathrm{def16}(M_4)def16(M4​) is a valid instance of Problem 3, and the two instances have the same number of solutions:

∣{S:S solves def16(M4)}∣=∣{S:S solves M4}∣.\bigl|\{S : S \text{ solves } \mathrm{def16}(M_4)\}\bigr| = \bigl|\{S : S \text{ solves } M_4\}\bigr|.​{S:S solves def16(M4​)}​=​{S:S solves M4​}​.

The paper proves this through Lemmas 17 and 18, which give solution maps in both directions; the count equality needs in addition that these maps are mutually inverse on solutions. Cardinalities are Set.ncard (an infinite set would count as 000, but both sets here are finite).

This is one of the two halves of NQueensComp.NPC.theorem_19; the other, theorem_19_codes, is the statement about bit codes and polynomial-time computability.

Formalization credit: Wentao Li (Victor), under the Prove2Me account Victorized, with assistance from Claude (Anthropic).

Preamble
import Mathlib
import Definitions.Def_NQueensComp_NPC_Reductions
Formal statement
namespace NQueensComp.NPC

/-- Theorem 19, instance-level half. -/
theorem theorem_19_instances :
    ∀ M : Inst4, M.Valid →
      (def16 M).Valid ∧
        _root_.Set.ncard {S : Finset Queen | (def16 M).IsSol S} =
          _root_.Set.ncard {S : Finset Queen | M.IsSol S} := by sorry

end NQueensComp.NPC
Source
Gent, Jefferson & Nightingale, Complexity of n-Queens Completion, J. Artif. Intell. Res. 59 (2017), p. 827, Theorem 19 (instance-level half)

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