# Prime Number Snake

Place numbers 1 to 100 in the cells of the 10 x 10 board below in such a way that consecutive numbers occupy neighboring cells (either horizontally or vertically). Shaded cells should contain only prime numbers.

• Do the borders follow the rule of snake borders? Eg, can (1,10) be a neighbour of (4,10)? Jan 24 '20 at 5:00
• Unintuitively, it is very easy to work out where the 1 must go. I’ll try to post a full solution soon. Jan 24 '20 at 8:43
• Bernardo: this is a fun puzzle that I bet would be enjoyed by the readers of MAA Focus (here's evidence of puzzles in that publication). You might consider submitting it to them! Jan 25 '20 at 19:56
• For another puzzle of the kind (but with unique solution) go to puzzling.stackexchange.com/questions. Jan 27 '20 at 1:31
• @GregMartin theguardian.com/science/2021/oct/18/… Oct 19 '21 at 13:19

First, we want to take a look at the snake itself.

These are the number of non-primes (white squares) between consecutive primes

0 1    1 3 1 3 1 3    5 1    5 3 1 3    5 5 1    5 3 1   5 3   5 7 3
There are 25 dark squares on the grid, and there are 25 primes smaller than 100, so there are no sneaky primes in the white squares, even though the wording of the puzzle might otherwise allow such things.

(The extra spacing is there to make the colour pattern easier to remember. I used this, since I couldn't be bothered to build an actual snake. This turned out to be a mistake: the puzzle is VERY tricky to solve while having to remember the snake's exact colouring without a real world example, or at least a picture of the snake handy.)

Then, let's take a look at the grid, and see if there are some obvious features.

Since consecutive squares always have opposing parity, the head of the snake is easy to find: 2 is the only even prime. We also get the 1 for free.
The bottom right corner is also fixed, since it's only reachable if we have at least 4 non-primes at the end of the snake (we don't) or if there's a run of 7 white squares at some point. (There's one such run.)

So, let's fill those in:

Then, because the snake has more white near the tail end, I thought it would be a good idea to go from the 93 to the top side as soon as possible; the grid seems to have more white along the right and top sides.

Then, it was just a matter of fitting the rest of the snake in. This was very taxing to do without a real-world snake. There are many heuristics (never leave dead ends or walled-off areas) and mnemonics (there can never be a "dark-white-dark-white-dark" pattern), but in the end it all came down to just cramming the snake in there, and wiggling until it fit.

Here's the final snake (with only the primes explicitly written out to minimise visual clutter):

EDIT:

It turns out the solution isn't unique, there are a couple of possible variations at least:

• The sequence from 6 to 18 can be reversed, and independently from that,
• The sequence from 86 to 100 can be reversed.
• also 8-22 can be reversed
– daw
Jan 26 '20 at 16:47

Partial answer, to be used as a springboard

Parity

The first thing to notice is that

the odd numbers and the even numbers must form a checkerboard pattern: fifty odd numbers on the "white" squares and fifty even numbers on the "black" squares.

Then, of course,

all but one of the shaded primes are odd. That means we can immediately place 1 and 2 in the grid.

We notice also that

the top left and bottom right corners are odd while the top right and bottom left corners are even.

Prime gaps

The primes between 1 and 100 are:

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

With gaps:

1 2 2 4 2 4 2 4 6 2 6 4 2 4 6 6 2 6 4 2 6 4 6 8

Now look at

the bottom right corner of the grid. This is an odd number, but the closest prime to it on either side is at least four steps away. So this must be the middle of the (only) gap of size eight, namely 93.

Similarly,

the cell second from the right, fourth from the top (marked with * below) is an even number with the closest prime on either side being at least three steps away. So this must be the middle of a gap of size six, namely one of 26, 34, 50, 56, 64, 76, 86.

So far we have:

I'm guessing further deductions can be made along the same lines, thinking about parity and prime gaps to narrow down the possibilities. But I'm not sure exactly what the next step should be.

• I'm not sure the position 93 is necessarily correct. Jan 24 '20 at 10:19
• The star has one more option. :-)
– Bass
Jan 24 '20 at 10:59

I could not think of a way to solve this riddle by hand (besides the observations already made by Rand al'Thor.

So, I wrote a small program to solve this riddle. The key to get acceptable run-time was to implement some flood-fill algorithm to check that the current chain does not split the board in two disconnected region. This is easy to spot for humans, but not for computers.

Here is the solution:

    57    58  [ 67]   68    69    76    77    80    81    82
56  [ 59]   66    65    70    75    78  [ 79]   84  [ 83]
55    60  [ 61]   64  [ 71]   74  [ 31]   32    85    86
54  [ 53]   62    63    72  [ 73]   30    33   100    87
51    52    15    14  [ 13]   12  [ 29]   34    99    88
50  [ 17]   16     1  [  2] [ 11]   28    35    98  [ 89]
49    18  [  5]    4  [  3]   10    27    36  [ 97]   90
48  [ 19]    6  [  7]    8     9    26  [ 37]   96    91
[ 47]   20    21    22  [ 23]   24    25    38    95    92
46    45    44  [ 43]   42  [ 41]   40    39    94    93


In total 8 solutions were found. The numbers 86-100 can be reversed in all of them reducing the total to 4. Two of these are obtained by reversing 8-16 and 8-22 of the solution above. Here is a fourth type, I do not see how this can be obtained from the first:

    57    58  [ 67]   68    69    76    77    80    81    82
56  [ 59]   66    65    70    75    78  [ 79]   84  [ 83]
55    60  [ 61]   64  [ 71]   74  [ 29]   28    85   100
54  [ 53]   62    63    72  [ 73]   30    27    86    99
51    52    45    44  [ 43]   42  [ 31]   26    87    98
50  [ 47]   46     1  [  2] [ 41]   32    25    88  [ 97]
49    48  [  5]    4  [  3]   40    33    24  [ 89]   96
12  [ 11]    6  [  7]   38    39    34  [ 23]   90    95
[ 13]   10     9     8  [ 37]   36    35    22    91    94
14    15    16  [ 17]   18  [ 19]   20    21    92    93


And here is a grid of all numbers that are the same in all solutions.

    57    58  [ 67]   68    69    76    77    80    81    82
56  [ 59]   66    65    70    75    78  [ 79]   84  [ 83]
55    60  [ 61]   64  [ 71]   74  [...]  ...    85   ...
54  [ 53]   62    63    72  [ 73]   30   ...   ...   ...
51    52   ...   ...  [...]  ...  [...]  ...   ...   ...
50  [...]  ...     1  [  2] [...]  ...   ...   ...  [...]
49   ...  [  5]    4  [  3]  ...   ...   ...  [...]  ...
...  [...]  ...  [...]  ...   ...   ...  [...]  ...   ...
[...]  ...   ...   ...  [...]  ...   ...   ...   ...   ...
...   ...   ...  [...]  ...  [...]  ...   ...   ...    93


• Amazing! I was doing almost the same thing, only with a combination of DFS and backtracking, it takes a whole lot of time for my algorithm to work too. If you could post your code as well, it would also be of a resourceful reference indeed. Jan 24 '20 at 13:26
• There may be a mistake in your code - the solution does NOT seem to be unique - the entire section from 86 to 100 can be reversed for a second solution. Jan 24 '20 at 13:29
• @Steve yup, same thing with 6-18.
– Bass
Jan 24 '20 at 18:05
• @ÉbeIsaac the code is a mess :/
– daw
Jan 26 '20 at 16:12
• @Steve that's correct. Another answer was posted as well, which differs also in the position of prime numbers. I will check my code :)
– daw
Jan 26 '20 at 16:13

Partial solution [started before a full solution was posted, so may decide to abandon if I don't get anywhere]

First, take a look at the empty grid and the snake that must fill it:

In the above, I'm using the convention that a thick line is a known border, no line (drawn as pale grey due to Excel) for cells that are connected, and a thin black line where connection is unknown.

There are two distinctive and unique features that are clearly visible, mentioned in the "springboard" from Rand al'Thor, which fix the positions of

1, 2, 93

odd non-primes (underlined below) must be on the underlined squares, and the cells marked with * can only contain one of the even numbers marked in bold (including 100, which is henceforth marked as 0 to avoid needing one-off special formatting). Remaining bold numbers must be in cells adjacent to at least 2 underlined cells.
1 and 100 are not in corners, so the corners must be connected to the two adjacent cells.

Marking these "clues" on the image (and highlighting in red the parts of the reference snake whose positions are known), I get an initial layout like this:

Next, observe that from each of the cells marked with *, the snake MUST take a minimum-distance path to one of the nearest grey cells, giving limits to how "twisty" it can be in those regions.

In particular the region in the bottom right seems to have a limited number of valid possibilities...

... or perhaps less limited than I first thought... manually working through what seemed like a limited set of possibilities led to the following possibilities for the bottom-right corner: ... originally intended as an exhaustive list, but I'm not 100% on that now.

I ran out of insights about how to deduce the (by now already-known) solution, and I was taking too long, so am now abandoning this answer.

Not sure whether etiquette suggests I should delete it completely, or leave in place in case someone else wants to complete an answer not involving guesswork or computer-based searches.

• Seeing how there are already two answers with the full solution, I'd say it's too late to post partials.
– Bass
Jan 24 '20 at 11:38
• @bass there weren't when I started writing, and looking at them, I see that neither really "show their working" - will see if I get anywhere with actual deduction rather than exhaustive computer search or informed guesswork and "wiggle it until it fits", and if not can abandon this. Jan 24 '20 at 12:10

I wrote a small Python program which found another solution:

     +----------------------------------------------------+
|  57   58   67*  68   69   76   77   80   81   82   |
|  56   59*  66   65   70   75   78   79*  84   83*  |
|  55   60   61*  64   71*  74   31*  32   85  100   |
|  54   53*  62   63   72   73*  30   33   86   99   |
|  51   52   15   16   17*  18   29*  34   87   98   |
|  50   13*  14    1    2*  19*  28   35   88   97*  |
|  49   12    5*   4    3*  20   27   36   89*  96   |
|  48   11*   6    7*  22   21   26   37*  90   95   |
|  47*  10    9    8   23*  24   25   38   91   94   |
|  46   45   44   43*  42   41*  40   39   92   93   |
+----------------------------------------------------+


Edit: Added as requested the code used. It is quite rough, slow and straight forward. The function enough_space_for_the_tail is a first improvement, there can be more made I think. Currently it stops at the first solution found, this can easily be changed by returning False after print("Hurray") but this will result in duplicate solutions.

"""
see: https://puzzling.stackexchange.com/questions/93030/prime-number-snake
"""

def primes_less_or_equal(n):
l = [True] * (n + 1)
for factor in range(2, n // 2):
for i in range(2 * factor, n+1, factor):
l[i] = False
retval = []
for i in range(2,n+1):
if l[i]:
retval.append(i)
return retval

# constants
N  = 10
N2 = N * N
PRIMES_BELOW_N2 = primes_less_or_equal(N2)
PRIME_POSITIONS = [ # values from problem definition
(0,2),
(1,1), (1,7), (1,9),
(2,2), (2,4), (2,6),
(3,1), (3,5),
(4,4), (4,6),
(5,1), (5,4), (5,5), (5,9),
(6,2), (6,4), (6,8),
(7,1), (7,3), (7,7),
(8,0), (8,4),
(9,3), (9,5)
]
SHOW_PROGRESS_TRIES = 100000 # ....,a lot

# globals
board = None
tries = 0

def on_board(i,j):
return i >= 0 and i < N and j >= 0 and j < N

def all_neighbours(i,j):
return [(i-1,j), (i+1,j), (i,j-1), (i,j+1)]

def valid_neighbours(i,j):
return [neigh for neigh in all_neighbours(i,j) if on_board(*neigh)]

def create_board():
board = {}
for i in range(10):
for j in range(10):
board[(i,j)] = {
'occupies'        : 0,  # 0 means not occupied (yet)
'should_be_prime' : (i,j) in PRIME_POSITIONS,
'neighbours'      : valid_neighbours(i,j)
}
return board

def print_board():
global board
print(" +----------------------------------------------------+")
for i in range(N):
print(" | ", end='')
for j in range(N):
prime = "*" if board[(i,j)]["should_be_prime"] else " "
number = board[(i,j)]["occupies"]
number = f"{number:3}" if number else "   "
print(f'{number}{prime} ', end='')
print(" | ")
print(" +----------------------------------------------------+")

def free_space_at(free,i,j):
if not (i,j) in free:
return 0
else:
free.remove((i,j))
return ( 1 + free_space_at(free, i-1,j  )
+ free_space_at(free, i+1,j  )
+ free_space_at(free, i  ,j-1)
+ free_space_at(free, i  ,j+1) )

def enough_space_for_the_tail(number, i, j):
global board
free = [key for key, item in board.items() if not item['occupies']]
n = free_space_at(free,i,j)
return (101 - number) <= n

def try_it(number, i, j):
global board, tries
tries += 1

# show some progress
if (tries % SHOW_PROGRESS_TRIES) == 0:
print(tries, number)
print_board()

if number == 101:
# Hurray, we are finished, return succes
print("Hurray")
print(tries, number)
print_board()
return True

# check if this is a valid move
if board[(i,j)]["occupies"]:
return False

if (number in PRIMES_BELOW_N2) != board[(i,j)]["should_be_prime"]:
return False

if not enough_space_for_the_tail(number, i, j):
return False

# let's make our move, ...
board[(i,j)]["occupies"] = number

# ..., and try the next steps, ...
for neigh in board[(i,j)]["neighbours"]:
next_i, next_j = neigh
if try_it(number + 1, next_i, next_j):
# Hurray, succes
return True

# Nope, this move did not work, undo and return failure
board[(i,j)]["occupies"] = 0
return False

def main():
global board
board = create_board()
for i in range(N):
for j in range(N):
try_it(1, i, j)

main()

• Great! I wonder how to amend original puzzle so that solution is unique. Jan 26 '20 at 13:54
• Small code? Sounds interesting! Could you share the code with your a answer? Jan 26 '20 at 16:14
• @Ébe Isaac, relativity small of course, added the code. Jan 26 '20 at 19:56
• Of course Python is the best language to search for snakes with. Jan 27 '20 at 0:08