I asked this in the Theoretical Computer Science Stack Exchange, but someone told me this wasn’t theoretical enough, so I’m trying here.

I think I have a Hamilton path finding problem, with a twist. No one asked me to solve this, but I’m trying to do it anyway.

I’m rowing in a regatta tomorrow. There are about forty-two crews in the regatta. Each crew races twice. In each pair of races that a crew races in, the two crews are the same two crews, but they change lanes. So in their first race, A will go against B, and A will be in the inside lane and B will be in the outside lane. In the second race, it will still be A against B, but B will be in the inside lane and A will be in the outside lane. That part really isn’t important.

This is the first important part: there are 42 races. The number of possible orderings of the races is 42!, which is a pretty big number (more than the number of atoms in the human body or number of stars in the universe, but less than the number of atoms in the universe).

This is the second important part: some crews would like to share rowers (some rowers want to be on more than one crew). This is called “subbing” for “substitute rowing” (it arises because some crews have people going on vacation or whatever so they can’t fill the boat and they ask for help from other crews).

This is the third important part: You are not allowed to sub unless six races separate the races you want to participate in. I think this is the most critical piece of information.

How do I solve this, in other words, how do I find an ordering so the most number of crews get the substitute rowers that they want?

I considered mapping this to a Hamilton path finding type problem. I thought, why don’t we make a graph of V vertices, each vertex represents a race. The edges E represent desired subbing relationships. So if there’s an edge between vertices, that means there’s a rower who wants to row in both races. Then take the complement graph and find the Hamilton path in the complement graph. This doesn’t work however, because because finding a Hamilton path in such a graph will not guarantee six races of separation, even if it is available.

One hacky way to find an ordering seems to iterate over all the edges in the graph G that I described. For each edge, assign one vertex to a slot, and then assign the other vertex to the slot six slots away from it. Try to do this for all the edges. I’m not sure that’s optimal, however.

Thanks,

Ben

Here’s a link to a screenshot of our actual regatta schedule for tomorrow, for the first 21 of 42 races. https://imgur.com/a/SKP8rIM

An example issue has already arisen, I’m rowing for teams 33x and 2n in this screenshot, and I would like to row for 4n as well. But I can’t row for 4n because it is too close to my race with 2n.

Update: After thinking about this some more, I’m not sure Hamilton paths are the best way to describe this problem. But I would like some certainty that whatever algorithm I pick is optimal