

Join them; it only takes a minute:

Sign up
Join the Stack Overflow community to:
  1. Ask programming questions
  2. Answer and help your peers
  3. Get recognized for your expertise

This is based on an article I read about puzzles and interview questions asked by large software companies, but it has a twist...

General question:

What is an algorithm to seat people in a movie theater so that they sit directly beside their friends but not beside their enemies.

Technical question:

Given an N by M grid, fill the grid with N * M - 1 items. Each item has an association Boolean value for each of the other N * M - 2 items. In each row of N, items directly beside other items should have a positive association value for the other. Columns however do not matter, i.e. an item can be "enemies" with the item in front of it. Note: If item A has a positive association value for B, then that means B also has a positive association value for A. It works the same for negative association values. An item is guarenteed to have a positive association with atleast one other item. Also, you have access to all of the items and their association values before you start placing them in the grid.


I have been researching this problem and thinking about it since yesterday, from what I have found it reminds me of the bin packing problem with some added requirements. In some free time I attempted to implement it, but large groups of "enemies" were sitting next to each other. I am sure that most situations will have to have atleast one pair of enemies sitting next to each other, but my solution was far from optimal. It actually looked as if I had just randomized it.

As far as my implementation went, I made N = 10, M = 10, the number of items = 99, and had an array of size 99 for EACH item that had a randomized Boolean value that referred to the friendship of the corresponding item number. This means that each item had a friendship value that corresponded with their self as well, I just ignored that value.

I plan on trying to reimplement this again later and I will post the code. Can anyone figure out a "good" way to do this to minimize seating clashes between enemies?

share|improve this question
It reminds me of a placement algo for electonic components. I'd expect to make several stabs at it and then have some kind of judging algo to select the 'best' one. This is my general approach to 'placement' problems, which are well suited to iterative, computational solutions and not to direct numerical formula. – John Oct 21 '11 at 18:13
i think it is .. if andersk wants watch seat him either behind a pillar or behind somebody with large hat who refuses to take it off because its too cold. – Anders K. Oct 21 '11 at 18:16
So boring! It would be so much more exciting to seat people to maximize fights between enemies. – Peter Olson Oct 21 '11 at 18:27
It is definetly NP-Hard, so - an there is not known polynomial solution for this kind of problem, are you looking also for a proof for this? or are you aware of this fact and looking for solution within these bounds? what is your best solution at the moment? – amit Oct 21 '11 at 19:15
This question would probably find a better home in Mathematics or Comp Sci Theory, since it isn't really programming related. – Igby Largeman Oct 21 '11 at 20:45
up vote 9 down vote accepted

This problem is NP-Hard.
Define L={(G,n,m)|there is a legal seating for G in m×m matrix,(u,v) in E if u is friend of v} L is a formal definition of this problem as a language.

We will show Hamiltonian-Problem ≤ (p) 2-path ≤ (p) This-problem in 2 steps [Hamiltonian and 2-path defined below], and thus we conclude this problem is NP-Hard.

(1) We will show that finding two paths covering all vertices without using any vertex twice is NP-Hard [let's call such a path: 2-path and this problem as 2-path problem]
A reduction from Hamiltonian Path problem:

input: a graph G=(V,E)
Output: a graph G'=(V',E) where V' = V U {u₀}.


  • if G has Hamiltonian Path: v₁→v₂→...→vn, then G' has 2-path: v₁→v₂→...→vn,u₀
  • if G' has 2-path, since u₀ is isolated from the rest vertices, there is a path: v₁→...→vn, which is Hamiltonian in G.

Thus: G has Hamiltonian path 1 ⇔ G' has 2-path, and thus: 2-path problem is NP-Hard.

(2)We will now show that our problem [L] is also NP-Hard:
We will show a reduction from the 2-path problem, defined above.

input: a graph G=(V,E)
output: (G,|V|+1,1) [a long row with |V|+1 sits].


  • If G has 2-path, then we can seat the people, and use the 1 sit gap to use as a 'buffer' between the two paths, this will be a legal perfect seating since if v₁ is sitting next to v₂, then v₁ v₁→v₂ is in the path, and thus (v₁,v₂) is in E, so v₁,v₂ are friends.
  • If (G,|V|+1,1) is legal seat:[v₁,...,vk,buffer,vk+1,...,vn] , there is a 2-path in G, v₁→...→vk, vk+1→...→vn

Conclusion: This problem is NP-Hard, so there is not known polynomial solution for it.

Exponential solution: You might want to use backtracking solution: which is basically: create all subsets of E with size |V|-2 or less, check which is best.

static best <- infinity
  if |used| <= |V|-2:
     val <- evaluate(used)
     best <- min(best,val)
  if |used| == |V|-2: 
  for each edge e in E-used: //E without used 
     least_enemies(G,used + e)

in here we assume evaluate(used) gives the 'score' for this solution. if this solution is completely illegal [i.e. a vertex appear twice], evaluate(used)=infinity. an optimization can of course be made, trimming these cases. to get the actual sitting we can store the currently best solution.

(*)There are probably better solutions, this is just a simple possible solution to start with, the main aim in this answer is proving this problem is NP-Hard.

EDIT: simpler solution:
Create a graph G'=(V U { u₀ } ,E U {(u₀,v),(v,u₀) | for each v in V}) [u₀ is a junk vertex for the buffer] and a weight function for edges:

w((u,v)) = 1    u is friend of v
w((u,v)) = 2    u is an enemy v
w((u0,v)) = w ((v,u0)) = 0

Now you got yourself a classic TSP, which can be solved in O(|V|^2 * 2^|V|) using dynamic programming.

Note that this solution [using TSP] is for one lined theatre, but it might be a good lead to find a solution for the general case.

share|improve this answer

One algorithm used for large "search spaces" such as this is simulated annealing

share|improve this answer

Your Answer


