Some Chessboard Problems

  1. What is the smallest number of moves needed by a chess rook to visit every square on a chessboard?  (A rook can only move horizontally.  A "move" can be any length in a single direction.)
  2. What is the smallest number of moves needed by a chess queen to visit every square on a chessboard? (A queen can move both horizontally and diagonally.)
  3. A chess bishop can only move diagonally.  What is the maximum number of squares a chess bishop can visit, if it is only allowed to visit each square once?
  4. Cut a chessboard into two pieces along the grid lines, then rearrange the two pieces (with rotation possibly, but not reflection) to try to achieve the largest number of same-color neighboring squares.  (For example, if you cut off one column, and rotate it, then there will be eight pairs of adjacent squares of the same color.)
  5. Repeat problem 4, with the added restriction that the two pieces be identical (through rotation.)
Source: Original.
Solutions were received from Joseph DeVincentis, Jeremy Galvagni and Alan O'Donnell.

Joseph's solutions.  He interpreted the cutting problem differently than I'd intended, creating continuously connected sets of squares - an interesting solution:

You have some problems with the directions (horizontally, diagonally) in the
first two parts.

1. I'm guessing that you mean by "visit" that squares passed over in a move
are also visited. Otherwise it clearly takes 64 moves to visit all the
squares, regardless of how far the rook moves between squares, and the tour
can be completed trivially.

Vith this interpretation of "visit", it takes 15 moves for a rook to visit
every square. To see this, consider that in order for the rook to visit
every square in a row or column, it must either travel along some part of
the length of that row or column once, or else cross perpendicular to it 8
times in different positions. To do the latter requires 15 moves, 8
crossings and 7 other moves between the crossings to get the rook into a new
position for each subsequent move. To avoid having to do this 15-move
solution, you have to have a move along every row and every column, or thus
at least 16 moves. A 15 move solution can be done in a very simple way,
crossing each column from end to end and moving one step horizontally
between columns.

2. Upon thinking about this a bit more, I realized that this is essentially
equivalent to the second problem on this page:
http://www.mathpuzzle.com/dots.html
In that problem, you have more freedom to go in directions other than
those that a queen moves (though only exact hits on the centers of
squares would get counted) AND you have the freedom to go outside the
edges of the board. But still, you can only ever save one line relative
to the boring rook solution, or at least, that is all anybody managed to
find after a lot of work on the problem.

So the answer is 14 moves, and an example that fits our queen problem:
http://www.mathpuzzle.com/conn8x8.GIF



3. With the same interpretation of "visit" as above, the answer seems to be
29. It's possible to do this in four zig-zag crossings across the board, but
at each turning you miss a square on the edge. other patterns Only seem to
move the three missed squares around.

01    03    05    07
   02    04    06    08
XX    13    11    09
   14    12    10    XX
15    17    19    21
   16    18    20    22
29    27    25    23
   28    26    24    XX

If you don't count the passed-over squares, then a complete tour is
possible.

32    06    23    25
   05    22    24    26
04    21    07    13
   20    02    12    14
19    03    31    15
   28    11    16    08
29    27    17    09
   30    18    10    01


4. Use this cutting pattern:

oooooooo
XXXXXXXo
Xooooooo
XXXXXXXo
Xooooooo
XXXXXXXo
Xooooooo
XXXXXXXX

When you move the pieces apart by one space, gives this pattern of black and
white squares:

 WBWBWBWB
BWBWBWB W
W BWBWBWB
BWBWBWB W
W BWBWBWB
BWBWBWB W
W BWBWBWB
BWBWBWBW

Two pairs of adjacent white squares, and five sets of 8 same-color squares.

But if you want a single large group, you can do better. Cut this way:

oooooooo
oXoXoXoX
oXXXXXoX
oXoXXooX
oXooXXoX
oXoXXXXX
oXoXoXoX
oooooooo

When you rotate the piece, it gives this pattern of black and white squares:

WBWBWBWB
B B B B 
W     W 
B B  WB 
W WB  W 
B B     
W W W W 
BWBWBWBW

 B B B B
 WBWBW W
 B BW  B
 W  BW W
 B BWBWB
 W W W W

WBWBWBWB
BBBBBBBB
WWBWBWWW
BBBBWWBB
WWWBBWWW
BBBBWBWB
WWWWWWWW
BWBWBWBW

24 connected black squares, and 22 connected white squares. I'm not sure
this is the best possible.

5. With both pieces identical:

Xooooooo
XXXXXXXo
XoXoXoXo
Xooooooo
XXXXXXXo
XoXoXoXo
Xooooooo
XXXXXXXo

Shift the pieces vertically by 3 positions, to give this pattern of black
and white squares:

 BWBWBWB
       W
 B B B B
WWBWBWBW
BWBWBWBB
WWWWWWWW
BBWBWBWB
WBWBWBWW
B B B B
W
BWBWBWB

22 connected white squares.

Joseph DeVincentis

Jeremy's cutting solutions: Each has 48 pairs:
11111111
12121212
12121212
12122222
12222212
12121212
12121212
11111111 rotate 180

11111111
12212121
11212221
12222111
11122221
12221211
12121221
11111111 rotate 90

Mail to Ken