2836085845172927 2422106047213123 4038426243194139 0204060049050301 5153555750565452 1315116348161412 3335096146203234 2537075944183026Moreover, I will prove that the maximal length for a rook tour in a (2k)*(2k) board, for any k, is 16/3 k3-10/3 k+2.
A further generalization of this, which can be attained by the same means as the present proof and only minor additional complications (left for the reader to tackle), gives the solution for a general n*m board. In the general case, the solution is n(3m2+n2-10)/6+C, where we assume without loss of generality that m≥n. Here, C is given by the following table.
| C | n%4 | ||||
| 0 | 1 | 2 | 3 | ||
| m%2 | 0 | 2 | 3/2 | 2 | 1/2 | 1 | 0 | 1 | 1 | 1 |
Credit: the proof I originally prepared for this riddle is essentially identical to the one sent in by Lorenz Reichel, but at various points I found Lorenz's wording to be superior to my own. I have therefore borrowed liberally from his phrasing. Thanks, Lorenz!
Proof: Consider two lines, one horizontal and one vertical, dissecting the (2k)*(2k) board into four quadrants of size k*k each. Denote the lines h and v, respectively. For each square, S, of the (2k)*(2k) squares of the board, denote by H(S) its distance to h and by V(S) its distance to v. Furthermore, define M(S)=max{H(S),V(S)}, m(S)=min{H(S),V(S)} and δ(S)=M(S)-m(S).
Consider, now, a rook move from any square S1 to any square S2. We'll assume, without loss of generality, that S1 is in the top right quadrant.
If the rook moves in the direction up from S1, the length of the move is V(S2)-V(S1). This length can be split to two separate contributions, one dependent only on S1 and the other dependent only on S2. In this case, the S1 contribution is -V(S1), and the S2 contribution is V(S2). Similarly, if the move was to the right, the contribution of S1 would have been -H(S1) and the S2 contribution would have been H(S2).
Consider now the case of the rook moving in the direction down. The contribution of S1 in this case is V(S1) and the contribution of S2 is either plus or minus V(S2), depending only on the quadrant in which S2 resides. The case of the rook moving to the left is similar.
We see, therefore, that the contribution of S1 is one of {V(S1), H(S1), -V(S1), -H(S1)} and can be determined entirely by the direction of the rook's motion, regardless of the identity of S2.
If the rook moves in the best possible direction both to and from S1, the length contribution of S1 will be M(S1) for each of these two moves, for a total of 2M(S1). If even one of these moves is in any other direction, the minimal cost to the total length that this will incur is δ(S1).
We therefore get an initial bound to the total rook tour length, simply by summing 2M(S) over all squares S. The bound that we get (336 for the 8*8 board) is the maximal length for the covering of the chessboard by multiple cycles. For example, this bound can be reached if from any point the rook travels towards the line, h or v, farthest away from it, until it reaches the point that is its own mirror image, using the line crossed as a reflection line. (These being cycles of length 2.) For squares that are equidistant from both reflection lines, one can choose, arbitrarily, to favor a horizontal path.
There are many other ways as well, in which one can attain the first upper bound. However, it is not possible to attain this bound in less than k cycles for a (2k)*(2k) board. To see this, consider the partitioning of the chessboard shown below (which can be extended trivially to any size).
| 4 | 3 | 2 | 1 | 1 | 2 | 3 | 4 |
| 3 | 3 | 2 | 1 | 1 | 2 | 3 | 3 |
| 2 | 2 | 2 | 1 | 1 | 2 | 2 | 2 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 2 | 2 | 1 | 1 | 2 | 2 | 2 |
| 3 | 3 | 2 | 1 | 1 | 2 | 3 | 3 |
| 4 | 3 | 2 | 1 | 1 | 2 | 3 | 4 |
In order to reduce to a single cycle, some of the squares must not have optimal directions. They must reduce the total path length by at least δ(S). The diagram below shows δ(S) for all squares of the board.
| 0 | 1 | 2 | 3 | 3 | 2 | 1 | 0 |
| 1 | 0 | 1 | 2 | 2 | 1 | 0 | 1 |
| 2 | 1 | 0 | 1 | 1 | 0 | 1 | 2 |
| 3 | 2 | 1 | 0 | 0 | 1 | 2 | 3 |
| 3 | 2 | 1 | 0 | 0 | 1 | 2 | 3 |
| 2 | 1 | 0 | 1 | 1 | 0 | 1 | 2 |
| 1 | 0 | 1 | 2 | 2 | 1 | 0 | 1 |
| 0 | 1 | 2 | 3 | 3 | 2 | 1 | 0 |
This indicates that connecting partition 1 to partition k must suffer at least a loss of k-1 to the total path length. Furthermore, because the desired path is a cycle, partition 1 must be connected to partition k by two disjoint paths. Therefore, this penalty must be suffered twice, for a total loss of 2k-2. This brings us to our final result. In the case of the 8*8 chessboard, the reduction is from 336 to 330, which is the maximum path length.
Next, let us show that this maximum can actually be attained in the general case. It is, of course, possible to use the proof of the upper bound as the basis for a construction. We will build the construction differently here. Specifically, we will use induction from a board of size (2k)*(2k) to a board of size (2k+2)*(2k+2). We do this by placing the original construction at the (2k)*(2k) central squares of a (2k+2)*(2k+2) board. We now extend the cycle to include the new squares.
The induction will start with the single possible (up to direction) Hamiltonian rook cycle on the 2*2 chessboard. This rook tour satisfies two criteria which we will require and ensure for all next iterations of the induction. The criteria are as follows:
We exploit the first of the two criteria listed above by the following mechanism. Let us take any move. For example, suppose the move is from (x,y1) to (x,y2), where y1<y2. (This example considers a move in the direction "down", but is otherwise generic. The same procedure, mutatis mutandis, can be applied to moves in all other directions as well.) We now replace the original move by the move sequence from (x,y1) to (x,2k+1) to (x,0) to (x,y2). The new path differs from the original path by covering two additional points in the cycle, and by lengthening the total tour by 4k+2, regardless of the distance between the two original points. We pick one segment in each row and each column in order to transpose in this way. We are guaranteed that such exists by the first criterion.
At the end of this first sequence of transpositions, the entire new square is covered, except for its four corners. We exploit the second criterion for the corners. Without loss of generality, let us assume that there is a move from (1,1) to (1,2k) and a move from (1,2k) to (2k,2k). Now, instead of performing on these moves (or any other move on their row/column) the transposition described above, we transform them to a move sequence from (1,1) to (1,2k+1) to (1,0) to (2k+1,0) to (2k+1,2k+1) to (0,2k+1) to (0,0) to (0,2k) to (2k+1,2k) to (1,2k) to (2k,2k).
Counting the total length of the cycle defined in this manner shows that it is, indeed, maximal.
The Python program here implements the algorithm. Use "print_rooks(n)" to get the solution for an n-by-n board. (For clarity, spaces were added between the cells, rather than relying on a fixed-width format. Larger n values will require more digits to represent the solution.)
This is the program that generated the solution above.
Now, for some credits for this riddle.
The riddle was first brought to my attention by Yaron Gvili. His question was identical to the one ultimately asked, except that he was interested in open Hamiltonian rook paths, rather than in closed Hamiltonian cycles. I chose to ask about cycles, because they seem to have the more interesting theory behind them.
In researching this issue, I found that the definitive source for this riddle, cited by everyone (c.f. here) is Martin Gardner's book "Knotted Doughnuts and Other Mathematical Entertainments". This book gives the formula I quote above for the general case. (I haven't checked all m*n variations on it; you're most welcomed to verify these yourself. There's always a chance that what everyone quotes is a mistake.)
Gardner's book provides the formula, but no proof. It credits unpublished work by "Frederick Hartmann, of Rolling Hills Estate, California" for the general m*n case. The case of a square board, Gardner says, was tackled by Edward N. Peters in a piece called "Rooks Roaming Round Regular Rectangles", published in the Journal of Recreational Mathematics (Vol. 6, No. 3, Summer, 1973, pp. 169-173).
It was not easy to track down this 1973 publication, but I ultimately managed to get my hands on a copy. (My thank-yous go to Graham Farr for assisting me in this hunt.) Peters makes a series of (correct, I believe) claims regarding the rook tour, and constructs a valid Hamiltonian cycle, but I don't see his claims as having any adjoining proofs (or as being self-evident), so, despite the author's claims, I think this 1973 paper does not, in fact, prove maximality. If that is the case, then this Using your Head is Permitted solution is the first published proof of maximality for the rook tour. (There's still room to write a follow-up paper: "Rigorous Results Regarding Rooks Roaming Rectangles"!)
If any reader is aware of an earlier published proof of maximality for the maximal-length rook tour, I will be most interested in learning about it. Please let me know!