/* 

  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 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,S),
 exact_cover(N,M,S, X),
 println(x=X),
 println("The sets:"),
 foreach(J in 1..M)
   if X[J] == 1 then
     println(J=S[J])
   end
 end,
 nl,
 fail,

 nl.


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

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

      %  use this for the at most 1 version
      % sum(j in 1..m) ( x[j]*bool2int(i in s[j])) <= 1
 end,

 solve(X).



%
% does a contains e?
%
contains(E, A, B) =>
  sum([A[I] #= E : I in 1..A.len]) #>= 1 #<=> B #= 1.


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



% From Pearls of Discrete Mathematics, page 193
% (There are two solutions:  S = {1,2,3} or S = {1,4}
data(2,N,M,S) => 
  N = 5,
  M = 4,
  S = 
   [
      [1],      % A, 1
      [2],      % B, 2
      [3,4,5],  % C, 3
      [2,3,4,5] % D, 4
  ].