{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreigimbierxlcgdzgnqyqunlg7zy2qqwu64ifxjkek45dlmj6266nme",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mpin6z2zlh42"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2606.29153v1",
  "publishedAt": "2026-06-30T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Henry Siegel"
  ],
  "textContent": "**Authors:** Henry Siegel\n\nThis 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.",
  "title": "The Optimal Knight Exchange Puzzle is NP-Hard"
}