1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 | % golfers.mzn % vim: ft=zinc ts=4 sw=4 et tw=0 % Ralph Becket <rafe@csse.unimelb.edu.au> % Mon Oct 29 13:56:25 EST 2007 % % The social golfers problem, see % http://www.dcs.st-and.ac.uk/~ianm/CSPLib/prob/prob001/data.txt % % A club has a number of golfers that play rounds in groups (the number of % golfers is a multiple of the number of groups). Each round, a golfer % plays with a group of different people, such that the same pair of golfers % never play together twice. include "globals.mzn" ; int : n_groups; % The number of groups. int : n_per_group; % The size of each group. int : n_rounds; % The number of rounds. int : n_golfers = n_groups * n_per_group; set of int : rounds = 1..n_rounds; set of int : golfers = 1..n_golfers; set of int : places = 1..n_golfers; array [rounds, places] of var golfers: round_place_golfer; array [golfers, golfers] of var 0..n_rounds: golfer_golfer_round; % Each member of each group must be distinct. % constraint forall (r in rounds) ( alldifferent (p in places) (round_place_golfer[r, p]) ); % Break some symmetry by strictly ordering each group in each round. % constraint forall (r in rounds, p in places) ( if p mod n_per_group != 0 then round_place_golfer[r, p] < round_place_golfer[r, p + 1] else true endif ); % Each pair can play together at most once. % constraint forall (r in rounds, g in 0..(n_groups - 1), i, j in 1..n_per_group where i < j) ( golfer_golfer_round[ round_place_golfer[r, n_per_group * g + i], round_place_golfer[r, n_per_group * g + j] ] = r ); solve :: int_search([round_place_golfer[r, p] | r in rounds, p in places], first_fail, indomain_min, complete) satisfy ; output [ "Social golfers:\n\n" , "Groups : " , show (n_groups), "\n" , "No. per group : " , show (n_per_group), "\n" , "No. of rounds : " , show (n_rounds), "\n" ] ++ [ ( if p = 1 then "\nround " ++ show (r) ++ ":" else "" endif ) ++ ( if p mod n_per_group = 1 then " " else " " endif ) ++ show_int (2, round_place_golfer[r, p]) | r in rounds, p in places ]; %-----------------------------------------------------------------------------% %-----------------------------------------------------------------------------% |