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