Seating Chart Optimization
I use an ILP. I hope there are better solutions available.

Let H be your $n\times n$ happiness matrix. I use $n^2$ 0-1-variables $uv_{ij}$ per edge $uv$ in the seating graph. $uv_{ij}$ is 1 if person $i$ sits at place $u$ and person $j$ sits at place $v$.

maximize $\sum_{uv\in E} h_{ij} \cdot uv_{ij}$
s.t.
$\sum_{i,j} uv_{ij}=1$ for all $uv$, each edge gets exactly one neighbor configuration
$\sum_{j} ux_{ij} = \sum_{j} uy_{ij}$ for all edges $ux$ $uy$ that share an endpoint and all i, if $i$ sits at $u$ according to $ux$, they must also sit at $u$ according to $uy$