I Used an Algorithm to Seat 900 People at a School Dinner. Here's What Happened

What started as a spreadsheet favour turned into a masterclass in real-world combinatorial optimisation.

When a school asked for help organising seating for their annual family dinner, the request sounded simple: “Can you look at this spreadsheet and figure out who sits where?”

The spreadsheet had 268 rows. Students had nominated up to three preferred dinner companions. Families had bought tickets: one ticket, one seat. Some students had submitted the form twice. Some names were spelled three different ways. And every table had to seat exactly 9, 10 or 11 people, no exceptions, across a venue with fewer than 94 tables.

Simple, right?

Why this is harder than it looks

This is not a seating chart problem. It is, formally, a combination of three classically difficult problems stacked on top of each other:

Each of these is NP-hard individually. Together, with messy real-world data, they become the kind of problem that operations research departments publish papers about. We had an afternoon.

Step 1Clean the mess first

Before any algorithm touches data, the data has to be trustworthy. Nine students had submitted the form more than once, sometimes with different choices. Names appeared in multiple casings: “Maya Fernandes-Lim” and “maya fernandes-lim” are the same person. Some students nominated peers who hadn't filled in the form at all.

Every duplicate was merged, combining all unique preference choices across submissions. Every name was normalised. Every cross-reference was validated. Only then did the actual problem begin.

Step 2Find the social groups

With 268 students each nominating up to three others, the nominations form a directed graph: arrows pointing from nominator to nominee. The goal was to find clusters of students who are socially connected, directly or transitively.

If A nominates B, and B nominates C, and C nominates D, all four belong together, even if A has never mentioned D.

This is a classic Union-Find problem, solved using a data structure called Disjoint Set Union (DSU) with path compression. Every nomination merges two nodes into the same cluster. Run it across all 268 students and their choices, and the graph resolves into 56 distinct social groups, ranging from a 21-member supergroup down to simple pairs, plus 32 students with no connections at all.

The algorithm runs in near-linear time. The hard part was trusting it when a 21-person group emerged that would need to be split across seven tables.

Step 3Pack the tables

Each social group now had a total ticket count. The constraint: fit those tickets into tables of exactly 9, 10 or 11 seats. No group crosses a table boundary. No table sits half-empty.

This is bin packing: provably NP-hard, meaning there is no known algorithm that guarantees the perfect solution in reasonable time for large inputs. For each group, the approach was exhaustive search within a bounded range: try all combinations of 9s, 10s and 11s that cover the group's total tickets, minimise the number of tables used, minimise empty seats.

The result: 90 tables, four under the venue ceiling of 94, with a handful of under-filled tables flagged for manual top-up from the unconnected group.

Step 4Honour the preferences

Groups were assigned to tables. Now the question was: within a group that spans multiple tables, who sits where?

A greedy preference-weighted algorithm scored each possible placement, giving higher weight to mutual nominations (A nominated B and B nominated A) than one-way ones, with a secondary score for table fill rate to avoid fragmentation. Each student was placed at the table that maximised their preference score given remaining capacity.

It is not globally optimal. A true Integer Linear Program (ILP) solver would find better solutions given enough compute time. But greedy with smart scoring is often 80–90% of optimal at a fraction of the cost, and in this case, the results bore that out.

The numbers

Of 200 students who made at least one nomination:

The 65 unsatisfied students were identified and listed explicitly, with notes on where their preferred companions landed. Most are one table away. A manual swap pass could push overall satisfaction above 75%.

Lessons learnt

1. Data quality is the real problem. The algorithm took minutes to write and seconds to run. Data cleaning took the most time and required the most judgement: how to handle duplicate submissions, how to resolve name mismatches, whether to trust a nomination that points to an unknown student. In production systems, this phase is perpetually underestimated and chronically underfunded. It shouldn't be.
2. Decomposition beats sophistication. The instinct when facing an NP-hard problem is to reach for a powerful solver. The better instinct is to ask whether the problem can be broken into smaller, tractable sub-problems. Separating group formation (Union-Find), table packing (bin packing) and seat assignment (greedy scoring) meant each stage was independently debuggable, explainable and replaceable. A monolithic ILP across all 268 students would have been harder to build, harder to explain, and not meaningfully better in outcome.
3. Define your satisfaction metric before you start, not after. “Everyone sits with someone they like” is not a metric. “Percentage of students seated with their first or second choice” is. Having a concrete, computable measure of success changed how the algorithm was designed; specifically, it made mutual nominations worth double the score of one-way nominations. Without the metric defined upfront, that weighting decision would have been arbitrary.
4. Structural constraints cap your ceiling, and that's fine. 67.5% satisfaction sounds like a B+. But the theoretical maximum here is not 100%. It is structurally lower, because some nominations point across groups, some groups are too large for a single table, and some students nominated the same person as their first and second choice. Knowing the ceiling matters as much as knowing the score.
5. Always surface the residual. The 65 unsatisfied students weren't just reported as a number. They were listed, with their choices and the tables those choices landed on. Making the failure cases explicit and actionable is what separates a useful optimisation from a black box. Organisers could pick up that list and make five targeted swaps to meaningfully improve the outcome.

What a productionised version would look like

This solution was built for a one-time event with a single spreadsheet. Scaling it into a reusable tool, for a school system, a conference organiser or a corporate events team, would require a few deliberate additions.

• A proper data intake layer. Replace the Google Form with a structured intake that enforces name matching against a pre-loaded student registry at submission time. This eliminates the single biggest source of manual work: resolving free-text names that refer to the same person. A fuzzy-match lookup at form submission, flagging ambiguous entries for confirmation, would reduce post-collection cleaning from hours to minutes.
• An ILP solver for within-group assignment. The greedy seat assignment works well but leaves satisfaction points on the table for larger groups. A mixed-integer linear program using an open-source solver like PuLP or Google OR-Tools would find globally optimal within-group assignments, likely pushing first or second choice satisfaction above 80% for the same inputs.
• An interactive swap interface. The output today is a spreadsheet with flagged rows. A lightweight web interface, showing each table's current occupants, their unmet preferences and suggested swaps, would let an organiser make final adjustments in minutes rather than manually cross-referencing Excel sheets. The swap engine itself is simple: for each unsatisfied student, find a same-group student on an adjacent table whose swap would increase net satisfaction without breaking capacity constraints.
• A satisfaction simulation mode. Before the event, run the algorithm across historical preference data to benchmark expected satisfaction rates. This gives organisers realistic expectations and surfaces structural issues, like groups that are simply too large for a single table, early enough to act on them, for example by increasing table capacity or splitting the group intentionally.
• Audit logging and reproducibility. In any operational context, the output needs to be reproducible and auditable. Every allocation decision (group assignments, table packing choices, seat assignments) should be logged with the input state that produced it, so that re-runs after late ticket changes don't silently produce a different seating plan.

The core algorithms don't change. What productionisation adds is the scaffolding that makes a one-afternoon solution trustworthy enough to run every year, by someone who wasn't in the room when it was built.

What this is really about

No school administrator thinks of their dinner as a graph partitioning problem. No parent filling in a Google Form thinks of their three nominations as directed edges in a combinatorial structure. But that is exactly what they are, and treating them that way is what turns a messy spreadsheet into a defensible, explainable, optimised seating plan in a single afternoon.

This is what applied AI and data science actually looks like in practice. Not a neural network. Not a GPU cluster. A well-decomposed problem, the right classical algorithms, and enough care to clean the data before touching it.

Built with Python (pandas, openpyxl), Union-Find, greedy bin packing and preference-weighted graph assignment. Part of my school volunteering during my career break. Read the full story →