To elaborate the 2 points from the latest comments of @donman and me:
Another approach (4) Global Constraint connected()
We can make use of it by
ns and es, respectively, andpredicate connected(array [$$E] of $$N: from,
array [$$E] of $$N: to,
array [$$N] of var bool: ns,
array [$$E] of var bool: es)
This 35x35 Hitori:
hitori_35x35 = [
[27, 33, 32, 20, 1, 12, 27, 35, 34, 3, 17, 34, 22, 1, 10, 4, 1, 23, 4, 24, 25, 24, 19, 16, 34, 26, 4, 15, 32, 29, 27, 18, 3, 5, 34],
[34, 9, 20, 11, 30, 19, 31, 17, 16, 22, 17, 5, 6, 14, 17, 3, 17, 11, 18, 26, 11, 33, 12, 7, 4, 25, 2, 25, 8, 11, 21, 32, 12, 19, 23],
[35, 16, 10, 5, 33, 21, 29, 2, 4, 16, 8, 31, 29, 6, 11, 13, 20, 16, 26, 29, 1, 16, 9, 16, 29, 18, 33, 17, 13, 30, 27, 33, 23, 16, 19],
[ 2, 1, 33, 15, 10, 3, 4, 11, 18, 25, 9, 33, 27, 11, 24, 26, 25, 12, 16, 29, 34, 10, 22, 10, 28, 25, 30, 25, 6, 8, 10, 31, 11, 20, 35],
[ 6, 18, 4, 24, 22, 15, 13, 25, 8, 26, 8, 9, 17, 33, 8, 30, 12, 6, 27, 20, 30, 32, 17, 23, 8, 16, 13, 34, 3, 17, 35, 6, 17, 2, 17],
[ 3, 22, 23, 2, 27, 23, 10, 22, 32, 19, 6, 19, 13, 23, 14, 20, 19, 30, 22, 25, 19, 27, 35, 19, 15, 19, 1, 23, 24, 21, 33, 27, 5, 27, 18],
[ 9, 31, 7, 25, 15, 29, 25, 32, 13, 4, 35, 19, 33, 18, 13, 17, 5, 27, 22, 13, 6, 9, 10, 9, 12, 11, 26, 30, 24, 2, 33, 3, 25, 1, 24],
[19, 27, 33, 9, 12, 24, 5, 31, 11, 29, 1, 12, 25, 12, 20, 29, 12, 22, 12, 8, 27, 2, 27, 35, 29, 4, 6, 12, 7, 12, 14, 27, 3, 12, 10],
[21, 14, 6, 7, 34, 6, 3, 21, 23, 31, 21, 17, 6, 29, 21, 5, 4, 21, 1, 21, 9, 6, 25, 6, 2, 12, 6, 11, 21, 16, 6, 30, 6, 22, 6],
[32, 11, 3, 23, 28, 9, 15, 1, 35, 17, 21, 23, 26, 35, 7, 35, 8, 14, 15, 27, 19, 22, 35, 34, 10, 5, 18, 19, 2, 20, 25, 24, 4, 13, 16],
[33, 32, 33, 11, 26, 33, 22, 3, 9, 29, 3, 16, 33, 34, 2, 31, 3, 7, 13, 3, 5, 3, 4, 33, 6, 33, 12, 3, 19, 3, 15, 21, 33, 8, 27],
[22, 8, 35, 16, 9, 6, 23, 15, 24, 8, 33, 27, 34, 32, 9, 11, 1, 27, 23, 12, 23, 25, 8, 30, 27, 10, 9, 13, 27, 5, 7, 7, 29, 21, 8],
[10, 15, 13, 10, 27, 10, 30, 5, 28, 18, 5, 4, 28, 23, 6, 10, 2, 3, 9, 5, 35, 10, 21, 25, 22, 25, 32, 5, 12, 10, 1, 20, 11, 25, 17],
[33, 12, 8, 14, 12, 4, 13, 28, 7, 21, 2, 20, 17, 14, 32, 34, 14, 31, 6, 15, 13, 29, 21, 27, 14, 9, 13, 10, 21, 26, 5, 22, 12, 18, 13],
[11, 6, 30, 25, 30, 10, 13, 18, 8, 32, 22, 30, 4, 16, 27, 35, 21, 29, 11, 7, 12, 18, 2, 9, 31, 30, 23, 18, 17, 28, 9, 19, 33, 9, 5],
[20, 17, 2, 11, 4, 13, 26, 6, 19, 12, 5, 18, 11, 21, 19, 32, 26, 16, 25, 10, 22, 20, 26, 33, 19, 11, 8, 9, 23, 19, 24, 11, 15, 7, 20],
[14, 32, 32, 12, 4, 22, 7, 19, 34, 4, 16, 4, 2, 10, 33, 29, 15, 18, 29, 13, 29, 23, 5, 32, 1, 3, 29, 21, 29, 6, 19, 9, 29, 4, 8],
[17, 23, 14, 14, 2, 27, 29, 34, 10, 20, 29, 24, 15, 27, 26, 10, 11, 28, 3, 17, 7, 30, 28, 13, 17, 8, 33, 28, 5, 10, 9, 35, 28, 31, 27],
[ 8, 5, 24, 31, 16, 19, 6, 4, 14, 5, 27, 24, 28, 25, 24, 1, 4, 34, 2, 5, 17, 4, 33, 2, 30, 7, 28, 22, 5, 23, 16, 2, 20, 5, 12],
[ 9, 2, 18, 4, 20, 30, 34, 29, 2, 21, 34, 13, 24, 2, 12, 32, 28, 4, 4, 19, 4, 31, 17, 5, 8, 1, 34, 23, 15, 4, 6, 27, 4, 25, 32],
[19, 10, 28, 33, 11, 19, 20, 22, 17, 19, 31, 19, 5, 13, 21, 27, 19, 28, 34, 28, 8, 28, 23, 28, 9, 28, 35, 28, 4, 3, 30, 26, 24, 14, 19],
[10, 4, 5, 26, 4, 25, 35, 35, 20, 4, 3, 7, 12, 4, 30, 8, 9, 24, 4, 2, 11, 15, 11, 31, 11, 34, 10, 29, 18, 7, 32, 18, 14, 4, 22],
[30, 21, 6, 23, 32, 2, 29, 14, 2, 33, 7, 8, 21, 3, 28, 2, 16, 7, 17, 22, 20, 25, 27, 22, 25, 21, 4, 26, 11, 9, 7, 13, 26, 15, 7],
[ 5, 7, 11, 6, 16, 32, 9, 8, 27, 9, 30, 9, 1, 24, 22, 21, 22, 35, 5, 18, 16, 26, 20, 22, 14, 5, 24, 33, 24, 17, 3, 22, 34, 24, 29],
[ 5, 24, 5, 17, 8, 20, 25, 1, 21, 23, 20, 3, 19, 12, 29, 17, 27, 1, 4, 9, 14, 34, 30, 18, 5, 13, 22, 14, 28, 14, 26, 14, 32, 10, 14],
[13, 10, 22, 8, 10, 14, 29, 27, 12, 29, 7, 29, 11, 31, 29, 9, 29, 2, 29, 28, 18, 28, 6, 26, 21, 29, 10, 3, 10, 15, 29, 5, 29, 26, 4],
[25, 5, 12, 35, 17, 31, 23, 24, 6, 30, 25, 22, 8, 11, 13, 25, 33, 11, 28, 4, 6, 7, 14, 21, 25, 14, 15, 12, 9, 8, 29, 6, 19, 11, 8],
[12, 4, 26, 32, 7, 11, 2, 27, 15, 8, 23, 32, 20, 9, 30, 14, 19, 33, 30, 27, 21, 1, 31, 32, 27, 22, 8, 24, 16, 13, 4, 29, 32, 3, 25],
[17, 16, 2, 3, 21, 17, 14, 9, 2, 10, 21, 34, 23, 21, 18, 2, 22, 21, 20, 30, 2, 28, 15, 2, 24, 21, 5, 7, 21, 4, 2, 33, 13, 35, 17],
[ 1, 6, 30, 14, 9, 34, 19, 20, 3, 13, 12, 6, 28, 8, 6, 22, 6, 5, 29, 14, 10, 14, 13, 4, 6, 33, 19, 18, 27, 25, 18, 2, 31, 24, 28],
[15, 30, 19, 29, 23, 8, 17, 5, 10, 14, 19, 32, 16, 5, 25, 9, 26, 9, 16, 31, 16, 13, 24, 5, 18, 15, 27, 20, 35, 5, 22, 8, 1, 9, 3],
[ 7, 33, 1, 19, 34, 17, 33, 12, 33, 5, 15, 33, 32, 9, 4, 16, 9, 21, 24, 33, 13, 9, 11, 3, 11, 20, 34, 35, 34, 27, 9, 8, 34, 6, 33],
[27, 21, 1, 22, 25, 1, 19, 10, 33, 27, 13, 12, 23, 20, 31, 23, 18, 15, 7, 11, 1, 4, 34, 24, 32, 27, 3, 1, 30, 24, 28, 1, 8, 24, 14],
[23, 9, 15, 14, 5, 28, 32, 31, 26, 27, 18, 9, 21, 24, 27, 13, 31, 20, 9, 3, 29, 8, 14, 11, 33, 25, 31, 1, 9, 19, 27, 34, 29, 30, 9],
[21, 3, 28, 13, 14, 20, 34, 26, 34, 9, 14, 2, 30, 22, 1, 28, 31, 25, 12, 30, 4, 16, 8, 34, 7, 16, 29, 14, 33, 30, 10, 16, 27, 30, 15]
]
… is solved with the chuffed solver in about 1.5s (minizinc via Python@colab):
Hitori:
. 33 . 20 1 12 27 35 . 3 17 . 22 . 10 4 . 23 . 24 25 . 19 16 34 26 . 15 32 29 . 18 . 5 .
34 9 20 . 30 . 31 . 16 22 . 5 6 14 . 3 17 11 18 26 . 33 . 7 4 . 2 25 8 . 21 32 12 19 23
35 . 10 5 33 21 . 2 4 . 8 31 . 6 11 . 20 . 26 . 1 16 9 . 29 18 . 17 13 30 27 . 23 . 19
2 1 . 15 . 3 4 11 18 25 9 33 27 . 24 26 . 12 16 29 34 . 22 10 28 . 30 . 6 8 . 31 . 20 35
. 18 4 24 22 15 . 25 . 26 . 9 . 33 8 30 12 . 27 20 . 32 . 23 . 16 13 34 3 . 35 6 17 2 .
3 22 . 2 . 23 10 . 32 . 6 . 13 . 14 20 . 30 . 25 19 27 35 . 15 . 1 . 24 21 33 . 5 . 18
. 31 7 . 15 29 . 32 13 4 35 19 33 18 . 17 5 27 22 . 6 . 10 9 12 11 26 30 . 2 . 3 25 1 24
19 27 33 9 . 24 5 31 11 . 1 . 25 . 20 29 . 22 . 8 . 2 . 35 . 4 6 . 7 12 14 . 3 . 10
. 14 . 7 34 . 3 . 23 31 . 17 . 29 . 5 4 . 1 21 9 6 25 . 2 12 . 11 . 16 . 30 . 22 .
32 11 3 . 28 9 15 1 . 17 21 23 26 35 7 . 8 14 . 27 . 22 . 34 10 5 18 19 2 20 25 24 4 13 16
. 32 . 11 26 33 22 . 9 29 . 16 . 34 2 31 . 7 13 . 5 3 4 . 6 . 12 . 19 . 15 21 . 8 27
22 8 35 16 . 6 . 15 24 . 33 27 34 32 . 11 1 . 23 12 . 25 . 30 . 10 9 13 . 5 7 . 29 21 .
. 15 13 . 27 . 30 5 28 18 . 4 . 23 6 . 2 3 9 . 35 10 21 25 22 . 32 . 12 . 1 20 11 . 17
33 . 8 14 12 4 . 28 7 . 2 20 17 . 32 34 . 31 6 15 . 29 . 27 . 9 . 10 21 26 5 22 . 18 13
11 6 . 25 . 10 13 . 8 32 22 . 4 16 27 35 21 29 . 7 12 18 2 . 31 30 23 . 17 28 . 19 33 9 5
20 17 2 . 4 13 . 6 . 12 5 18 . 21 . 32 . 16 25 10 22 . 26 33 19 . 8 9 23 . 24 11 15 7 .
14 . 32 12 . 22 7 19 34 . 16 . 2 10 33 . 15 18 . 13 . 23 5 . 1 3 . 21 29 6 . 9 . 4 8
. 23 14 . 2 27 . 34 . 20 29 24 15 . 26 10 11 . 3 . 7 30 . 13 17 8 33 . 5 . 9 35 28 31 .
8 . 24 31 . 19 6 4 14 . 27 . 28 25 . 1 . 34 2 5 17 . 33 . 30 7 . 22 . 23 16 . 20 . 12
9 2 18 . 20 30 . 29 . 21 . 13 24 . 12 . 28 4 . 19 . 31 17 5 8 1 34 23 15 . 6 27 . 25 32
. 10 . 33 11 . 20 22 17 19 31 . 5 13 21 27 . 28 34 . 8 . 23 . 9 . 35 . 4 3 30 26 24 14 .
10 4 5 26 . 25 35 . 20 . 3 7 12 . 30 8 9 24 . 2 11 15 . 31 . 34 . 29 18 . 32 . 14 . 22
30 . 6 23 32 . 29 14 2 33 . 8 . 3 28 . 16 . 17 . 20 . 27 22 25 21 4 . 11 9 . 13 26 15 7
. 7 11 6 . 32 9 8 27 . 30 . 1 . 22 21 . 35 5 18 16 26 20 . 14 . 24 33 . 17 3 . 34 . 29
5 24 . 17 8 . 25 . 21 23 20 3 19 12 29 . 27 1 4 9 . 34 30 18 . 13 22 . 28 . 26 14 32 10 .
13 . 22 8 . 14 . 27 12 . 7 . 11 31 . 9 . 2 . 28 18 . 6 . 21 29 . 3 10 15 . 5 . 26 4
. 5 12 35 17 31 23 24 6 30 . 22 8 . 13 25 33 . 28 4 . 7 . 21 . 14 15 . 9 . 29 . 19 11 .
12 . 26 . 7 11 2 . 15 8 23 . 20 9 . 14 19 33 30 . 21 1 31 32 27 22 . 24 16 13 4 29 . 3 25
17 16 . 3 21 . 14 9 . 10 . 34 23 . 18 2 22 . 20 30 . 28 15 . 24 . 5 7 . 4 . 33 13 35 .
1 . 30 . 9 34 . 20 3 . 12 6 . 8 . 22 . 5 29 14 10 . 13 4 . 33 19 . 27 25 18 2 31 24 28
15 30 19 29 23 8 17 . 10 14 . 32 16 5 25 . 26 9 . 31 . 13 24 . 18 . 27 20 35 . 22 . 1 . 3
7 . 1 19 . 17 . 12 . 5 15 . 32 . 4 16 . 21 24 . 13 9 . 3 11 20 . 35 34 27 . 8 . 6 33
27 21 . 22 25 . 19 10 33 . 13 12 . 20 31 23 18 15 7 11 . 4 34 . 32 . 3 . 30 24 28 1 8 . 14
23 . 15 . 5 28 32 . 26 27 18 . 21 24 . 13 . 20 . 3 29 8 14 11 33 25 31 1 . 19 . 34 . 30 9
21 3 28 13 . 20 34 26 . 9 . 2 30 22 1 . 31 25 12 . 4 . 8 . 7 . 29 14 33 . 10 16 27 . 15
Unshaded:
0 1 0 1 1 1 1 1 0 1 1 0 1 0 1 1 0 1 0 1 1 0 1 1 1 1 0 1 1 1 0 1 0 1 0
1 1 1 0 1 0 1 0 1 1 0 1 1 1 0 1 1 1 1 1 0 1 0 1 1 0 1 1 1 0 1 1 1 1 1
1 0 1 1 1 1 0 1 1 0 1 1 0 1 1 0 1 0 1 0 1 1 1 0 1 1 0 1 1 1 1 0 1 0 1
1 1 0 1 0 1 1 1 1 1 1 1 1 0 1 1 0 1 1 1 1 0 1 1 1 0 1 0 1 1 0 1 0 1 1
0 1 1 1 1 1 0 1 0 1 0 1 0 1 1 1 1 0 1 1 0 1 0 1 0 1 1 1 1 0 1 1 1 1 0
1 1 0 1 0 1 1 0 1 0 1 0 1 0 1 1 0 1 0 1 1 1 1 0 1 0 1 0 1 1 1 0 1 0 1
0 1 1 0 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0 1 0 1 1 1 1 1 1 0 1 0 1 1 1 1
1 1 1 1 0 1 1 1 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1 1 0 1 1 1 0 1 0 1
0 1 0 1 1 0 1 0 1 1 0 1 0 1 0 1 1 0 1 1 1 1 1 0 1 1 0 1 0 1 0 1 0 1 0
1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 0 1 1 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1
0 1 0 1 1 1 1 0 1 1 0 1 0 1 1 1 0 1 1 0 1 1 1 0 1 0 1 0 1 0 1 1 0 1 1
1 1 1 1 0 1 0 1 1 0 1 1 1 1 0 1 1 0 1 1 0 1 0 1 0 1 1 1 0 1 1 0 1 1 0
0 1 1 0 1 0 1 1 1 1 0 1 0 1 1 0 1 1 1 0 1 1 1 1 1 0 1 0 1 0 1 1 1 0 1
1 0 1 1 1 1 0 1 1 0 1 1 1 0 1 1 0 1 1 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 1
1 1 0 1 0 1 1 0 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 0 1 1 0 1 1 1 1
1 1 1 0 1 1 0 1 0 1 1 1 0 1 0 1 0 1 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1 0
1 0 1 1 0 1 1 1 1 0 1 0 1 1 1 0 1 1 0 1 0 1 1 0 1 1 0 1 1 1 0 1 0 1 1
0 1 1 0 1 1 0 1 0 1 1 1 1 0 1 1 1 0 1 0 1 1 0 1 1 1 1 0 1 0 1 1 1 1 0
1 0 1 1 0 1 1 1 1 0 1 0 1 1 0 1 0 1 1 1 1 0 1 0 1 1 0 1 0 1 1 0 1 0 1
1 1 1 0 1 1 0 1 0 1 0 1 1 0 1 0 1 1 0 1 0 1 1 1 1 1 1 1 1 0 1 1 0 1 1
0 1 0 1 1 0 1 1 1 1 1 0 1 1 1 1 0 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 0
1 1 1 1 0 1 1 0 1 0 1 1 1 0 1 1 1 1 0 1 1 1 0 1 0 1 0 1 1 0 1 0 1 0 1
1 0 1 1 1 0 1 1 1 1 0 1 0 1 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 1 0 1 1 1 1
0 1 1 1 0 1 1 1 1 0 1 0 1 0 1 1 0 1 1 1 1 1 1 0 1 0 1 1 0 1 1 0 1 0 1
1 1 0 1 1 0 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 0 1 1 0 1 0 1 1 1 1 0
1 0 1 1 0 1 0 1 1 0 1 0 1 1 0 1 0 1 0 1 1 0 1 0 1 1 0 1 1 1 0 1 0 1 1
0 1 1 1 1 1 1 1 1 1 0 1 1 0 1 1 1 0 1 1 0 1 0 1 0 1 1 0 1 0 1 0 1 1 0
1 0 1 0 1 1 1 0 1 1 1 0 1 1 0 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1
1 1 0 1 1 0 1 1 0 1 0 1 1 0 1 1 1 0 1 1 0 1 1 0 1 0 1 1 0 1 0 1 1 1 0
1 0 1 0 1 1 0 1 1 0 1 1 0 1 0 1 0 1 1 1 1 0 1 1 0 1 1 0 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 1 1 0 1 1 1 1 0 1 1 0 1 0 1 1 0 1 0 1 1 1 0 1 0 1 0 1
1 0 1 1 0 1 0 1 0 1 1 0 1 0 1 1 0 1 1 0 1 1 0 1 1 1 0 1 1 1 0 1 0 1 1
1 1 0 1 1 0 1 1 1 0 1 1 0 1 1 1 1 1 1 1 0 1 1 0 1 0 1 0 1 1 1 1 1 0 1
1 0 1 0 1 1 1 0 1 1 1 0 1 1 0 1 0 1 0 1 1 1 1 1 1 1 1 1 0 1 0 1 0 1 1
1 1 1 1 0 1 1 1 0 1 0 1 1 1 1 0 1 1 1 0 1 0 1 0 1 0 1 1 1 0 1 1 1 0 1
{'paths': 0,
'flatBoolVars': 4830,
'flatIntVars': 2450,
'flatBoolConstraints': 3606,
'flatIntConstraints': 6125,
'evaluatedHalfReifiedConstraints': 2450,
'eliminatedImplications': 1225,
'method': 'satisfy',
'flatTime': datetime.timedelta(microseconds=546540),
'time': datetime.timedelta(seconds=1, microseconds=539000),
'nodes': 3,
'failures': 1,
'restarts': 0,
'variables': 1020589,
'intVars': 2450,
'boolVariables': 1018137,
'propagators': 2522,
'propagations': 7477,
'peakDepth': 2,
'nogoods': 1,
'backjumps': 1,
'peakMem': 0.0,
'initTime': datetime.timedelta(seconds=1, microseconds=290000),
'solveTime': datetime.timedelta(microseconds=249000),
'baseMem': 0.0,
'trailMem': 0.42,
'randomSeed': 553203394,
'nSolutions': 1}
Interestingly, in the same Colab environment but modeled directly with CP-SAT, the 35x35 Hitori is solved faster with any of the approaches presented in the previous answers, except for method (1) transitivity.
These are the stats for CP-SAT with the fastest model for 35x35:
Method (3b) i.e., instead of +1, just GT the min. adjacent neighbors
CpSolverResponse summary:
status: OPTIMAL
objective: 0
best_bound: 0
integers: 1474
booleans: 1
conflicts: 0
branches: 2
propagations: 0
integer_propagations: 9287
restarts: 2
lp_iterations: 0
walltime: 0.407316
usertime: 0.407316
deterministic_time: 0.0461002
gap_integral: 0
solution_fingerprint: 0xc77004407055b303