/* 

  Partial Latin square in Picat.

  http://mathworld.wolfram.com/PartialLatinSquare.html
  """
  In a normal n×n Latin square, the entries in each row and column are chosen from a 
  "global" set of n objects. Like a Latin square, a partial Latin square has no 
  two rows or columns which contain the same two symbols. However, in a partial 
  Latin square, each cell is assigned one of its own set of n possible "local" 
  (and distinct) symbols, chosen from an overall set of more than three distinct 
  symbols, and these symbols may vary from location to location. 

  For example, given the possible symbols {1,2,...,6} which must be arranged as

    (1,2,3)   (1,3,4)  (2,5,6)
    (2,3,5)   (1,2,3)  (4,5,6)
    (4,3,6)   (3,5,6)  (2,3,5)

  the 3×3 partial Latin square

    1,3,2
    2,1,5
    6,5,3
  
  can be constructed.
  """

  This Picat model implements the example above, which gives 1185 solutions.


  Somewhat later note: It seems that there is slightly other explanation
  of partial latin squares. For example http://www.keele.ac.uk/depts/ma/people/db.html ,
  which suggest that the latin square may contain cells where a specific value must 
  be put. In this model it simply means that the cardinality of that set is 1. 

  In Picat there is, however, another way of forcing an element in an array/matrix:
  by explicitly state that element. The cells with variable elements is then 
  represented with '_'. 
  Example: the following will force the cell x[1,1] to 2, and let the other cells
  be variable.

  X = 
  {
   {2, _, _},
   {_, _, _},
   {_, _, _}
  },

  See go2/0 for experimenting on this approach.


  This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/

import cp.


main => go.

go ?=>
  N = 3,
  MaxVal = 6,

  S = new_array(N, N,N),
  S :: 1..MaxVal,
  
  S ={{{1,2,3},  {1,3,4},  {2,5,6}},
      {{2,3,5},  {1,2,3},  {4,5,6}},
      {{4,3,6},  {3,5,6},  {2,3,5}}},

  X = new_array(N,N),
  X :: 1..MaxVal,
  
  % the elements in each cell is taken from the element in the cell of s
  foreach(I in 1..N, J in 1..N)
     sum([ X[I,J] #= S[I,J,K] : K in 1..N]) #= 1 
  end,
  
  latin_square(X),

  Vars = X.vars ++ S.vars,
  solve(Vars),

  foreach(Row in X)
    println(Row)
  end,
  nl,
  fail,
  
  nl.

go => true.


%
% Testing the other approach with fixed entries in X.
% 
%
go2 ?=>
  N = 3,
  MaxVal = 6,

  X = new_array(N,N),
  X :: 1..MaxVal,

  % This has 52960 solutions
  X = {{2, _, _},
       {_, _, _},
       {_, _, _}},

  latin_square(X),

  Vars = X.vars,
  solve(Vars),

  foreach(Row in X)
    println(Row)
  end,
  nl,
  fail,
  
  nl.

go2 => true.


%
% X must be a latin square, i.e. all element in each row is
% different, and all element in each column is diffeerent
%
latin_square(M) =>
  N = M.len,
  foreach(I in 1..N)
    all_different([ M[I, J] : J in 1..N]),
    all_different([ M[J, I] : J in 1..N])
  end.