pith. sign in

arxiv: 2606.29153 · v1 · pith:L4XQ3ZQSnew · submitted 2026-06-28 · 💻 cs.DM · cs.CC

The Optimal Knight Exchange Puzzle is NP-Hard

Henry Siegel This is my paper

Pith reviewed 2026-06-30 02:30 UTC · model grok-4.3

classification 💻 cs.DM cs.CC
keywords Knight's TourKnight ExchangeNP-hardnesscomputational complexitychess puzzlesconnected boardspolynomial-time reduction
0
0 comments X

The pith

Knight's Tour on connected boards is NP-hard, and optimal Knight Exchange reduces from it in polynomial time.

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

The paper proves that finding a knight's tour remains NP-hard even when the board is connected and has no holes. It then supplies a polynomial-time reduction that carries this hardness over to the problem of finding the shortest sequence of knight moves that swaps two pieces. A reader would care because these results close a gap between rectangular boards, where tours are easy, and boards with holes, where tours are already known to be hard. The reduction shows that computing an optimal knight exchange inherits the same intractability.

Core claim

We show that Knight's Tour is NP-hard for connected boards. We also give a short polynomial-time reduction between the two problems, showing that the optimality version of Knight Exchange is NP-hard.

What carries the argument

A short polynomial-time reduction from connected-board Knight's Tour instances to optimal Knight Exchange instances that preserves hardness.

If this is right

  • Knight's Tour is NP-hard on every connected board shape.
  • Optimal Knight Exchange cannot be solved in polynomial time unless P equals NP.
  • The two problems are computationally equivalent under polynomial reductions.

Where Pith is reading between the lines

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

  • Similar reductions could establish hardness for knight movement puzzles with other objectives on connected boards.
  • Any practical program that claims to solve these puzzles quickly must fail on some inputs.
  • The same technique might apply to tours or exchanges using other chess pieces on connected regions.

Load-bearing premise

The constructed exchange instances remain hard precisely when the connected tour instances are hard.

What would settle it

Either a polynomial-time algorithm that solves optimal Knight Exchange on every connected board, or an explicit connected board on which Knight's Tour is solvable in polynomial time.

Figures

Figures reproduced from arXiv: 2606.29153 by Henry Siegel.

Figure 1
Figure 1. Figure 1: This particular puzzle appeared in the video game [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: One can check that it is possible to swap the black and white pebbles on [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: G is a four-cycle, and G′ contains two additional vertices x and y attached to 0 as shown. In this example, n = 4. 8 [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: A grid graph and the resulting construction is shown. Each vertex in the grid graph gets mapped to a 9 [PITH_FULL_IMAGE:figures/full_fig_p009_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: A board is k−connected if its vertex in the grid graph has k edges. Transition squares are entry/leaving points to other chessboards. For any pair of transition squares on the unique 4-connected board up to symmetry, there is an open knight’s tour. The visit times on each square is enumerated, and transition squares are circled [PITH_FULL_IMAGE:figures/full_fig_p012_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: For every pair of transition squares on two 3-connected board up to symmetry, there is a knight’s tour. [PITH_FULL_IMAGE:figures/full_fig_p012_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: For every pair of transition squares on three 2-connected board up to symmetry, there is a knight’s tour. [PITH_FULL_IMAGE:figures/full_fig_p012_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: For both types of 1-connected boards, up to symmetry, there is a knight’s tour starting on the transition [PITH_FULL_IMAGE:figures/full_fig_p013_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: In our reduction to closed and open knight’s tour, the chessboards coming from vertices on the right edge [PITH_FULL_IMAGE:figures/full_fig_p013_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Shown above is an example of a chessboard that cannot be nicely extended. No matter how two additional [PITH_FULL_IMAGE:figures/full_fig_p013_10.png] view at source ↗
read the original abstract

This paper explores the hardness of two popular recreational chess puzzles: The Knight's Tour and the Knight Exchange (Swap). The problem of finding a Knight's Tour is known to be NP-hard for any chessboard with holes and constant-time decidable for rectangular chessboards, so a natural direction is to explore the hardness of the problem for intermediate chessboard restrictions. In this paper, we show that Knight's Tour is NP-hard for connected boards. We also give a short polynomial-time reduction between the two problems, showing that the optimality version of Knight Exchange is NP-hard.

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

0 major / 2 minor

Summary. The paper claims that the Knight's Tour problem is NP-hard even when restricted to connected boards (extending prior results for boards with holes) and provides an explicit short polynomial-time reduction from connected-board Knight's Tour instances to optimal Knight Exchange instances, establishing NP-hardness for the optimality version of the latter problem.

Significance. If the constructions hold, the result fills an intermediate case in the complexity of knight's tour variants and directly transfers hardness to the optimization version of Knight Exchange. The manuscript supplies both the connected-board construction and the explicit reduction, which is a strength for verifiability in a complexity paper.

minor comments (2)
  1. [Abstract] Abstract: the phrase 'constant-time decidable for rectangular chessboards' would benefit from a brief parenthetical reference to the known result (e.g., the polynomial-time algorithm) to orient readers unfamiliar with the background.
  2. The reduction is described as 'short'; including a high-level pseudocode or diagram of the instance mapping (even if the full proof is in the text) would improve readability without lengthening the paper substantially.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary and recommendation of minor revision. The assessment correctly captures the paper's contributions on NP-hardness for connected-board Knight's Tour and the explicit reduction to optimal Knight Exchange.

Circularity Check

0 steps flagged

No significant circularity; derivation builds on external known result with explicit new constructions

full rationale

The paper cites an external result (Knight's Tour NP-hard on boards with holes) and then supplies its own constructions: a proof that the problem remains NP-hard on connected boards, plus an explicit polynomial-time reduction to the optimality version of Knight Exchange. Neither step reduces by definition or self-citation to the paper's own inputs; the reduction is described as direct and hardness-preserving. No fitted parameters, self-definitional loops, or load-bearing self-citations appear in the claimed chain. This is the normal case of a reduction proof that remains independent of its target result.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Only abstract available; no free parameters, invented entities, or non-standard axioms visible. Relies on standard definitions of NP-hardness and polynomial reductions.

axioms (1)
  • standard math Standard definitions of NP-completeness and polynomial-time reductions from prior literature on Knight's Tour hardness
    Invoked implicitly to transfer hardness via the stated reduction

pith-pipeline@v0.9.1-grok · 5605 in / 1151 out tokens · 43022 ms · 2026-06-30T02:30:54.796750+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

13 extracted references · 4 canonical work pages · 1 internal anchor

  1. [1]

    Schwenk (1991).Which Rectangular Chessboards Have a Knight’s Tour? Mathematics Magazine, 64, 325–332

    A. Schwenk (1991).Which Rectangular Chessboards Have a Knight’s Tour? Mathematics Magazine, 64, 325–332. https://doi.org/10.1080/0025570x.1991.11977627

    work page doi:10.1080/0025570x.1991.11977627 1991

  2. [2]

    Goraly and R

    G. Goraly and R. Hassin.Multi-Color Pebble Motion on Graphs.Algorithmica, 2010

    2010

  3. [3]

    Calinescu, A

    G. Calinescu, A. Dumitrescu, and J. Pach.Reconfigurations in graphs and grids.SIAM Journal on Discrete Mathematics, 22(1):124–138, 2008

    2008

  4. [4]

    Iordan.Optimal Solutions for the Knight Exchange on4n×4nChessboards

    M. Iordan.Optimal Solutions for the Knight Exchange on4n×4nChessboards. 2019

    2019

  5. [5]

    Iranpoor.Knights Exchange Puzzle—Teaching the Efficiency of Modeling.INFORMS Transactions on Edu- cation, 2021

    R. Iranpoor.Knights Exchange Puzzle—Teaching the Efficiency of Modeling.INFORMS Transactions on Edu- cation, 2021

    2021

  6. [6]

    Goldreich.Finding the Shortest Move-Sequence in the Graph-Generalized 15-Puzzle Is NP-Hard

    O. Goldreich.Finding the Shortest Move-Sequence in the Graph-Generalized 15-Puzzle Is NP-Hard. 1984

    1984

  7. [7]

    Geft.On the Hardness of Optimal Motion on Trees

    T. Geft.On the Hardness of Optimal Motion on Trees. arXiv preprint arXiv:2606.00000, June 2026

    work page arXiv 2026

  8. [8]

    McGown and A

    K. McGown and A. Leininger.Knight’s Tour. Oregon State University REU Proceedings, August 15, 2002

    2002

  9. [9]

    A. Itai, C. H. Papadimitriou, and J. L. Szwarcfiter.Hamiltonian Paths in Grid Graphs. SIAM Journal on Computing, 11(4):676–686, November 1982

    1982

  10. [10]

    E. D. Demaine and M. Rudoy.Hamiltonicity is Hard in Thin or Polygonal Grid Graphs, but Easy in Thin Polygonal Grid Graphs. arXiv preprint arXiv:1706.10046, June 2017

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  11. [11]

    Conrad, T

    A. Conrad, T. Hindrichs, H. Morsy, and I. Wegener.Solution of the knight’s Hamiltonian path problem on chessboards.Discrete Applied Mathematics, 50(2):125–134, 1994. 6

    1994

  12. [12]

    D. M. Kornhauser, G. L. Miller, and P. G. Spirakis.Coordinating Pebble Motion on Graphs, the Diameter of Permutation Groups, and Applications. MIT Laboratory for Computer Science Technical Report MIT-LCS-TR- 320, 1984

    1984

  13. [13]

    Ardizzoni, I

    S. Ardizzoni, I. Saccani, L. Consolini, M. Locatelli, and B. Nebel. An algorithm with improved complexity for pebble motion/multi-agent path finding on trees. Journal of Artificial Intelligence Research, 79:483–514, 2024. https://doi.org/10.1613/jair.1.15249 7 Appendix 0 4 5 6 1 2 3 8 y x Figure 2: One can check that it is possible to swap the black and w...

    work page doi:10.1613/jair.1.15249 2024