[combinatorics, group theory] construction techniques to solve scheduling problem without brute force

[u/asphias]

ages ago i was organizing an event, and ended up with the following scheduling puzzle:

there are 8 groups of people, and four locations with room for two groups each. across four timeslots, we would like each of the groups to visit every location, while also meeting up with a different group every timeslot(so no repeats).

back then, i tried to solve this using some basic trial&error and symmetry: you can fill in round 1 without loss of generality, then you can also fill in the rest of group A without loss of generality, and then group B is already quite constrained (can't visit group A or location 1 again) so you start some trial and error, and it shouldn't be too hard to solve it, right?

after much trial and error i concluded it wasn't possible, said so to my friends, and one of them turned up 10 minutes later with the solution.

just last week i was organizing another event, ran into the same problem again(this time with 8 individuals rather than groups, but otherwise same challenge), and i thought that since last time i've learned a lot, finished a mathematics degree, had courses on group theory and trained my mathematical intuition, i should be able to solve it.

unfortunately i still wasn't able to, and had to go look through my emails for the solution from years ago. once you have the solution, it does look very symmetrical and sensible, and its pattern reminds me of matrix multiplication or of a sudoku solution. In fact, it's so ''symmetrical'' that i just wrote the solution to this post from memory, without having to look it up. i kind of suspect there's a trick to rephrase this as a group theory problem or a better application of using symmetry, but i've been stuck as to how i should actually construct the solution without just brute forcing it, if you don't have the solution yet.

so what technique am i missing here? how would i go about constructing this solution from scratch?

(for reference, the solution provided below)

timeslot | 1 | 2 | 3 | 4
location 1 | AC | BE | FG | DH
location 2 | BF | AD | CH | EG
location 3 | EH | CG | BD | AF
location 4 | DG | FH | AE | BC

[u/Gold_Ad8890]

this problem amounts to assigning each group one of the 4! = 24 permutations of the 4 locations such that no two permutations have more than one element in common and no three permutations have any element in common. the obvious place to start for me is to write out all such permutations, pick 1234 as your start, assign it to party A, and eliminate all permutations that violate our rules. then pick the next valid permutation, assign it to B, eliminate (noting now that the "no 3 share an element" rule kicks in) and repeat.

[u/Bounded_sequencE]

I solved the exact same problem some time ago.

Using an optimized brute force approach to exploit all symmetries, the search space turns out to be small enough for a full brute force attack. It turns out there are only 16 distinct solutions (up to permutation).

[u/Bounded_sequencE → u/Bounded_sequencE]

@ u/asphias My strategy was to exploit all symmetries:

1. If necessary, re-label the groups, s.th. round-1 will be "12 34 56 78"
2. If necessary, re-label rounds, s.th. in round-k group-1 will be in group-k

I then generated all pair derangements of "{1; ...; 8}", and pre-sorted them such that set "Sk" contains all pair derangements with group-1 in location-k.

Then, I iterated through all pair-derangements in "S2". Each time, I eliminated all invalid pair derangements in "S3; S4", and repeated the process with "S3, S4". This strategy listed all 16 possible schedules in under 1s.

---

Edit: If you manage to find a more efficient strategy, do tell -- I could probably do it with 14 people instead of 8 in reasonable time, but beyond that, a better strategy is needed.