Debian Codegraph @

tests/spec/examples/quasigroup_qg5.mzn

raw
1 /***
2 !Test
3 expected:
4 - !Result
5 solution: !Solution
6 q:
7 - [1, 4, 5, 2, 3]
8 - [3, 2, 1, 5, 4]
9 - [4, 5, 3, 1, 2]
10 - [5, 3, 2, 4, 1]
11 - [2, 1, 4, 3, 5]
12 ***/
13
14 %% Bennett quasigroup existence problem (QG5).
15 %%
16 %% A quasigroup is just a groupoid whose "multiplication table" is a
17 %% Latin square: each row and each column is a permutation of the
18 %% elements. Bennett's equation (not invented by Frank Bennett but
19 %% studied by him) is (yx.y)y = x which forces the quasigroup to have
20 %% interesting properties such as being orthogonal to certain of its
21 %% conjugates. Idempotent ones are more important than the others.
22 %%
23 %% Bennett quasigroups exist for all positive N except for 2, 6, 10
24 %% and with the possible exceptions of 14, 18, 26, 30, 38, 42 and 158.
25 %%
26 %% Idempotent ones exist for all positive N not in {2, 3, 4, 6, 9, 10,
27 %% 12, 13, 14, 15, 16} except possibly for N in {18, 20, 22, 24, 26,
28 %% 28, 30, 34, 38, 39, 42, 44, 46, 51, 52, 58, 60, 62, 66, 68, 70, 72,
29 %% 74, 75, 76, 86, 87, 90, 94, 96, 98, 99, 100, 102, 106, 108, 110,
30 %% 114, 116, 118, 122, 132, 142, 146, 154, 158, 164, 170, 174}
31 %%
32 %% The existence of smallish open problems makes this algebraic
33 %% question attractive from the viewpoint of automated reasoning and
34 %% constraint satisfaction.
35 %%
36 %% Reference:
37 %% F. E. Bennett
38 %% Quasigroups
39 %% C. J. Colbourn (ed)
40 %% The CRC Handbook of Combinatorial Designs
41 %% Chapter 36, pp .424-429.
42
43 include "globals.mzn";
44
45 int: N;
46
47 array[1..N,1..N] of var 1..N: q;
48
49 constraint
50 forall( x in 1..N )
51 ( q[x, x] = x );
52
53 constraint
54 forall( x in 1..N )
55 ( alldifferent([q[x,y] | y in 1..N]) );
56
57 constraint
58 forall( y in 1..N )
59 ( alldifferent([q[x,y] | x in 1..N]) );
60
61 constraint
62 forall( x in 1..N )
63 ( q[x, 1] < x + 2 );
64
65 constraint
66 forall( x in 1..N, y in 1..N )
67 ( q[q[q[y, x], y], y] = x );
68
69 solve :: int_search(array1d(1..N*N, q), input_order, indomain, complete)
70 satisfy;
71
72 output ["Bennett quasigroup of size " ++ show(N) ++ ":\n"] ++
73 [ if y=1 then "\n " else " " endif ++ show(q[x,y]) | x,y in 1..N ] ++
74 [ "\n" ];
75
76 N = 5; % Solutions also exist for N=7, N=8 and N=11.