/* Seating arrangement problem in Picat. Problem statement from From Texas Action Group (mailing list) "Seating Arrangements: Solutions" http://www.cs.utexas.edu/users/vl/tag/seating_problem """ You are organizing a New Year's Eve party. There will be N tables in the room, with M chairs around each table. You need to select a table for each of the guests, who are assigned numbers from 1 to MN, so that two conditions are satisfied. First, some guests like each other and want to sit together; accordingly, you are given a set A of two-element subsets of {1,...,MN}, and, for every {i,j} in A, guests i and j should be assigned the same table. Second, some guests dislike each other and want to sit at different tables; accordingly, you are given a set B of two-element subsets of {1,...,MN}, and, for every {i,j} in B, guests i and j should be assigned different tables. Your program should find such a seating arrangement or determine that it is impossible. """ Problem instances (Answer Set Programming) from "Seating Arrangements: Solutions" http://www.cs.utexas.edu/users/vl/tag/seating_solutions Also, see the discussions about the problem and solutions from an Answer Set Programming point of view. http://www.cs.utexas.edu/users/vl/tag/seating_discussion Here is the (unique) solution for problem 1: x = [1,1,2,3,3,2,3,2,1] Table 1: [ 1, 2, 9] Table 2: [ 3, 6, 8] Table 3: [ 4, 5, 7] Without symmetry breaking there are 6 solutions: x = [1,1,2,3,3,2,3,2,1] x = [1,1,3,2,2,3,2,3,1] x = [2,2,1,3,3,1,3,1,2] x = [2,2,3,1,1,3,1,3,2] x = [3,3,1,2,2,1,2,1,3] x = [3,3,2,1,1,2,1,2,3] Here are the first solutions for the other two problem instances: problem = 2 x = [1,1,2,2,2,2,1,2,2,1,1,1,1,2,1,2,1,1,2,2,3,3,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5,6,6,6,6,6,6,6,6,6,6,7,7,7,7,7,7,7,7,7,7,8,8,8,8,8,8,8,8,8,8,9,9,9,9,9,9,9,9,9,9,10,10,10,10,10,10,10,10,10,10] Table 1: [ 1, 2, 7, 10, 11, 12, 13, 15, 17, 18] Table 2: [ 3, 4, 5, 6, 8, 9, 14, 16, 19, 20] Table 3: [ 21, 22, 23, 24, 25, 26, 27, 28, 29, 30] Table 4: [ 31, 32, 33, 34, 35, 36, 37, 38, 39, 40] Table 5: [ 41, 42, 43, 44, 45, 46, 47, 48, 49, 50] Table 6: [ 51, 52, 53, 54, 55, 56, 57, 58, 59, 60] Table 7: [ 61, 62, 63, 64, 65, 66, 67, 68, 69, 70] Table 8: [ 71, 72, 73, 74, 75, 76, 77, 78, 79, 80] Table 9: [ 81, 82, 83, 84, 85, 86, 87, 88, 89, 90] Table 10: [ 91, 92, 93, 94, 95, 96, 97, 98, 99,100] problem = 3 x = [1,1,2,2,2,2,1,2,3,3,3,1,4,3,3,3,1,4,4,4,4,4,2,5,5,5,5,5,5,1] Table 1: [ 1, 2, 7, 12, 17, 30] Table 2: [ 3, 4, 5, 6, 8, 23] Table 3: [ 9, 10, 11, 14, 15, 16] Table 4: [ 13, 18, 19, 20, 21, 22] Table 5: [ 24, 25, 26, 27, 28, 29] This program was created by Hakan Kjellerstrand, hakank@gmail.com See also my Picat page: http://www.hakank.org/picat/ */ import cp. main => go. % Show all solutions for problem 1 go => problem(1,N,M,Likes,Dislikes), seating_arrangement(N,M,Likes,Dislikes, X), println(x=X), print_seating(N,M,X), fail, nl. % % Print one solution for each problem. % go2 => foreach(P in 1..3) println(problem=P), problem(P,N,M,Likes,Dislikes), seating_arrangement(N,M,Likes,Dislikes, X), println(x=X), print_seating(N,M,X) end, nl. % Print the seating print_seating(N,M,X) => K = N*M, foreach(Table in 1..N) printf("Table %2d: %w\n",Table,[to_fstring("%3d",I) : I in 1..K, X[I] == Table]) end, nl. seating_arrangement(N,M,Likes,Dislikes, X) => K = N*M, % number of persons NumLikes = Likes.len, NumDislikes = Dislikes.len, % which table is assigned for the persons X = new_list(K), X :: 1..N, % Ensure that people who like each other % is at the same table foreach(I in 1..NumLikes) X[Likes[I,1]] #= X[Likes[I,2]] end, % Ensure that people who dislike each other % is not at the same table foreach(I in 1..NumDislikes) X[Dislikes[I,1]] #!= X[Dislikes[I,2]] end, % There are exactly M persons at each table global_cardinality(X, $[I-M : I in 1..N]), % Symmetry breaking: % Do not place a person at table I unless tables 1..I-1 has % at least one placement. value_precede_chain(1..N, X), solve(X). % % Data % % Problem instance from % http://www.cs.utexas.edu/users/vl/tag/seating_solutions % "PROGRAM 11, for smodels, By Chitta Baral (chitta@asu.edu)" problem(1,N,M,Likes,Dislikes) => N = 3, % number of tables M = 3, % number of chairs at each table Likes = [[1,2], [7,4], [6,8]], Dislikes = [[2,3], [3,4], [5,6], [9,4]]. % Problem instance from % http://www.cs.utexas.edu/users/vl/tag/seating_solutions % "PROGRAM 13, for smodels, By Michael Gelfond (mgelfond@cs.ttu.edu)" problem(2,N,M,Likes,Dislikes) => N = 10, M = 10, Likes = [[1,2], [3,4], [5,6], [10,13], [10,11], [4,5]], Dislikes = [[1,5], [1,6], [12,16], [13,14], [7,8], [7,9]]. % Problem instance from % http://www.cs.utexas.edu/users/vl/tag/seating_solutions % "PROGRAM 16, for smodels, By Jonathan Campbell (campbell@cs.utexas.edu)" problem(3,N,M,Likes,Dislikes) => N = 5, M = 6, Likes = [[1, 7], [4, 23], [7, 30], [12, 30], [17, 30], [20, 21]], Dislikes = [[3, 10], [3, 11], [4, 12], [7, 28], [9, 30], [11, 13], [11, 17], [13, 14], [13, 16], [14, 25], [15, 17], [23, 25], [23, 29], [24, 30]]. % Do not assign a value I before at least one value of 1..I-1 % has been placed. value_precede_chain(C, X) => foreach(I in 2..C.length) value_precede(C[I-1], C[I], X) end. % This definition is inspired by % MiniZinc definition value_precede_int.mzn value_precede(S,T,X) => XLen = X.length, B = new_list(XLen+1), B :: 0..1, foreach(I in 1..XLen) % Xis :: 0..1, Xis #= (X[I] #= S), (Xis #=> (B[I+1] #= 1)) #/\ ((#~ Xis #= 1) #=> (B[I] #= B[I+1])) #/\ ((#~ B[I] #= 1) #=> (X[I] #!= T)) end, B[1] #= 0.