Suppose a chess piece can move only one square horizontally
or vertically at a time, i.e. a
king that cannot move diagonally.
Suppose that on a standard chessboard two squares at opposite
ends of the same diagonal are deleted. The first puzzle was to
determine if it possible for the king to visit
every square and
return to his starting point. The answer is no, but the
difficult part is giving a convincing argument
that explains why
no path, no matter how convoluted, will work. The statement "I
couldn't find one" is certainly not enough.
One way to see that
no path will work is to observe two important facts. The first
is that the "king" always moves
from a square of one color to a
square of another color since it only moves horizontally and
vertically. Thus
the colors (black and white) must alternate in
any path that the king takes. If the king could cover
every
square once and return to the starting point this alternation
would mean that the
board would have the same number of black and
white squares. The second
observation is that the two deleted
squares at opposite corners
must be of the same color, either
both black or both
white. Since the board originally had 32
black
and 32 white squares the deleted board will have
an
imbalance of two squares, 30 black and 32 white
for example.
Hence no path is possible.
The above solution
should give ideas that are useful in
solving the following variations.
Suppose that the board is m
squares by n squares with no deleted corners.
For what values of
m and n is it possible for the "king" to visit every square and
return to his starting point? Suppose two corners diagonally
opposite are deleted from
an m by n board. For what m and n is
it possible now? In each case you should provide the
values of m
and n for which it is not possible (with an explanation as to
why) and the values of m
and n for which it is possible (with
some general diagram that shows how the path is constructed).