Knight’s Tours on Rectangular Chessboards Using External Squares

The classic puzzle of finding a closed knight’s tour on a chessboard consists of moving a knight from square to square in such a way that it lands on every square once and returns to its starting point. The 8？×？8 chessboard can easily be extended to rectangular boards, and in 1991, A. Schwenk characterized all rectangular boards that have a closed knight’s tour. More recently, Demaio and Hippchen investigated the impossible boards and determined the fewest number of squares that must be removed from a rectangular board so that the remaining board has a closed knight’s tour. In this paper we define an extended closed knight’s tour for a rectangular chessboard as a closed knight’s tour that includes all squares of the board and possibly additional squares beyond the boundaries of the board and answer the following question: how many squares must be added to a rectangular chessboard so that the new board has a closed knight’s tour? 1. Introduction For many years individuals have been intrigued with the chessboard, not just because of the intricacies and strategies in the game of chess, but also for the many puzzles that have been devised on the board. In addition, mathematicians see these puzzles as special cases of major topics in graph theory. For instance, positioning queens on the board so that none can be captured illustrates independence; choosing the fewest number of squares so that rooks on these squares can attack every square is dominance; and moving a knight from square to square in such a way that it lands on every square once and returns to its starting point is an example of a Hamiltonian cycle. One source that surveys the history and results of many chessboard puzzles, as well as summarizing variations and extensions to other surfaces, is [1]. Specifically for the knight’s tour problem, if we label each square on an 8 × 8 chessboard with an ordered pair using its row and column position, and assign (1, 1) to the upper left square, then a knight beginning at (r, c) can legally move to any of the eight squares (r ± 2, c ± 1) or (r ± 1, c ± 2) unless (r, c) is too close to the edge of the board. An open knight’s tour (sometimes called a path) consists of a sequence of legal moves so that a knight lands on each square exactly once. See Figure 1 for some examples that will be used later where the tours begin at the square labeled or 1 and end at squares or 20. A closed knight’s tour has the added condition that the knight must end its tour on the initial square. The 8 × 8 chessboard can easily be extended to rectangular boards, and in 1991,