# Seat guests based on prioritized parameters

The following data model represents tables with seats and guests, in an application that lets a user create tables and seats, visually using HTML5. // The data model var data = { guests: [], // id, name, tags tables: [], // id, seats seats: [], // id, guest tags: [] // id, name }; The guests have tags (kind of categories) attached to them. These tags can be prioritized and set to work as "grouping" or "ungrouping" parameters. The user then clicks "Seat", and the guests are seated (seemingly randomly), while the prioritized parameters are respected. Full-blown example: http://jsfiddle.net/kBp49/2/ (look for "SOLUTION GOES HERE" in JS panel) **The question is:** How do I implement a function that seats the guests to the tables, while taking into consideration that some guests should be seated next to each other and others should be seated apart from each other in order to create one of the best seaating configurations? The number of guests can exceed 1000 but not 2000. Real life example, to clarify the problem ---------------------------------------- Let's say we have 3 tables. They have 4 seats each. Let's also say that we have 9 guests to fill these tables with. They are as follows: 1. Guest 1, Jewish, from US 2. Guest 2, Jewish, from UK 3. Guest 3, Christian, from US 4. Guest 4, Christian, from UK 5. Guest 5, Christian, from Sweden 6. Guest 6, Atheist, from UK 7. Guest 7, Atheist, from Sweden 8. Guest 8, Muslim, from Saudi Arabia 9. Guest 9, Muslim, from UK Now, the user prioritizes the parameters like this. First is most important. 1. I want those with the same religion to sit apart from each other 2. I want those with the same geographical location to sit next to each other This is OK: 1. Table 1: Guests: 1, 3, 7, 8 2. Table 2: Guests: 2, 4, 6, 9 3. Table 3: Guests: 5 **Update** One solution could be the Minimax algorithm. It would calculate a score for each possibility and present the best found solution (found after, say 10 seconds of calculation). The algorithm is what I need help with, the implementation itself will of course require decisions that only I can make.
I've removed that detail. Please note also that the solution will be applied to around 1000 seats, so the algorithm cannot be way too slow (but a couple of seconds for 1000 seats is okay, I can implement a progress bar)