Library

The Optimal Knight Exchange Puzzle is NP-Hard

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.

Artificial Intelligence in GamesPolynomial and algebraic computationFormal Methods in Verification
Source

Paper

Similar papers

Proving the existence of Euclidean knight's tours on $n \times n \times \cdots \times n$ chessboards for $n < 4$Marco Ripà2023 · arXiv (Cornell University) In Library
Proving the existence of Euclidean knight’s tours on n × n × ⋯ × n chessboards for n < 4World Intelligence Network, Marco Ripà2024 · Notes on Number Theory and Discrete Mathematics In Library
Edge Matching with Inequalities, Triangles, Unknown Shape, and Two PlayersJeffrey Bosboom, Charlotte Chen, Lily Chung et al.2020 · arXiv (Cornell University) In Library
Chess Tour Solver: A Formal Framework and Reference Architecture for Generalized Chess Piece Tour EnumerationShakunth S2026 · Zenodo (CERN European Organization for Nuclear Research) In Library
Chess Tour Solver: A Formal Framework and Reference Architecture for Generalized Chess Piece Tour EnumerationShakunth S2026 · Zenodo (CERN European Organization for Nuclear Research) In Library
Completing the Complexity Classification of 2-Solo Chess: Knights and Kings are HardKolja Kühn, Wendy Yi2026 · Open MIND In Library
Completing the Complexity Classification of 2-Solo Chess: Knights and Kings Are HardKolja Kühn, Wendy Yi, John Iacono2026 · KITopen In Library
Complexity of Retrograde and Helpmate Chess Problems: Even Cooperative Chess Is Hard.Josh Brunner, Erik D. Demaine, Dylan Hendrickson et al.2020 · DSpace@MIT (Massachusetts Institute of Technology) In Library
Queen v KnightSimon Whitaker2026 · Zenodo (CERN European Organization for Nuclear Research) In Library
Queen v KnightSimon Whitaker2026 · Zenodo (CERN European Organization for Nuclear Research) In Library
© 2026 NYSGPT2525 LLC