Best way to create draw with limitation

Question

I'm writing a program to automatically make the draw for a competition. There are four objects: Debate Judge School Team Each Debate has two teams and a judge. Each team participates in three debates.

With this, there are the following rules: 1) A team cannot face someone from their same school 2) A team cannot face another team from the same other school (As in if they play a team from a school once, they cannot play again against someone from that school) 3) A judge cannot come from the same school as a team they are judging.

So how would I create a draw? A draw looks like a table (I just need the data, but when you write it it looks like this) with a column for judges and then three other columns for each round of debates (the three debates each team participates in).

Right now I'm basically choosing a random team, finding an opposing team that hasn't played the school of the first team before and doesn't come from the same school and then finding a judge from neither of those schools. Then I do the same thing until I have all the debates. The problem is the program sometimes gets into ruts where there is no other team/judge that fits. A human would then shift things around and try to find a way to move other judges around to figure it out, but how can I do that with a program. If I run the program again it figures it out just because it's random which teams it chooses for what. Basically, I'm wondering what the best solution is to the problem?

Answer 1

Sounds like a good candidate for using the knapsack problem algorithm. You may want one of the multi-variant extensions (also listed in that Wikipedia reference), but ultimately it's the same algorithm. You could have a look at one of my recent answers for a very similar problem domain.

The bad news is that this is an NP-hard problem. Loose translation: you'll never find a perfect algorithm to solve the issue. However, if you're willing to use some "cheats" then you can generate an algorithm that will reliably complete. The cheats aren't that big of a deal in this case; you just need to constrain the starting parameters in order to allow the algorithm to converge upon a solution. And it's not like you need true randomness for setting up the draw, you just need to make sure the participants are able to compete against as wide of a range of other participants as reasonably possible.

Answer 2

I think you're close. The trick is to start with the first team ('first' can be defined any way you want, including random) and make a list of all the available other teams, in some order. Pair up the first team with the first of the available other teams. Now look make a list of the available judges (again in some order), and pick the first available judge.

Repeat the above for the next set. At some point you won't have any second team to pick, or you'll be out of judges. At that point you need to "backtrack" - unwind one of your previous decisions and move on to the next.

For example, when you select team A, your choices are (B and C). You select B and move on. Later you discover that B was an unfortunate choice, so you revisit that choice and select C instead.

The idea is called Depth First Search. It's a lot easier than the Wikipedia page makes it out to be.

I'd handle your challenge by assigning each team a random number then use that number for sorting them whenever I'm looking for the "next available" team or judge. That way you'd get your random pairings and a way to backtrack and unwind. (The goal is to correctly select the correct teams and judges in such an order that you get all the pairings you need, subject to the contest rules constraints).

The only time you use Random() is when you're setting up the data. The algorithm shouldn't use it.

Answer 3

As it's Saturday, and my thinker is currently broken, I'll take the lazy way out. Count iterations without a match found. If they get above an arbitrary number, dump your result set and start over.

It's a kludge fix, but it will address the never-ending rut issue.