# 8x8 square with no adjacent numbers summing to a prime

Can you fill a 8x8 grid with numbers from 1 to 8 such that:

• Every number occurs exactly once in each row and in each column (Latin square).
• No two adjacent (horizontally or vertically) numbers sum to a prime.

Good luck!

• This seems more like a search than a puzzle. I wonder how many of the 108776032459082956800 possible Latin squares would satisfy this?
– Jay
Jan 19, 2021 at 1:16
• @Jay the second constraint forces serious limitations on the structure of the square. Once you realize this, you will see that there are not that many options. The final solution has a lot of structure and beauty. Jan 19, 2021 at 1:19
• Ok fair enough, I see there is some strategy in building it
– Jay
Jan 19, 2021 at 1:21
• By using constraint programming, I found that there are 4,223,584 solutions. Jan 19, 2021 at 18:46

I think this works:

7 5 3 1 8 6 4 2
5 3 1 8 6 4 2 7
3 1 8 6 4 2 7 5
1 8 6 4 2 7 5 3
8 6 4 2 7 5 3 1
6 4 2 7 5 3 1 8
4 2 7 5 3 1 8 6
2 7 5 3 1 8 6 4

The adjacent number pairs are restricted to

(7,5), (5,3), (3,1), (1,8), (8,6), (6,4), (4,2), (2,7)

where each pair sums to

either an even number (greater than 2) or 9, all of which are composite.

Note that it is necessary to

minimize the boundary between an even and an odd number

because

the only possible odd sums are 9 (allowing four pairs) and 15 (only allowing (7,8)).

• Very nice. I didn't even consider this solution. Jan 19, 2021 at 4:04
• Actually, the solution is easily generalised to any $n\times n$ square for $n\geqslant6$. Jan 19, 2021 at 16:20

Here is another one:

7 5 3 1 8 6 4 2
1 7 5 3 6 4 2 8
3 1 7 5 4 2 8 6
5 3 1 7 2 8 6 4
4 6 8 2 7 1 3 5
2 4 6 8 1 3 5 7
8 2 4 6 3 5 7 1
6 8 2 4 5 7 1 3

Note that for any permutation of the first 4 columns there are 6 matching permutations of the last 4 that give rise to another solution. And similar for rows. So this is actually a family of solutions.

• Nice. This is the solution I had in mind. Jan 19, 2021 at 4:04

Quite easy using a constraint solver. For example Minizinc language and then using Gecode solver:

include "alldifferent.mzn";

int: N = 8;
array[1..N,1..N] of var 1..N: p;
set of int: not_primes = array2set([4, 6, 8, 9, 10, 12, 14, 15, 16]);

constraint forall(n in 1..N)(
alldifferent([p[n,g] |g in 1..N]) /\ alldifferent([p[g,n] |g in 1..N])
);
constraint forall(n in 1..N, g in 1..(N-1)) (
p[n,g]+p[n,g+1] in not_primes
);
constraint forall(n in 1..N, g in 1..(N-1)) (
p[g,n]+p[g+1,n] in not_primes
);

output  [show_int(1,p[i,j])++
if j == N then
if i != N then "\n"
else " " endif
else " " endif
| i,j in 1..N ] ++ ["\n"];


There are millions of solutions. (I didn't wait.).

8 2 4 6 3 1 7 5
6 4 2 8 1 7 5 3
3 5 7 1 8 2 4 6
1 7 5 3 6 4 2 8
5 3 1 7 2 8 6 4
7 1 3 5 4 6 8 2
2 8 6 4 5 3 1 7
4 6 8 2 7 5 3 1
----------
1 5 3 7 2 6 8 4
7 3 1 5 4 2 6 8
5 1 7 3 6 8 4 2
3 7 5 1 8 4 2 6
6 2 4 8 1 5 7 3
2 6 8 4 5 1 3 7
4 8 6 2 7 3 1 5
8 4 2 6 3 7 5 1
----------
7 3 1 5 4 8 6 2
3 7 5 1 8 2 4 6
5 1 3 7 2 6 8 4
1 5 7 3 6 4 2 8
8 4 2 6 3 5 7 1
4 6 8 2 7 1 3 5
2 8 6 4 5 7 1 3
6 2 4 8 1 3 5 7

• I don't think the code is right. On the bottom left corner of the first grid, 2 and 3 are adjacent. Jan 19, 2021 at 16:39
• The constraints for the last row (n = N and g < N) and last column (g = N and n < N) were omitted. Jan 19, 2021 at 18:02
• Thanks @RobPratt. I've corrected the code. Jan 21, 2021 at 10:29

The following Latin square meets the requirements you have set.

• You really should learn to use something easier to read than a picture of hand drawing. Jan 19, 2021 at 1:43