pith. sign in

arxiv: 2603.01675 · v2 · pith:LHZB4Z6Pnew · submitted 2026-03-02 · 💻 cs.CC

Completing the Complexity Classification of 2-Solo Chess: Knights and Kings are Hard

Kolja K\"uhn , Wendy Yi This is my paper

Pith reviewed 2026-05-21 12:42 UTC · model grok-4.3

classification 💻 cs.CC
keywords 2-Solo ChessNP-completenesscomplexity classificationknightskingschess problemscomputational complexityreductions
0
0 comments X

The pith

2-Solo Chess is NP-complete even when restricted to boards with only knights or only kings.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper completes the complexity classification of 2-Solo Chess, a single-player capture puzzle in which each piece may capture at most twice before the board must be reduced to one piece. Prior results already placed the problem in P for pawns alone and in NP-complete for rooks, bishops, or queens alone. The new proofs establish NP-completeness for the remaining two cases of knights alone and kings alone. A reader would care because the result shows that, for every standard chess piece type except pawns, deciding whether a given 2-Solo Chess position can be cleared is computationally intractable in the worst case.

Core claim

We prove that 2-Solo Chess is NP-complete if the instance contains only knights or only kings. The proofs are by polynomial-time reductions from known NP-complete problems that produce valid 2-Solo Chess instances using only the target piece type while preserving yes and no answers.

What carries the argument

Polynomial-time reductions that map yes/no instances of a known NP-complete problem onto 2-Solo Chess boards populated exclusively by knights or exclusively by kings.

If this is right

  • Deciding whether a knight-only or king-only 2-Solo Chess position can be cleared requires exponential time in the worst case unless P equals NP.
  • The only standard chess piece type for which 2-Solo Chess stays in P is the pawn.
  • Any practical solver for general 2-Solo Chess must fall back to exponential search when knights or kings are present.
  • The hardness holds even though each piece is limited to at most two captures.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Piece movement rules alone can shift a capture puzzle from polynomial to NP-complete, suggesting similar thresholds exist in other board-game problems.
  • One could test whether adding a single knight or king to an otherwise polynomial pawn instance immediately renders the problem hard.
  • The classification invites analogous complexity results for 3-Solo Chess or for variants that relax the two-capture limit.

Load-bearing premise

The constructed reductions from a known NP-complete problem correctly map solvable instances to solvable 2-Solo Chess positions and unsolvable instances to unsolvable positions.

What would settle it

Discovery of a polynomial-time algorithm that correctly decides every 2-Solo Chess instance consisting solely of knights (or solely of kings).

read the original abstract

We extend the study of the 2-Solo Chess problem which was first introduced by Aravind, Misra, and Mittal in 2022. 2-Solo Chess is a single-player variant of chess in which the player must clear the board via captures such that only one piece remains, with each piece capturing at most twice. It is known that the problem is solvable in polynomial time for instances containing only pawns, while it becomes NP-complete for instances restricted to rooks, bishops, or queens. In this work, we complete the complexity classification by proving that 2-Solo Chess is NP-complete if the instance contains only knights or only kings.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper extends prior work on 2-Solo Chess (a single-player capture-to-one-piece problem with an at-most-two-captures-per-piece rule) by proving NP-completeness for the knight-only and king-only restrictions, thereby completing the complexity classification across all standard chess pieces (previously known to be in P for pawns and NP-complete for rooks, bishops, and queens).

Significance. If the reductions are valid, the result is significant: it supplies the missing cases in the complexity map of 2-Solo Chess and demonstrates that the two-capture bound does not render the problem tractable for knights or kings. The work follows the standard reduction-based approach for establishing NP-completeness in combinatorial games.

major comments (2)
  1. [§3] §3 (Knight reduction): The gadget construction must be shown to preserve yes/no answers under the explicit global constraint that each piece captures at most twice. The manuscript describes piece placements and intended capture sequences but does not contain a lemma or case analysis verifying that no simulating sequence requires a piece to exceed two captures (or that any such sequence can be disallowed without altering the reduction's correctness). This equivalence is load-bearing for the NP-completeness claim.
  2. [§4] §4 (King reduction): Analogous verification is required for the king gadgets. Because kings have limited mobility, it is possible that the two-capture bound interacts with the gadget in a way that either admits spurious solutions or blocks valid ones; the text does not supply an explicit argument that the reduction remains answer-preserving once the capture limit is enforced.
minor comments (2)
  1. [Abstract] The abstract and introduction should cite the exact source problem (e.g., 3-SAT or Vertex Cover) used in each reduction for immediate clarity.
  2. [§3 and §4] Notation for board positions and capture sequences could be made uniform across the knight and king sections to ease comparison.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading of the manuscript and for the constructive comments on the need for explicit verification of the two-capture constraint. We agree that additional formal arguments are required to fully establish that the reductions remain correct under this global restriction. We address each major comment below and will incorporate the necessary additions in the revised version.

read point-by-point responses

  1. Referee: [§3] §3 (Knight reduction): The gadget construction must be shown to preserve yes/no answers under the explicit global constraint that each piece captures at most twice. The manuscript describes piece placements and intended capture sequences but does not contain a lemma or case analysis verifying that no simulating sequence requires a piece to exceed two captures (or that any such sequence can be disallowed without altering the reduction's correctness). This equivalence is load-bearing for the NP-completeness claim.

    Authors: We acknowledge that the current presentation relies on the intended capture sequences without a dedicated lemma ruling out alternatives that might violate the two-capture bound. While the knight gadgets are constructed so that each piece is positioned to participate in at most two captures in any valid clearing sequence (due to the linear capture chains and isolation of gadgets), we agree an explicit case analysis is needed to confirm no spurious sequences exceed the limit or that such sequences fail to clear the board. In the revision we will add Lemma 3.1 providing this exhaustive local analysis for each gadget type, proving equivalence under the capture constraint. revision: yes

  2. Referee: [§4] §4 (King reduction): Analogous verification is required for the king gadgets. Because kings have limited mobility, it is possible that the two-capture bound interacts with the gadget in a way that either admits spurious solutions or blocks valid ones; the text does not supply an explicit argument that the reduction remains answer-preserving once the capture limit is enforced.

    Authors: We agree that the restricted movement of kings makes interaction with the capture bound particularly important to verify explicitly. The king gadgets were designed with short capture paths and mobility constraints that limit each king to at most two captures in valid solutions, but we did not include a formal argument addressing potential spurious or blocked sequences. We will add a corresponding lemma (Lemma 4.1) with case analysis on king moves and captures within the gadgets to confirm that the reduction preserves yes/no answers under the two-capture rule. revision: yes

Circularity Check

0 steps flagged

Standard NP-completeness reductions with no circularity

full rationale

The paper extends an existing definition of 2-Solo Chess from prior independent work (Aravind et al. 2022) and proves NP-completeness for knight-only and king-only instances via polynomial-time reductions from known NP-complete source problems. No equations, self-definitional steps, fitted parameters renamed as predictions, or load-bearing self-citations appear; the cited polynomial-time and NP-completeness results for other piece types are external. The derivation chain therefore remains self-contained against external benchmarks and does not reduce to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Proof relies on standard definitions of NP-completeness and polynomial reductions from prior literature; no free parameters or invented entities appear in the abstract.

axioms (1)
  • standard math Standard definitions of NP-completeness via polynomial-time reductions
    Invoked implicitly when claiming NP-completeness for the new piece types.

pith-pipeline@v0.9.0 · 5638 in / 964 out tokens · 33231 ms · 2026-05-21T12:42:57.225158+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.