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" ]; |