%% ======================================================== %% Auteur: Jean-Michel Richer %% email: jean-michel.richer@univ-angers.fr %% ======================================================== %% %% Problème des pigeons (PigeonHole Problem) : %% %% Etant donné N pigeons et P pigeonniers, chaque %% pigeon pourra t-il trouver un pigeonnier, sachant %% qu'un pigeonnier ne peut accueillir qu'un seul pigeon. %% %% Ce problème admet des solutions si N <= P. %% Si N > P alors, il n'y a pas de solution. %% %% ======================================================== include "globals.mzn"; %% -------------------------- %% Variables %% -------------------------- int: N = 3; int: P = 3; array[1..N,1..P] of var 0..1 : holes; %% -------------------------- %% Constraints %% -------------------------- constraint forall(i in 1..N) ( sum(holes[i,1..P]) = 1 ); constraint forall(j in 1..P) ( sum(holes[1..N,j]) <= 1 ); %% -------------------------- %% Search %% -------------------------- solve satisfy; %% -------------------------- %% Result %% -------------------------- output [ if j = 1 then "\n" else " " endif ++ show(holes[i,j]) ++ " " | i in 1..N, j in 1..P ] ++ ["\n"];