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.
2 Answers
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
from here, there are two different positions for
... and as @avi noted in comments,
-
1$\begingroup$ there is another way to fill 5-8: place 5 to the right of 4 $\endgroup$– dawJan 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$– SteveJan 30, 2020 at 14:50
-
1$\begingroup$ I really appreciate you taking the time to logically break this down - keep going, please :) $\endgroup$– AviJan 30, 2020 at 15:20
-
$\begingroup$ After reaching 49, you can identify both 64 and 81. $\endgroup$ Jan 30, 2020 at 15:35
-
1$\begingroup$ There do appear to be at least two valid solutions (spoilers, beware) $\endgroup$– AviJan 30, 2020 at 15:36
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()
-
$\begingroup$ Neat code like this never ceases to soothe me. $\endgroup$ 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$– SteveJan 30, 2020 at 16:05
-
$\begingroup$ @Steve I too am amazed by the lack of variety :P $\endgroup$– AviJan 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$– SteveJan 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$– RobPrattJan 30, 2020 at 16:25