/* 

  Exact cover example in Picat.

  This is the example given in
  http://en.wikipedia.org/wiki/Exact_cover
  and
  http://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X#Example
  """
  For example, consider the exact cover problem specified by the 
  universe U = {1, 2, 3, 4, 5, 6, 7} and the collection of sets 
  {S} = {A, B, C, D, E, F}, where:
  
          A = {1, 4, 7};
          B = {1, 4};
          C = {4, 5, 7};
          D = {3, 5, 6};
          E = {2, 3, 6, 7}; and
          F = {2, 7}.
  
  This problem is represented by the matrix:
  
                1       2       3       4       5       6       7
      A         1       0       0       1       0       0       1
      B         1       0       0       1       0       0       0
      C         0       0       0       1       1       0       1
      D         0       0       1       0       1       1       0
      E         0       1       1       0       0       1       1
      F         0       1       0       0       0       0       1
  
  Algorithm X with Knuth's suggested heuristic for selecting columns 
  solves this problem as follows:
  ...
  """
  
  This model use a matrix representation instead of sets
  that where used in 
     http://www.hakank.org/picat/exact_cover_dlx.pi


  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 ?=>
  do_exact_cover(1),
  nl,
  do_exact_cover(2),
  nl.

go => true.

%
% Run a problem instance.
%
do_exact_cover(Problem) =>
 println(problem=Problem),
 data(Problem,N,M,Mat),
 exact_cover(N,M,Mat, X),
 println(x=X),
 fail,

 nl.


exact_cover(N,M,Mat, X) => 
 X = new_list(M),
 X :: 0..1,

 % ensure that all numbers 1..n are covered by exactly 
 % one choosen set
 foreach(J in 1..N)
    sum([X[I]*Mat[I,J]   : I in 1..M])  #= 1
 end,

 solve(X).


% One solution: S = {2,4,6} (i.e. {B,D,F})
data(1,N,M,Mat) =>
  N = 7,
  M = 6,
  Mat = 
   [   % 1 2 3 4 5 6 7 
     [1,0,0,1,0,0,1], % A {1, 4, 7}
     [1,0,0,1,0,0,0], % B {1, 4}
     [0,0,0,1,1,0,1], % C {4, 5, 7}
     [0,0,1,0,1,1,0], % D {3, 5, 6}
     [0,1,1,0,0,1,1], % E {2, 3, 6, 7}
     [0,1,0,0,0,0,1] % F {2, 7}
  ].