/*

  Pigeon hole problem in Picat.

  From
  ftp://ftp.inria.fr/INRIA/Projects/contraintes/publications/CLP-FD/plilp94.html
  """
  pigeon: the pigeon-hole problem consists in putting n pigeons in m pigeon-holes 
  (at most 1 pigeon per hole). The boolean formulation uses n - m variables to 
  indicate, for each pigeon, its hole number. Obviously, there is a 
  solution iff n <= m.
  """

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

*/

import util.
import cp.

main => go.

go => 
   N = 3,  % N pigeons
   M = 10, % M pigeon holes     
   wrapper(N,M).

% This is an impossible problem (M < N)
go2 =>
   N = 5,  % N pigeons
   M = 4, % M pigeon holes
   wrapper(N,M).


wrapper(N,M) =>
   L = findall(P, $pigeon_hole(N,M, P)),
   foreach(Sol in L) pretty_print(Sol) end,
   printf("It was %d solutions.\n", L.length).

pigeon_hole(N,M, PigeonHoles) =>

   % N pigeons at M pigeon holes
   PigeonHoles = new_array(N,M),
   PigeonHoles :: 0..1,
   
   writeln(here1),
   writeln(row_len=PigeonHoles.length),
   writeln(col_len=PigeonHoles[1].length),

   % all pigeon must be placed and only at one hole (rows)
   % foreach(Row in PigeonHoles) sum(Row) #=1 end, % this don't work

   foreach(Row in PigeonHoles) sum(Row.to_list()) #=1 end, % must explicitly convert Row to list
   % foreach(I in 1..N) sum([$PigeonHoles[I,J] : J in 1..M]) #=1 end,

   % max 1 pigeon per pigeon hole (columns)
   foreach(Column in transpose(PigeonHoles).array_matrix_to_list_matrix()) sum(Column) #=< 1 end,

   solve([ff],PigeonHoles).


pretty_print(X) =>
   foreach(Row in X) writeln(Row) end, 
   nl.