Problem of the Week 1154

The Wandering Bishop

Suppose a bishop is on the lower left square (assumed to be white) of an 11 × 16 chessboard. Find a sequence of bishop moves that allows him to visit each white square once and only once, ending up back at the start. Note that a move from A to B that passes over square C is not counted as having visited C.

Harder, but doable: For which pairs of positive integers (m, n) does the (white) bishop graph B(m, n) on an m x n board have a Hamiltonian cycle?

Notes: A bishop moves along diagonals of a chessboard. A white bishop can only move to white squares. The problem is asking for a Hamiltonian cycle in the (white) bishop's graph B(m, n) for an m x n board. Peter Saltzman and I have characterized the cases where B(m, n) is Hamiltonian.

Open question: Are the bishop's graphs Hamilton-connected, meaning: Is it possible to get from any square to any other via a Hamiltonian path? We suspect B(m, n) is Hamilton-connected except in some easily handled negative cases: m <= 3 and B(4, 4).

Source: Joint work in summer 2012 by Peter Saltzman and Stan Wagon. It appears that the problem had been considered before but not in the pure graph sense; that is, a move from A to B over C was considered as having visited C. We are interested here in the purer problem about certain graphs being Hamiltonian.