I'm trying to find an algorithm to solve the seating chart problem. The goal is to place pepole at one (or multiple) tables such that the overall happiness is maximized.
Each seat has neighbors. A person on a seat can talk to persons on neighboring seats (note that these neighbors normally sit next to each other or on the opposite side of the table).
Example of a table with 4 seats on each side:
1 2 3 4 8 7 6 5
6 has neighbors 2, 3, 4, 5 and 7, 8 has neighbors 1, 2, 7
There's a matrix describing how well two persons get along with each other. This is a value between 0 and 9 (the relation value). Relations are symmetrical.
Example of a relation matrix with four people:
A B C D A 0 2 0 5 B 2 0 3 6 C 0 3 0 1 D 5 6 1 0
The happiness of a single person is the sum of the relation values of all neighboring persons.
How would you find a solution that maximizes the overall happiness?