Download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
%
% Quasigroup problem 4 Idempotent in MiniZinc.
%
% This model is a translation of the EssencePrime model quasiGroup4Idempotent.eprime
% from the Minion Translator examples.
% """
% The quasiGroup existence problem (CSP lib problem 3)
%
% An m order quasigroup  is an mxm multiplication table of integers 1..m,
% where each element occurrs exactly once in each row and column and certain
% multiplication axioms hold (in this case, we want axiom 4 to hold).
% """
% See
% http://www.dcs.st-and.ac.uk/~ianm/CSPLib/prob/prob003/index.html
% http://www.dcs.st-and.ac.uk/~ianm/CSPLib/prob/prob003/spec.html
 
%
% This MiniZinc model was created by Hakan Kjellerstrand, hakank@gmail.com
% See also my MiniZinc page: http://www.hakank.org/minizinc/
%
 
% Licenced under CC-BY-4.0 : http://creativecommons.org/licenses/by/4.0/
 
include "globals.mzn";
 
int: n = 9; % solutions for n=5, n=9...
set of int: nDomain = 0..n-1;
 
array[nDomain, nDomain] of var nDomain: quasiGroup;
array[nDomain] of var nDomain: qgDiagonal;
 
% solve satisfy;
solve :: int_search([quasiGroup[row, col] | row, col in nDomain],
        first_fail, indomain_min, complete) satisfy;
 
constraint
 
     % accessor for diagonal
     forall(i in nDomain) (
         qgDiagonal[i] = quasiGroup[i,i]
     )
     /\
     % All rows have to be different
     forall(row in nDomain) (
          all_different([quasiGroup[row,col] | col in nDomain ] )
     )
     /\
     % All columns have to be different
     forall(col in nDomain) (
          all_different([quasiGroup[row,col] | row in nDomain] )
     )
     /\
     % (j*i)*(i*j) = i
     forall(i in nDomain) (
          forall(j in nDomain) (
                quasiGroup[quasiGroup[j,i],quasiGroup[i,j]] = i
          )
     )
     /\
     % Idempotency
     forall(i in nDomain) (
          quasiGroup[i,i] = i
     )
     /\
     % Implied (from Colton,Miguel 01)
     % All-diff diagonal
     all_different(qgDiagonal)
 
     /\
     % anti-Abelian
     forall(i in nDomain) (
       forall(j in nDomain) (
           (i != j) ->
             (quasiGroup[i,j] != quasiGroup[j,i])
       )
     )
     /\
     % if (i*i)=j then (j*j) = i
     forall(i in nDomain) (
       forall(j in nDomain) (
         (quasiGroup[i,i]=j) -> (quasiGroup[j,j]=i)
       )
     )
     /\
     % Symmetry-breaking constraints
     forall(i in nDomain) (
           quasiGroup[i,n-1] + 2 >= i
     )
;
 
 
output [
  if col = 0 then "\n" else " " endif ++
    show(quasiGroup[row, col])
  | row, col in nDomain
] ++ ["\n"];