💼 The Perfect Seating Chart: Solving the Leadership Summit Problem in Go 🔗

Organizing a leadership summit or a large-scale networking event comes with a unique logistical headache: how do you maximize interactions among attendees?

If you have multiple rounds of table discussions, you want to ensure people are constantly meeting new faces. Ideally, no person should sit at the same table as someone they’ve already met in a previous round.

This challenge is a classic combinatorics puzzle (closely related to the Social Golfer Problem). In this post, we’ll explore a backtracking solution written in Go that can assign $N$ tables with $N$ people each, for a maximum of $(N + 1)$ rounds, without any duplicate pairings.

📑 Table of Contents 🔗

📐 The Mathematical Bound: Why (N + 1) Rounds? 🔗

Before diving into the code, let’s establish the absolute maximum number of rounds we can schedule before duplicate pairings become mathematically unavoidable.

The maximum number of rounds is $(N + 1)$.

The Proof: Imagine we have $N$ tables, and each table seats $N$ people. This gives us a total of $N \times N$ (or $N^2$) attendees.

Now, look at the event from the perspective of a single attendee, Person A.

1. In every round, Person A sits with $(N - 1)$ new people.
2. The total number of other people at the event for Person A to meet is $(N^2 - 1)$.
3. To find out how many rounds it takes for Person A to meet everyone exactly once, we divide the total available people by the number of people met per round:

After $(N + 1)$ rounds, everyone will have perfectly networked with everyone else.

🧠 The Algorithmic Strategy 🔗

To solve this efficiently, we can use a backtracking algorithm. However, to drastically reduce the search space and speed up the execution, we can hardcode the first two rounds using a neat trick:

1. Round 0 (Horizontal): Assign everyone in sequential order horizontally.
2. Round 1 (Vertical): Assign everyone in sequential order vertically.
3. Remaining Rounds: Use backtracking to assign each seat a valid permutation of the attendees, ensuring no seating rules are broken.

💻 Implementation in Go 🔗

To track the progress of our backtracking, we use a State struct that holds the current tables, rounds, and maps to track who has interacted with whom.

Here is the core logic broken down into three parts: the search loop, the conflict validation, and the state management.

🔍 1. The Backtracking Search 🔗

The solveImpl function recursively tries to assign a person to the next available seat. If a path results in a conflict, it backtracks (unset) and tries the next person.

func solveImpl(state *State) bool {
	if state.solved {
		return true
	}

	// For the first round, consider all people
	start := 0
	end := state.people

	// From the second round onwards, restrict the search space
	if len(state.res) > 0 {
		start = len(state.table) * state.tableSize
		end = start + state.tableSize
	}

	for person := start; person < end; person++ {
		if !valid(state, person) {
			continue // Skip if this assignment causes a conflict
		}
        
		set(state, person) // Assign the seat
		if solveImpl(state) {
			return true // Success!
		}
		unset(state, person) // Backtrack
	}
	
	return false
}

🛡️ 2. Conflict Validation 🔗

An assignment is invalid (a conflict occurs) if:

1. The person has already been assigned a seat in the current round.
2. The person has already sat with someone currently at the table in a previous round.

func valid(state *State, person int) bool {
	// Has this person already been seated in this round?
	if state.usedPerson[person] {
		return false
	}
	
	// Has this person sat with anyone currently at this table before?
	for _, there := range state.table {
		first := min(there, person)
		second := max(there, person)
		
		if state.usedPair[first][second] {
			return false
		}
	}
	
	return true
}

⚙️ 3. State Management (set and unset) 🔗

When we assign a person to a seat, we must update our state tracker. If a table fills up, we move to the next. If a round fills up, we move to the next round.

func set(state *State, person int) {
	state.usedPerson[person] = true
	
	// Mark this person as having paired with everyone currently at the table
	for _, there := range state.table {
		first := min(there, person)
		second := max(there, person)
		if _, ok := state.usedPair[first]; !ok {
			state.usedPair[first] = map[int]bool{}
		}
		state.usedPair[first][second] = true
	}
	
	state.table = append(state.table, person)
	
	// Move to next table if full
	if len(state.table) != state.tableSize {
		return
	}
	state.round = append(state.round, state.table)
	state.table = []int{}
	
	// Move to next round if all tables are full
	if len(state.round) != state.numTables {
		return
	}
	state.res = append(state.res, state.round)
	state.round = [][]int{}
	state.usedPeople = append(state.usedPeople, state.usedPerson)
	state.usedPerson = map[int]bool{}
	
	// Check if we are completely done
	if len(state.res) != state.numRounds {
		return
	}
	state.solved = true
}

The unset function is the exact inverse, carefully walking back the state when our recursive tree hits a dead end.

func unset(state *State, person int) {
	state.solved = false
	
	// If the current table is empty, step back to the previous table
	if len(state.table) == 0 {
		if len(state.round) == 0 {
			last := len(state.res) - 1
			state.round = state.res[last]
			state.res = state.res[:last]
			state.usedPerson = state.usedPeople[last]
			state.usedPeople = state.usedPeople[:last]
		}
		last := len(state.round) - 1
		state.table = state.round[last]
		state.round = state.round[:last]
	}
	
	// Remove the person from the table
	state.table = state.table[:len(state.table)-1]
	
	// Unmark pairings
	for _, there := range state.table {
		first := min(there, person)
		second := max(there, person)
		state.usedPair[first][second] = false
	}
	state.usedPerson[person] = false
}

📊 The Results 🔗

🔢 Example: 4 Tables, 4 People Each (5 Rounds) 🔗

Here is the output for a smaller $N=4$ summit. Notice how in Round 0, the numbers go sequentially across the tables, and in Round 1, they go sequentially down the previous tables.

round 0:
  table 0: 0  1  2  3
  table 1: 4  5  6  7
  table 2: 8  9  10 11
  table 3: 12 13 14 15

round 1:
  table 0: 0  4  8  12
  table 1: 1  5  9  13
  table 2: 2  6  10 14
  table 3: 3  7  11 15

round 2:
  table 0: 0  5  10 15
  table 1: 1  4  11 14
  table 2: 2  7  8  13
  table 3: 3  6  9  12

round 3:
  table 0: 0  6  11 13
  table 1: 1  7  10 12
  table 2: 2  4  9  15
  table 3: 3  5  8  14

round 4:
  table 0: 0  7  9  14
  table 1: 1  6  8  15
  table 2: 2  5  11 12
  table 3: 3  4  10 13

🚀 Scaling Up: 8 Tables, 8 People Each (9 Rounds) 🔗

Because we prune our search tree intelligently by pre-filling the first two rounds, the algorithm scales nicely to larger groups. Below is the solution for 64 attendees spread across 8 tables.

round 0:
  table 0: 0  1  2  3  4  5  6  7
  table 1: 8  9  10 11 12 13 14 15
  table 2: 16 17 18 19 20 21 22 23
  table 3: 24 25 26 27 28 29 30 31
  table 4: 32 33 34 35 36 37 38 39
  table 5: 40 41 42 43 44 45 46 47
  table 6: 48 49 50 51 52 53 54 55
  table 7: 56 57 58 59 60 61 62 63

round 1:
  table 0: 0  8  16 24 32 40 48 56
  table 1: 1  9  17 25 33 41 49 57
  table 2: 2  10 18 26 34 42 50 58
  table 3: 3  11 19 27 35 43 51 59
  table 4: 4  12 20 28 36 44 52 60
  table 5: 5  13 21 29 37 45 53 61
  table 6: 6  14 22 30 38 46 54 62
  table 7: 7  15 23 31 39 47 55 63

round 2:
  table 0: 0  9  18 27 36 45 54 63
  table 1: 1  8  19 26 37 44 55 62
  table 2: 2  11 16 25 38 47 52 61
  table 3: 3  10 17 24 39 46 53 60
  table 4: 4  13 22 31 32 41 50 59
  table 5: 5  12 23 30 33 40 51 58
  table 6: 6  15 20 29 34 43 48 57
  table 7: 7  14 21 28 35 42 49 56

round 3:
  table 0: 0  10 20 30 35 41 55 61
  table 1: 1  11 21 31 34 40 54 60
  table 2: 2  8  22 28 33 43 53 63
  table 3: 3  9  23 29 32 42 52 62
  table 4: 4  14 16 26 39 45 51 57
  table 5: 5  15 17 27 38 44 50 56
  table 6: 6  12 18 24 37 47 49 59
  table 7: 7  13 19 25 36 46 48 58

round 4:
  table 0: 0  11 22 29 39 44 49 58
  table 1: 1  10 23 28 38 45 48 59
  table 2: 2  9  20 31 37 46 51 56
  table 3: 3  8  21 30 36 47 50 57
  table 4: 4  15 18 25 35 40 53 62
  table 5: 5  14 19 24 34 41 52 63
  table 6: 6  13 16 27 33 42 55 60
  table 7: 7  12 17 26 32 43 54 61

round 5:
  table 0: 0  12 19 31 38 42 53 57
  table 1: 1  13 18 30 39 43 52 56
  table 2: 2  14 17 29 36 40 55 59
  table 3: 3  15 16 28 37 41 54 58
  table 4: 4  8  23 27 34 46 49 61
  table 5: 5  9  22 26 35 47 48 60
  table 6: 6  10 21 25 32 44 51 63
  table 7: 7  11 20 24 33 45 50 62

round 6:
  table 0: 0  13 17 28 34 47 51 62
  table 1: 1  12 16 29 35 46 50 63
  table 2: 2  15 19 30 32 45 49 60
  table 3: 3  14 18 31 33 44 48 61
  table 4: 4  9  21 24 38 43 55 58
  table 5: 5  8  20 25 39 42 54 59
  table 6: 6  11 23 26 36 41 53 56
  table 7: 7  10 22 27 37 40 52 57

round 7:
  table 0: 0  14 23 25 37 43 50 60
  table 1: 1  15 22 24 36 42 51 61
  table 2: 2  12 21 27 39 41 48 62
  table 3: 3  13 20 26 38 40 49 63
  table 4: 4  10 19 29 33 47 54 56
  table 5: 5  11 18 28 32 46 55 57
  table 6: 6  8  17 31 35 45 52 58
  table 7: 7  9  16 30 34 44 53 59

round 8:
  table 0: 0  15 21 26 33 46 52 59
  table 1: 1  14 20 27 32 47 53 58
  table 2: 2  13 23 24 35 44 54 57
  table 3: 3  12 22 25 34 45 55 56
  table 4: 4  11 17 30 37 42 48 63
  table 5: 5  10 16 31 36 43 49 62
  table 6: 6  9  19 28 39 40 50 61
  table 7: 7  8  18 29 38 41 51 60

Next time you need to host a networking event, skip the manual spreadsheets and let a backtracking algorithm do the heavy lifting for you!

Kaue's Way of Life

Get It Free