% 
% Quasigroup completion problem in MiniZinc.
% 
% See 
% Carla P. Gomes and David Shmoys:
% "Completing Quasigroups or Latin Squares: Structured Graph Coloring Problem"
%
% Demo applet by Carla P. Gomes
% http://www.cs.cornell.edu/gomes/QUASIdemo.html
  
% See also
% Ivars Peterson "Completing Latin Squares"
% http://www.maa.org/mathland/mathtrek_5_8_00.html
% """
% Using only the numbers 1, 2, 3, and 4, arrange four sets of these numbers into 
% a four-by-four array so that no column or row contains the same two numbers. 
% The result is known as a Latin square.
% ...
% The so-called quasigroup completion problem concerns a table that is correctly 
% but only partially filled in. The question is whether the remaining blanks in 
% the table can be filled in to obtain a complete Latin square (or a proper 
% quasigroup multiplication table).
% """
% 
%
% This is the model. For example problems see (e.g.)
% quasigroup_completion_gomes_shmoys_p3.mzn
% quasigroup_completion_gomes_shmoys_p5.mzn
% quasigroup_completion_gomes_shmoys_p7.mzn
% quasigroup_completion_martin_lynce.mzn
% quasigroup_completion_gcc.mzn
% quasigroup_completion_gomes_demo1.mzn
% quasigroup_completion_gomes_demo2.mzn
% quasigroup_completion_gomes_demo3.mzn
% quasigroup_completion_gomes_demo4.mzn
% quasigroup_completion_gomes_demo5.mzn

% 
% This MiniZinc model was created by Hakan Kjellerstrand, hakank@bonetmail.com
% See also my MiniZinc page: http://www.hakank.org/minizinc

include "globals.mzn"; 

int: n;
array[1..n, 1..n] of var 1..n: x;

%
% Predicate k all different.
%
predicate k_all_different(array[int, int] of var int: x) =
    forall(i in index_set_1of2(x)) (
       all_different([x[i,j] | j in index_set_2of2(x)]) 
       /\
       all_different([x[j,i] | j in index_set_2of2(x)]) 
    )   
;

predicate cp2d(array[int,int] of var int: x, array[int,int] of var int: y) =
  assert(index_set_1of2(x) = index_set_1of2(y) /\
         index_set_2of2(x) = index_set_2of2(y),
           "cp2d: x and y have different sizes",
     forall(i in index_set_1of2(x), j in index_set_2of2(x)) (
         y[i,j] = x[i,j]
    ) 
  )
; 

solve satisfy;
% solve :: int_search([x[i,j] | i,j in 1..n], max_regret, indomain_min, complete) satisfy;

constraint

    % make it a Latin Square (quasigroup)
    k_all_different(x)
;

output [
  if j = 1 then "\n" else " " endif ++
    show(x[i,j])  
  | i,j in 1..n

] ++ ["\n"];