9
$\begingroup$

Suppose you have a checkerboard with two opposite corner squares removed, like this:

mutilated chessboard

Can you move a pawn on the board only horizontally and vertically, one square at a time, and have it touch every square exactly once?

$\endgroup$
5
  • 1
    $\begingroup$ Hamiltonian path problem $\endgroup$ May 16, 2014 at 20:15
  • 3
    $\begingroup$ Pedantic: Your chessboard is sideways :) $\endgroup$ May 16, 2014 at 21:03
  • 3
    $\begingroup$ White on the right, I know, but it doesn't matter for this question. $\endgroup$
    – user88
    May 16, 2014 at 21:04
  • $\begingroup$ Follow up: Can you place 31 2x1 dominos so as to cover all of these squares exactly once? $\endgroup$
    – John Bupit
    May 19, 2014 at 14:38
  • 2
    $\begingroup$ The domino problem is the most common formulation of this problem. I wanted to post one that was different but followed the same principle. $\endgroup$
    – user88
    May 19, 2014 at 14:48

1 Answer 1

22
$\begingroup$

No.

Every move the pawn makes it switches from a white to a black square or vice versa. Therefore it must either touch an equal number of white and black squares with an even number of moves, or one more square of either color with an odd number of moves. (A move including initially placing it on the board.)

Because there are two more white squares than black squares (32 and 30) there is no way it can touch each square exactly once.

The same argument applies to show that the Knight's Tour cannot be completed on this board either.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.