Place numbers 1 to 64 in the cells of this 8 x 8 board in such a way that consecutive numbers occupy neighboring cells (either vertically or horizontally). Shaded cells must be occupied by prime numbers.
$\begingroup$
$\endgroup$
asked Sep 24, 2021 at 13:05
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
7
Here's the solution I got.....
answered Sep 24, 2021 at 18:21
-
$\begingroup$ Interesting. So it seems there are many different solutions $\endgroup$ Sep 24, 2021 at 19:28
-
1$\begingroup$ @DrXorile I wrote a program to check, there appear to be 4 solutions: pastebin.com/UeDRbX5J $\endgroup$ Sep 24, 2021 at 20:14
-
-
$\begingroup$ I think there are 4 solutions with a Hamiltonian path and only one solution with a proper tour (where values 1 and 64 are neighbors). $\endgroup$ Sep 29, 2021 at 5:47
-
1$\begingroup$ @BernardoRecamánSantos See yetanothermathprogrammingconsultant.blogspot.com/2021/09/… for a detailed discussion how I arrived at this conclusion. $\endgroup$ Oct 1, 2021 at 22:44
$\begingroup$
$\endgroup$
The start has to be:
There's only a handful of primes that are separated by 2. And, apart from 3-5-7, there's no 3 odd numbers in a row that are prime (well-known result, but easily verified up to 64). So that shows us this:
Note the corners have to be connected to the two squares on either side. This means the top-left and bottom-right corners can't be looping back onto the shaded areas (that would be two primes separated by 1). And the bottom left is one of the 5 composites in a row. The lack of 2 primes in a row add a few more restrictions to the path, which I've shown as a red line (i.e. the path can't go through the red lines).
Next I took an intuition that the bottom left must surround the 47-53-59 sequence (with 53 on the isolated shaded spot). I tried a few ways to get the end sequence (which needs 59-61-and the final tail of 3 composites), and eventually hit on using up the space on the right (I almost discarded it because it's not unique). But doing this and the rest fell in place:
answered Sep 24, 2021 at 17:55