Leadership Summit Table Assignment 🔗

For this year’s leadership summit we want to assign people to multiple rounds of table discussions maximizing interactions.

This post describes a backtracking solution in Go that can assign N tables with N people each for (N + 1) rounds of discussion without having any person sit in same table as any other person more than once.

You can try it here.

Table of Contents

Maximum number of rounds is (N + 1) 🔗

Proof:

• Say we have N tables with N people each, for a total of N * N people.
• Now think only about person A.
• Each round this person is sitting with (N - 1) people.
• After (N + 1) rounds, this person will have seated with all (N + 1) * (N - 1) = N * N - 1 people.

Example solution: 4 tables with 4 people each for 5 rounds 🔗

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

See also a bigger example at end of this post.

Solution description 🔗

• In first round, assign everyone in order horizontally
• In second round, assign everyone in order vertically
• In remaining rounds, assign to each seat index a permutation of same people as second round
  • Search for right permutations using backtracking

Solution in Go 🔗

For each person:

• check for conflict
• set next seat
• try to solve from there
• unset seat

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

  // only first round
  start := 0
  end := state.people

  // starting from second round
  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
    }
    set(state, person)
    if solveImpl(state) {
      return true
    }
    unset(state, person)
  }
  return false
}

Conflict if:

• same person assigned more than once in same round
• same pair of people assigned to same table on any round

func valid(state *State, person int) bool {
  if state.usedPerson[person] {
    return false
  }
  for _, there := range state.table {
    first := min(there, person)
    second := max(there, person)
    if state.usedPair[first][second] {
      return false
    }
  }
  return true
}

Assign a person to next seat:

• mark person as assigned
• mark other people in table as paired
• add person to table
• if table full, move to next table
• if all tables full, move to next round
• if all rounds done, mark as solved

func set(state *State, person int) {
  state.usedPerson[person] = true
  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)
  if len(state.table) != state.tableSize {
    return
  }
  state.round = append(state.round, state.table)
  state.table = []int{}
  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{}
  if len(state.res) != state.numRounds {
    return
  }
  state.solved = true
}

Unassign a person from last seat:

• mark as unsolved
• if table empty, move to previous table
  • if all tables empty, move to previous round
    • if all rounds empty, error
• remove person from table
• unmark people in same table as paired
• unmark person as assigned

func unset(state *State, person int) {
  state.solved = false
  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]
  }
  state.table = state.table[:len(state.table)-1]
  for _, there := range state.table {
    first := min(there, person)
    second := max(there, person)
    state.usedPair[first][second] = false
  }
  state.usedPerson[person] = false
}

Final solution: 8 tables with 8 people each for 9 rounds 🔗

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