Translate this page

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:

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 🔗

Solution in Go 🔗

For each person:

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:

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:

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:

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

Download my free ebook


Subscribe to my mailing list and get a free email course

* indicates required
Interests



Translate this page

Updated on 2024 Nov 20.

DISCLAIMER: This is not professional advice. The ideas and opinions presented here are my own, not necessarily those of my employer.