/* Movie theater seating problem in Picat. Row seating problem. Problem formulation from Fei Dai, Mohit Dhawan, Changfu Wu and Jie Wu "On Solutions to a Seating Problem", page 1 """ n couples are seated in one row. Each person, except two seated at the two ends, has two neighbors. It is required that each neighbor of person k should either have the same gender or be the spouse of k. """ Reasonable pattern (from the same page as above): """ A reasonable pattern is an assignment of n couples without indices that meet the above requirement. For example, when n = 3 all reasonable patterns are as follows: wwwhhh whhwwh whhhww hhwwwh hhhwww hwwhhw hwwwhh wwhhhw """ Coding of a couple i: husband: 2*(i-1)+1 = 0 wife : 2*(i-1)+2 = 1 Note: This model don't really care about the reasonable patterns since I'm interested in the concrete seating placements. For N=3 there is a total of 60 solutions (w/o symmetry breaking), with 8 different patterns. The first number indicates the occurences of each pattern. 12 hhhwww 6 hhwwwh 6 hwwhhw 6 hwwwhh 6 whhhww 6 whhwwh 6 wwhhhw 12 wwwhhh (See more in go3/0.) Cf seating_table.pi which models (circular) table seating. This program was created by Hakan Kjellerstrand, hakank@gmail.com See also my Picat page: http://www.hakank.org/picat/ */ import cp. main => go. go => N = 3, % number of couples M = 2*N, % number of persons GenderStr = ["h","w"], println(couples=couples(N)), nl, row_seating(N,M,Couples, X,Gender), println('x '=[to_fstring("%2d",X[I]) : I in 1..M]), println('couple'=[to_fstring("%2d",(X[I]+1) div 2) : I in 1..M]), println(gender=[to_fstring("%2w",GenderStr[G]) : G in Gender]), nl, fail, nl. /* Count the number of solutions * With symmetry breaking: fixing first person 1: 2 2: 4 3: 20 4: 204 5: 3504 6: 91680 7: 3405600 2,4,20,204,3504,91680,3405600 Not in OEIS * Without symmetry breaking 1: 2 2: 8 3: 60 4: 816 5: 17520 6: 550080 7: 23839200 2,8,60,816,17520,550080,23839200 https://oeis.org/A096121: "Number of full spectrum rook's walks on a (2 X n) board." */ go2 => foreach(N in 1..7) Count = count_all(row_seating(N, _M,_Couples,_X,_Gender)), printf("%d: %d\n",N,Count) end, nl. /* Number of the different patterns for N = 1..6 1 = [wh = 1,hw = 1] 2 = [wwhh = 2,whhw = 2,hwwh = 2,hhww = 2] 3 = [wwwhhh = 12,hhhwww = 12,wwhhhw = 6,whhwwh = 6,whhhww = 6,hwwwhh = 6,hwwhhw = 6,hhwwwh = 6] 4 = [wwwwhhhh = 144,hhhhwwww = 144,wwwhhhhw = 48,wwhhhhww = 48,whhhhwww = 48,hwwwwhhh = 48,hhwwwwhh = 48,hhhwwwwh = 48,wwhhwwhh = 24,wwhhhwwh = 24,whhwwwhh = 24,whhwwhhw = 24,whhhwwwh = 24,hwwwhhhw = 24,hwwhhwwh = 24,hwwhhhww = 24,hhwwwhhw = 24,hhwwhhww = 24] 5 = [wwwwwhhhhh = 2880,hhhhhwwwww = 2880,wwwwhhhhhw = 720,wwwhhhhhww = 720,wwhhhhhwww = 720,whhhhhwwww = 720,hwwwwwhhhh = 720,hhwwwwwhhh = 720,hhhwwwwwhh = 720,hhhhwwwwwh = 720,wwwhhwwhhh = 240,wwwhhhwwhh = 240,wwwhhhhwwh = 240,wwhhwwwhhh = 240,wwhhhwwwhh = 240,wwhhhhwwwh = 240,whhwwwwhhh = 240,whhhwwwwhh = 240,whhhhwwwwh = 240,hwwwwhhhhw = 240,hwwwhhhhww = 240,hwwhhhhwww = 240,hhwwwwhhhw = 240,hhwwwhhhww = 240,hhwwhhhwww = 240,hhhwwwwhhw = 240,hhhwwwhhww = 240,hhhwwhhwww = 240,wwhhwwhhhw = 120,wwhhhwwhhw = 120,whhwwwhhhw = 120,whhwwhhwwh = 120,whhwwhhhww = 120,whhhwwwhhw = 120,whhhwwhhww = 120,hwwwhhwwhh = 120,hwwwhhhwwh = 120,hwwhhwwwhh = 120,hwwhhwwhhw = 120,hwwhhhwwwh = 120,hhwwwhhwwh = 120,hhwwhhwwwh = 120] 6 = [wwwwwwhhhhhh = 86400,hhhhhhwwwwww = 86400,wwwwwhhhhhhw = 17280,wwwwhhhhhhww = 17280,wwwhhhhhhwww = 17280,wwhhhhhhwwww = 17280,whhhhhhwwwww = 17280,hwwwwwwhhhhh = 17280,hhwwwwwwhhhh = 17280,hhhwwwwwwhhh = 17280,hhhhwwwwwwhh = 17280,hhhhhwwwwwwh = 17280,wwwwhhwwhhhh = 4320,wwwwhhhwwhhh = 4320,wwwwhhhhwwhh = 4320,wwwwhhhhhwwh = 4320,wwwhhwwwhhhh = 4320,wwwhhhwwwhhh = 4320,wwwhhhhwwwhh = 4320,wwwhhhhhwwwh = 4320,wwhhwwwwhhhh = 4320,wwhhhwwwwhhh = 4320,wwhhhhwwwwhh = 4320,wwhhhhhwwwwh = 4320,whhwwwwwhhhh = 4320,whhhwwwwwhhh = 4320,whhhhwwwwwhh = 4320,whhhhhwwwwwh = 4320,hwwwwwhhhhhw = 4320,hwwwwhhhhhww = 4320,hwwwhhhhhwww = 4320,hwwhhhhhwwww = 4320,hhwwwwwhhhhw = 4320,hhwwwwhhhhww = 4320,hhwwwhhhhwww = 4320,hhwwhhhhwwww = 4320,hhhwwwwwhhhw = 4320,hhhwwwwhhhww = 4320,hhhwwwhhhwww = 4320,hhhwwhhhwwww = 4320,hhhhwwwwwhhw = 4320,hhhhwwwwhhww = 4320,hhhhwwwhhwww = 4320,hhhhwwhhwwww = 4320,wwwhhwwhhhhw = 1440,wwwhhhwwhhhw = 1440,wwwhhhhwwhhw = 1440,wwhhwwwhhhhw = 1440,wwhhwwhhhhww = 1440,wwhhhwwwhhhw = 1440,wwhhhwwhhhww = 1440,wwhhhhwwwhhw = 1440,wwhhhhwwhhww = 1440,whhwwwwhhhhw = 1440,whhwwwhhhhww = 1440,whhwwhhhhwww = 1440,whhhwwwwhhhw = 1440,whhhwwwhhhww = 1440,whhhwwhhhwww = 1440,whhhhwwwwhhw = 1440,whhhhwwwhhww = 1440,whhhhwwhhwww = 1440,hwwwwhhwwhhh = 1440,hwwwwhhhwwhh = 1440,hwwwwhhhhwwh = 1440,hwwwhhwwwhhh = 1440,hwwwhhhwwwhh = 1440,hwwwhhhhwwwh = 1440,hwwhhwwwwhhh = 1440,hwwhhhwwwwhh = 1440,hwwhhhhwwwwh = 1440,hhwwwwhhwwhh = 1440,hhwwwwhhhwwh = 1440,hhwwwhhwwwhh = 1440,hhwwwhhhwwwh = 1440,hhwwhhwwwwhh = 1440,hhwwhhhwwwwh = 1440,hhhwwwwhhwwh = 1440,hhhwwwhhwwwh = 1440,hhhwwhhwwwwh = 1440,wwhhwwhhwwhh = 720,wwhhwwhhhwwh = 720,wwhhhwwhhwwh = 720,whhwwwhhwwhh = 720,whhwwwhhhwwh = 720,whhwwhhwwwhh = 720,whhwwhhwwhhw = 720,whhwwhhhwwwh = 720,whhhwwwhhwwh = 720,whhhwwhhwwwh = 720,hwwwhhwwhhhw = 720,hwwwhhhwwhhw = 720,hwwhhwwwhhhw = 720,hwwhhwwhhwwh = 720,hwwhhwwhhhww = 720,hwwhhhwwwhhw = 720,hwwhhhwwhhww = 720,hhwwwhhwwhhw = 720,hhwwhhwwwhhw = 720,hhwwhhwwhhww = 720] */ go3 => garbage_collect(100_000_000), member(N,1..6), SymmetryBreaking = false, Sols = findall(Gender,row_seating(N, _M,_Couples,_X,Gender,SymmetryBreaking)), GenderStr = ['h','w'], Map = new_map(), foreach(Sol in Sols) Sol2 = [GenderStr[S] : S in Sol], Map.put(Sol2, Map.get(Sol2,0)+1) end, println(N=Map.to_list.sort_down(2)), fail, nl. couples(N) = [[2*(I-1)+1, 2*(I-1)+2] : I in 1..N]. row_seating(N,M,Couples, X,Gender) => row_seating(N,M,Couples, X,Gender,true). row_seating(N,M,Couples, X,Gender,SymmetryBreaking) => M = 2*N, Couples = couples(N), % the seating X = new_list(M), X :: 1..M, % the gender Gender = new_list(M), Gender :: 1..2, % ["h","w"] all_different(X), % The neighbours must be either % - of the same gender % - or the spouse foreach(I in 2..M) Gender[I] #= Gender[I-1] #\/ sum([ X[I] :: Couples[J] #/\ X[I-1] :: Couples[J] : J in 1..N]) #= 1 end, foreach(I in 1..M) Gender[I] #= 1+(X[I] mod 2) end, % symmetry breaking % Place the first person (one of the first couple) if SymmetryBreaking then X[1] #= 1 #\/ X[1] #= 2 end, Vars = X ++ Gender, solve(Vars).