Almost 20 years ago, in the warm summer of 1996, I was earning my money as a developer at a well-known software company east of Munich when a colleague excitedly reported a simple-sounding, but apparently difficult-to-solve, problem.

The principal of a school was confronted with the task of dividing nine teachers, 27 female students, and 18 male students into nine groups that would change in such a way that the students would sit in class with different teachers and different classmates each day. Each group was to consist of exactly one teacher, two boys, and three girls, and nine group classes were to take place in different classrooms each day, with each class taught by one of the nine teachers. For how many days could the school go ahead with lessons without the group compositions overlapping? Maybe five?

"Nothing easier than that!" my colleagues and I shouted immediately. We put our project on hold for a while and started to type the first programs on our workstations. Figure 1 shows the first attempt with a simple algorithm that populates nine groups with the same teachers, and not-yet allocated students, every day. It keeps a record of who has already been together with whom and simply takes the next student from the not-allocated pool if there is an overlap.

[...]