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.

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