Prime Number Snake

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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 
 

Answer 4

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

In addition, we know that

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.

Answer 5

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()