Knighted Pawn's Tour

The Knighted Pawn’s Tour is a variant of the traditional Knight’s Tour problem, whichitself is an instance of the Hamiltonian cycle problem. The deviation from the Knight’s Tour problem is that a pawn begins on any field on the second rank (row), and advances with legal moves that can include captures to the opposite end of the board to become a knight. These fields, used by the pawn on the path to knighthood, are subsequently forbidden for the knight’s return to the starting field. The knight must traverse the rest of the chessboard, visiting each remaining field exactly once before returning to the pawn’s original starting field, thus completing a Hamiltonian cycle. Because of symmetry, only the A-, B-, C-, and D-pawns need to be considered. For these pawns, we have found that a total of 88 advance paths allow for the completion of a Knighted Pawn’s Tour. In the proof, we first rule out certain advance paths with parity and geometric arguments, and then all remaining advance paths are algorithmically generated and tested.