/*
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.