💼 El plano de asientos perfecto: resolviendo el problema de la cumbre de liderazgo en Go 🔗

Organizar una cumbre de liderazgo o un evento de networking a gran escala conlleva un quebradero de cabeza logístico único: ¿cómo maximizar las interacciones entre los asistentes?

Si tienes múltiples rondas de debates en mesas, querrás asegurarte de que los participantes conozcan caras nuevas constantemente. Idealmente, ninguna persona debería sentarse en la misma mesa con alguien a quien ya haya conocido en una ronda anterior.

Este desafío es un clásico rompecabezas de combinatoria (estrechamente relacionado con el problema del golfista social). En este artículo, exploraremos una solución de vuelta atrás (backtracking) escrita en Go capaz de asignar $N$ mesas con $N$ personas cada una, durante un máximo de $(N + 1)$ rondas, sin repetir ningún emparejamiento.

📑 Tabla de Contenidos 🔗

📐 El límite matemático: ¿por qué (N + 1) rondas? 🔗

Antes de sumergirnos en el código, establezcamos el número máximo absoluto de rondas que podemos programar antes de que los emparejamientos duplicados se vuelvan matemáticamente inevitables.

El número máximo de rondas es $(N + 1)$.

La demostración: Imaginemos que tenemos $N$ mesas y en cada mesa se sientan $N$ personas. Esto nos da un total de $N \times N$ (o $N^2$) asistentes.

Ahora, observemos el evento desde la perspectiva de un único asistente, la Persona A.

1. En cada ronda, la Persona A se sienta con $(N - 1)$ personas nuevas.
2. El número total de otras personas en el evento a las que la Persona A puede conocer es $(N^2 - 1)$.
3. Para averiguar cuántas rondas hacen falta para que la Persona A conozca a todo el mundo exactamente una vez, dividimos el total de personas disponibles entre el número de personas que conoce por ronda:

Tras $(N + 1)$ rondas, todos habrán interactuado perfectamente con todos los demás.

🧠 La estrategia algorítmica 🔗

Para resolver esto de manera eficiente, podemos utilizar un algoritmo de backtracking. Sin embargo, para reducir drásticamente el espacio de búsqueda y acelerar la ejecución, podemos fijar las dos primeras rondas mediante un truco muy práctico:

1. Ronda 0 (Horizontal): Asignar a todos en orden secuencial horizontalmente.
2. Ronda 1 (Vertical): Asignar a todos en orden secuencial verticalmente.
3. Rondas restantes: Usar backtracking para asignar a cada asiento una permutación válida de los asistentes, garantizando que no se incumpla ninguna regla de asignación.

💻 Implementación en Go 🔗

Para hacer un seguimiento del progreso de nuestro backtracking, utilizamos una estructura State que almacena las mesas actuales, las rondas y mapas para registrar quién ha interactuado con quién.

Aquí está la lógica principal dividida en tres partes: el bucle de búsqueda, la validación de conflictos y la gestión del estado.

🔍 1. La búsqueda con backtracking 🔗

La función solveImpl intenta asignar recursivamente a una persona al siguiente asiento disponible. Si un camino provoca un conflicto, retrocede (unset) y prueba con la siguiente persona.

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. Validación de conflictos 🔗

Una asignación no es válida (se produce un conflicto) si:

1. La persona ya ha sido asignada a un asiento en la ronda actual.
2. La persona ya se ha sentado en una ronda anterior con alguien que está actualmente en la mesa.

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. Gestión del estado (set y unset) 🔗

Cuando asignamos una persona a un asiento, debemos actualizar nuestro registro de estado. Si una mesa se llena, pasamos a la siguiente. Si se completan todas las mesas de una ronda, pasamos a la siguiente ronda.

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
}

La función unset es exactamente la inversa: deshace cuidadosamente el estado paso a paso cuando nuestro árbol recursivo llega a un callejón sin salida.

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
}

📊 Los resultados 🔗

🔢 Ejemplo: 4 mesas, 4 personas por mesa (5 rondas) 🔗

Aquí tienes el resultado para una cumbre pequeña con $N=4$. Observa cómo en la Ronda 0 los números avanzan secuencialmente a lo largo de las mesas, y en la Ronda 1 avanzan secuencialmente hacia abajo respecto a las mesas anteriores.

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

🚀 Escalando: 8 mesas, 8 personas por mesa (9 rondas) 🔗

Dado que podamos nuestro árbol de búsqueda de forma inteligente rellenando previamente las dos primeras rondas, el algoritmo escala muy bien para grupos más grandes. A continuación se muestra la solución para 64 asistentes distribuidos en 8 mesas.

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

La próxima vez que tengas que organizar un evento de networking, olvídate de las hojas de cálculo manuales y deja que un algoritmo de backtracking haga el trabajo pesado por ti.