A rook's tour of the chessboard

Question

Place numbers 1 to 64 in the cells of this 8 x 8 board in such a way that consecutive numbers, and also numbers 1 and 64, occupy neighboring cells (either vertically or horizontally). Shaded cells must be occupied by prime numbers.

Answer 1

I used integer linear programming, as follows. Let binary decision variable $x_{i,j,k}$ indicate whether cell $(i,j)$ contains value $k$. Let $N_{i,j}$ be the set of neighbors of cell $(i,j)$. The constraints are: \begin{align} \sum_{k=1}^{64} x_{i,j,k} &= 1\\ \sum_{i=1}^8 \sum_{j=1}^8 x_{i,j,k} &= 1\\ x_{i,j,k} &\le \sum_{(i',j')\in N_{i,j}} x_{i',j',k+1} \end{align} The first constraint forces one value per cell. The second constraint forces one cell per value. The third constraint enforces the logical implication: if cell $(i,j)$ contains value $k$, then some neighboring cell $(i',j')$ contains value $k+1$ (with $64+1$ treated as $1$). Finally, if cell $(i,j)$ is shaded, then $k$ must be prime, and you can enforce this either by fixing $x_{i,j,k}=0$ for non-prime $k$ or by omitting that $x_{i,j,k}$ from the formulation.

There are two solutions:

The first: 39 38 37 36 35 16 15 14 40 29 30 33 34 17 12 13 41 28 31 32 19 18 11 10 42 27 24 23 20 5 6 9 43 26 25 22 21 4 7 8 44 53 54 55 56 3 64 63 45 52 51 50 57 2 1 62 46 47 48 49 58 59 60 61
and 39 38 29 28 27 16 15 14 40 37 30 25 26 17 12 13 41 36 31 24 19 18 11 10 42 35 32 23 20 5 6 9 43 34 33 22 21 4 7 8 44 53 54 55 56 3 64 63 45 52 51 50 57 2 1 62 46 47 48 49 58 59 60 61

Nicer picture of the first one:

Answer 2

Human mind can brute force too :P

2 is obvious and 3 is easy. Then: List of prime distances from 3 onward: 2, 2, 4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, (5) - to get from 61 to 2.

Draw path in corners, then

Extend path in bottom right corner past the bottom of 2 to make line unbroken. Also, note that all the remaining black squares (= the ones not grey) are filled with odd numbers where distance between primes is 4, 5 or 6.

Let's assume

1 is left of 2. This means the bottom right number has a distance of 4 or 6, followed by 2, followed by 6, ending in the tile top-right of 3. (or, obviously, reversed). There is a single sequence matching that with distances 6,2,6 (numbers 23, 29, 31, 37). This sequence requires continuation taking 4 steps on both sides. This takes black square top-right of 3, while we can write 5 down. As both 4s have 2 as the next number, we cannot take top-right grey tile, taking the one directly top-right from 5 instead.

Because

the top-right grey tile can be reached by continuing the red line to it, or by a 2-6 sequence. There is no such sequence left except 53-59-61, but that one cannot reach starting 1. So, extend red line, and now we know this sequence needs another tile with distance 4. Now there is either another distance of 2 (current number is 13, going to 11), or 6 (current number is 47, going to 53).

Assume the first option

7 needs to be left of 5. 11 needs to be top-right. But then, squares on top row above 9 and 10 are unreachable.

Second option:

47 is on that tile. Continue path to take the remaining 2 black squares, leaving obvious continuation from 5 to 7 to 11. This gives position of 64 on top of 1, fixing 61 to the left of it. 29 is below 2, 23 has to be left of it, giving 19 as the position on top-left of 61. There is no place for 59 left.

Therefore, after a lot of work

1 has to be RIGHT of number 2. This immediately gives 64 above, 63 right of it, then 62...59 and 58. Because 5 needs just 2 steps to 7, it has to be above 4. Now, which number can be right of 4? It could be easily 7, but can there be anything else? It is easy to see that the number chain would have to pick number top-right of 5 too, then either top-left or 2 squares above 5. But there is no sequence with 2x 2 distances in a row beyond 3-5-7. So, that number is 7.

What now?

13 cannot be top-left of 11 because it would be impossible to fill the top right corner. It cannot be top-left of 5 either. There are 3 dark squares left in the place above 13, meaning to get the corner, a sequence of 4-2-6 is requires, and this doesn't exist. Therefore, 13 is top-right of 11. Continuation to 19 is straightforward.

Let's write the remaining distances:

4, 6, 2, 6, 4, 2, 4, 6, 6. As there are just 2+1 black squares above 19, continuation above is not possible - it would be impossible to place 29. Therefore, 23 needs to be bottom-left of 19. There is no distance greater than 6, so we can pick at most 2 black squares between 2 grey ones. Therefore, it is not possible to have line coming to the square left of 2 from anywhere but 58. This gives position of 53 and continuity of the line also gives 47 and 43. 41 is trivial again.

Not far now:

Just numbers 29, 31, 37 are left to place with distances to the current ones of 6, 2, 6, 4. It is evident corner has that distance of 4, so 39 is in the top left corner of the board.

For the final two solutions:

From 23, we can continue either by picking 2 black squares on left or top of it. Picking squares on top of it gives 29 on the top grey square. 31 has to be below it to continue line, then 37 goes on the remaining grey square. Alternatively, picking squares on left puts 29 on top-right of 41 (top-left of 23 would make it impossible to place 31 and continue line). Fill in the remaining bits, and the chessboard is full of numbers.

I just wish there was a more obvious way of seeing impossibility of the first option that took a lot of time to analyze. It seems impossible from almost the start, but I had to nearly fill the board to show it really doesn't lead to any solution. Solutions are marked in blue and red. Sorry for the lack of clarity. I would have added progress, but that is even more of a mess.

Answer 3

I think there are two more solutions than Rob suggests, though the differences are quite slight. One is:

39, 38, 37, 36, 35, 16, 15, 14 
40, 29, 30, 33, 34, 17, 12, 13 
41, 28, 31, 32, 19, 18, 11, 10 
42, 27, 24, 23, 20,  7,  8,  9 
43, 26, 25, 22, 21,  6,  5, 64 
44, 53, 54, 55, 56,  3,  4, 63 
45, 52, 51, 50, 57,  2,  1, 62 
46, 47, 48, 49, 58, 59, 60, 61 

And the other is a similar adjustment to the difference between Rob's 2. I'm afraid I did this by brute force on Python having tried and failed to find an elegant method.