in reply to Perl for Adjudication

Here is an exhaustive approach. This is rather like the N-queens problem that has been discussed here on PM a few times.

Here you probably want to solve for various sizes of the problem and save the tables for later use. If the event is mandating the number of players a school must bring, that would help.

Create a table containing each panel of each round. Each panel in the table contains a spot for every player in the event. In very simplistic progression load each panel in order, after each panel is loaded check for legality, if there is a conflict, back up, and try the next pattern in the progression. When you get to the last panel and have no conflicts you have a solution. Apparently you need only one per round.

This is a N-queens problem with one extra dimension. To simplify your problem for any particular case, solve for the next exact fit larger. That is if you have 100 players going into 21 panels add 5 dummy-players so your panels are all the same. (Dummy players so each school has the same number of players could help also.)

In the case above each panel could contain 5 player numbers. The progression for each panel could be:

0 0 0 0 0 1 0 0 0 0 1 2 0 0 0 1 2 3 0 0 1 2 3 4 0 1 2 3 4 5 # first possibly valid set, though having 1 2 3 4 6 # 1 2 3 be from the same school lets you 1 2 3 4 7 # quickly skip obviously invalid matchings ... # getting to something like 1 4 7 11 14 # <- fairly quickly ... 1 2 3 4 105 ... 1 2 3 104 105 ... 101 102 103 104 105 # last possible value
When a panel has reached its last value there is no point in backing into it -- all possiblities have been tried.

There are a lot of possibilities so look for efficiencies. Each round should not redo the work of the prior rounds but continue to solve from that position. Find the first and last non-self-conflict state for a panel for each round and eliminate checking some useless states.

Replies are listed 'Best First'.
Re: Re: Perl for Adjudication
by simonm (Vicar) on Sep 30, 2003 at 17:31 UTC
    I spent some time thinking along these lines, but the scale of the problem made me cautious -- with over 100 entries per event, there are a massive number of possible combinations. Even with a fair amount of optimization, we're probably talking about days, or at least hours, of computation to work through them...

    And given the real-world possibility that some teams may be added at the last minute or fail to show up on the day of the event, you'd probably need to pre-calculate the choices for different numbers of entries from different numbers of schools, which means repeating the above computation thousands or millions of times.

    Given those constraints, it seemed the best real-world solution for the OP would be an approximate, non-exhaustive one -- although I'm sure that the solution I posted above could be improved with further effort.