Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. It only takes a minute to sign up.
Sign up to join this community
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.
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.
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:
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.
If, instead, we fill the gap below 9, we can't reach a 16.
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:
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:
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:
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.
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:
as indeed do
the next set of numbers down to 63
from here, there are two different positions for
62.
Only one of them leads on to a valid solution:
... and as @avi noted in comments,
there is a second way to fit in the numbers 44-53
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()
