6
$\begingroup$

On a rectangular $ 4 \times 2016 $ chessboard, a knight begins in the lower left corner, makes several knight moves, visits all squares of the chessboard at least once and in the end returns to the starting position.

Find the minimal number of squares that the knight must visit more than one time.

$\endgroup$
9
$\begingroup$

Besides the starting square,

the knight must visit two additional squares twice.

The images below show one possible tour:

The 2016 columns can be divided up into groups of three. The knight travels to to the far end (the red path), visiting half of the squares, then returns along the blue path to a square adjacent to the starting corner. The middle section can be repeated (flipped vertically each time) to extend the width of the board to any multiple of three, including 2016.
knight's tour
Then it's a simple matter to return to the starting square by revisiting two already visited squares:
completing the circuit

This tour uses the "domino pattern" from this paper: K. McGown and A. Leininger. "Knight's Tour." REU at Oregon State University. August, 2002. In that paper, they also show that

there are no circuits that don't repeat any squares on a $4 \times m$ board (Theorom 3.15). Two repeated squares must therefore be the minimum, because to return to the original square, the number of visited squares must be even, due to the way knights always move between the black and white squares on a chessboard, and repeating one square would result in an odd number of moves.

Though the above technique only works for $4 \times m$ boards where $m$ is a multiple of $3$, it should be possible to find

a closed tour that visits exactly two squares more than once on $4 \times m$ boards for all $m > 4$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.