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!
$\begingroup$
$\endgroup$
4
asked Jan 19, 2021 at 1:09
-
$\begingroup$ This seems more like a search than a puzzle. I wonder how many of the 108776032459082956800 possible Latin squares would satisfy this? $\endgroup$– JayCommented Jan 19, 2021 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 KamenetskyCommented Jan 19, 2021 at 1:19
-
1$\begingroup$ Ok fair enough, I see there is some strategy in building it $\endgroup$– JayCommented Jan 19, 2021 at 1:21
-
5$\begingroup$ By using constraint programming, I found that there are 4,223,584 solutions. $\endgroup$– RobPrattCommented Jan 19, 2021 at 18:46
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
2
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)).
-
$\begingroup$ Very nice. I didn't even consider this solution. $\endgroup$ Commented Jan 19, 2021 at 4:04
-
3$\begingroup$ Actually, the solution is easily generalised to any $n\times n$ square for $n\geqslant6$. $\endgroup$ Commented Jan 19, 2021 at 16:20
$\begingroup$
$\endgroup$
1
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.
-
$\begingroup$ Nice. This is the solution I had in mind. $\endgroup$ Commented Jan 19, 2021 at 4:04
$\begingroup$
$\endgroup$
3
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
-
$\begingroup$ I don't think the code is right. On the bottom left corner of the first grid, 2 and 3 are adjacent. $\endgroup$– BubblerCommented Jan 19, 2021 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$– RobPrattCommented Jan 19, 2021 at 18:02
-
$\begingroup$ Thanks @RobPratt. I've corrected the code. $\endgroup$– crestorCommented Jan 21, 2021 at 10:29
$\begingroup$
$\endgroup$
1
The following Latin square meets the requirements you have set.
answered Jan 19, 2021 at 1:36
-
2$\begingroup$ You really should learn to use something easier to read than a picture of hand drawing. $\endgroup$– BubblerCommented Jan 19, 2021 at 1:43