- 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.)
- 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.)
- 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?
- 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.)
- Repeat problem 4, with the added restriction that the two pieces be identical (through rotation.)

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