5
$\begingroup$

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!

$\endgroup$
4
  • $\begingroup$ This seems more like a search than a puzzle. I wonder how many of the 108776032459082956800 possible Latin squares would satisfy this? $\endgroup$ – Jay Jan 19 at 1:16
  • $\begingroup$ @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. $\endgroup$ – Dmitry Kamenetsky Jan 19 at 1:19
  • 1
    $\begingroup$ Ok fair enough, I see there is some strategy in building it $\endgroup$ – Jay Jan 19 at 1:21
  • 4
    $\begingroup$ By using constraint programming, I found that there are 4,223,584 solutions. $\endgroup$ – RobPratt Jan 19 at 18:46
10
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Very nice. I didn't even consider this solution. $\endgroup$ – Dmitry Kamenetsky Jan 19 at 4:04
  • 2
    $\begingroup$ Actually, the solution is easily generalised to any $n\times n$ square for $n\geqslant6$. $\endgroup$ – trolley813 Jan 19 at 16:20
6
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Nice. This is the solution I had in mind. $\endgroup$ – Dmitry Kamenetsky Jan 19 at 4:04
1
$\begingroup$

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
$\endgroup$
3
  • $\begingroup$ I don't think the code is right. On the bottom left corner of the first grid, 2 and 3 are adjacent. $\endgroup$ – Bubbler Jan 19 at 16:39
  • $\begingroup$ The constraints for the last row (n = N and g < N) and last column (g = N and n < N) were omitted. $\endgroup$ – RobPratt Jan 19 at 18:02
  • $\begingroup$ Thanks @RobPratt. I've corrected the code. $\endgroup$ – crestor Jan 21 at 10:29
-2
$\begingroup$

The following Latin square meets the requirements you have set.

![Jan18

$\endgroup$
1
  • 2
    $\begingroup$ You really should learn to use something easier to read than a picture of hand drawing. $\endgroup$ – Bubbler Jan 19 at 1:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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