18
$\begingroup$

Place numbers 1 to 100 in the cells of this 10 x 10 board in such a way that consecutive numbers, and also numbers 1 and 100, occupy neighboring cells (either vertically or horizontally). Prime numbers should occupy grey cells, while square numbers should go on green cells.

enter image description here

$\endgroup$
1
  • $\begingroup$ Has a correct answer been given? If so, please don't forget to $\color{green}{\checkmark \small\text{Accept}}$ it :) $\endgroup$
    – Rubio
    Feb 11, 2020 at 1:15

2 Answers 2

15
$\begingroup$

First it is easy to see that

2 is the only even prime, so can be instantly identified.
Adjacent to this, 1 and 100 are both square numbers, joining on the adjacent consecutive green squares. 99, 3 and 4 can also be immediately placed as the only legal adjacent squares. enter image description here

From here, there is only one "odd" square that

is within reach from '4' on which to place the '9', and although I found the correct route first,

as stated by @daw in comments,

another route for 5-9 exists that cannot be trivially eliminated:
enter image description here

It looks to me like this

leads to a contradiction - we can get to a suitable green square for 16 in 2 different ways, but both leave a section "cut off" which we can't revisit on the tour.
enter image description here
If, instead, we fill the gap below 9, we can't reach a 16.
enter image description here

The only remaining way to

fit 5-8 that will allow the rest of the snake to fit [and the only one I saw at first] is:
enter image description here

Continuing, we could turn left or right, but

left soon gets us stuck with not enough green squares around (we'll need to find 16 then 25, etc.)
so we must turn right, which I immediately spotted opened up 2 possibilities for numbers 12-16: enter image description here

The upper route

soon leads to a dead-end however we approach it - we need to go back through the gap between 13,14 and the edge, but also need to hit prime squares for 17 and 19, and also be in range of a green square for 25. That's not possible going that way.

For the other route shown above,

the even green square next to 13 and 15 would require an even square that is adjacent to two primes, of which there are none (36 is adjacent to only one prime, and 64 is adjacent to none.

Thus, only one possibility remains for

the 16 (which I'd mistakenly failed to spot at first), from which the positions of 17-23 and 25 become immediately obvious:
enter image description here

Looking to the next square number,

there are two even green squares left, but only one is within range. 36 has a prime on only 1 side, so several more squares, and the position of 49 immediately follow.
enter image description here

Now turning our attention to the higher numbers

after filling in 24-32 in the obvious way, it is clear that counting down from 99 we must fill the gap to the left of 25-26 before going towards the square that is now obviously 81. 98 down to 81 fit in very simply:
enter image description here

as indeed do

the next set of numbers down to 63
enter image description here

from here, there are two different positions for

62.
Only one of them leads on to a valid solution:
enter image description here

... and as @avi noted in comments,

there is a second way to fit in the numbers 44-53
enter image description here

$\endgroup$
5
  • 1
    $\begingroup$ there is another way to fill 5-8: place 5 to the right of 4 $\endgroup$
    – daw
    Jan 30, 2020 at 14:48
  • $\begingroup$ @daw next edit was going to comment how I must have made a mistake, but thanks for the pointer to where it was! $\endgroup$
    – Steve
    Jan 30, 2020 at 14:50
  • 1
    $\begingroup$ I really appreciate you taking the time to logically break this down - keep going, please :) $\endgroup$
    – Avi
    Jan 30, 2020 at 15:20
  • $\begingroup$ After reaching 49, you can identify both 64 and 81. $\endgroup$
    – trolley813
    Jan 30, 2020 at 15:35
  • 1
    $\begingroup$ There do appear to be at least two valid solutions (spoilers, beware) $\endgroup$
    – Avi
    Jan 30, 2020 at 15:36
6
$\begingroup$

Following on from a Python program posted on the first question of this type, I made some minor modifications - it turns out that the squares identified by @Steve are sufficient to guarantee a solution that fits the criteria of the problem, without explicitly taking squared-number criteria into account. Here is the solution:

Here is the program I used:

"""
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,1), (0,3), (0,7), 
                    (1,4), (1,6),
                    (2,1), (2,9),
                    (3,0), (3,4), (3,6), (3,8),
                    (4,3), (4,5), 
                    (5,2), (5,4), (5,6), (5,8), 
                    (6,1), (6,4),
                    (7,6), (7,8),
                    (8,1), (8,3), (8, 9),
                    (9,4)
                  ]
FIXED_SQUARES = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,100,99]
FIXED_POSITIONS = [
  (3,2), (3,3), (3,4), (3,5), (3,6), (3,7),
  (4,2), (4,3), (4,4), (4,7),
  (5,2), (5,3), (5,4),
  (6,2), (6,3), (6,4),
  (7,2)
]
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,
                'already_known'   : (i,j) in FIXED_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 " "
            prime = "X" if board[(i,j)]["already_known"] else prime
            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 (number in FIXED_SQUARES) != board[(i,j)]["already_known"]:
        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()

Edit: Upon modification to actually take square numbers into account, here are some solutions output (which only turn out to have 2 unique solutions):

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

Here is the code modified to take square numbers into account and print multiple solutions if they exist:

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,1), (0,3), (0,7), 
                    (1,4), (1,6),
                    (2,1), (2,9),
                    (3,0), (3,4), (3,6), (3,8),
                    (4,3), (4,5), 
                    (5,2), (5,4), (5,6), (5,8), 
                    (6,1), (6,4),
                    (7,6), (7,8),
                    (8,1), (8,3), (8, 9),
                    (9,4)
                  ]
SQUARES_BELOW_N2 = [x*x for x in range(1, N+1)]
SQUARE_POSITIONS = [
  (1,8),
  (2,2),
  (3,2),
  (4,4), (4,6),
  (5,7),
  (6,2), (6,3),
  (7,0),
  (8,7)
]
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,
                'should_be_square'   : (i,j) in SQUARE_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 " "
            prime = "^" if board[(i,j)]["should_be_square"] else prime
            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()

    # 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 (number in SQUARES_BELOW_N2) != board[(i,j)]["should_be_square"]:
        return False

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

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

    if number == 100:
        # Success! Print data and undo the move early
        print("Hurray")
        print(tries, number)
        print_board()
        board[(i,j)]["occupies"] = 0
        return False

    # ..., 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()
$\endgroup$
6
  • $\begingroup$ Neat code like this never ceases to soothe me. $\endgroup$
    – Ébe Isaac
    Jan 30, 2020 at 15:26
  • $\begingroup$ For a moment, I thought "how did I miss so many solutions?".... then I looked more closely to find out what the differences between them were... $\endgroup$
    – Steve
    Jan 30, 2020 at 16:05
  • $\begingroup$ @Steve I too am amazed by the lack of variety :P $\endgroup$
    – Avi
    Jan 30, 2020 at 16:06
  • $\begingroup$ Oh, I see... you print out each solution for each of the 4 places that it wants to try placing '101' next to '100' $\endgroup$
    – Steve
    Jan 30, 2020 at 16:09
  • $\begingroup$ I confirmed via integer linear programming that there are exactly two solutions, even if you do not require 1 and 100 to be adjacent. $\endgroup$
    – RobPratt
    Jan 30, 2020 at 16:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.