Many members of the club disliked the lack of variety and togetherness at the club. Although the club still had 12 members, some members were threatening to quit because each schedule was so short and there were so few people around each table.

To satisfy their request, the club decided to seat themselves around a big table and create a longer schedule. The twelve members of the club seated themselves in a schedule such that during each block of 55 days, no person was between the same pair of people. How was the schedule constructed?

(Based on The Round Table)

(In reply to I have an algorithm which works, but... by Erik O.)

Erik,

There is a WHOLE LOT of complication in your simple-sounding statement:
"Tracing back is required when there are no views which fulfill then next seat's requirement."

The probability of coming to a "dead end" in this manner grows exponentially as the number of people in the problem goes up.  And while I'm sure a program CAN exhaustively search them, this isn't a particularly elegant solution, nor particularly well described (such as how far to trace back).

My only addition is that basically, the program would "branch" the search tree every time there is more than one view to choose, and then recurse the tree every time it found a dead end.  This may be exactly what you meant to say.

Posted by ThoughtProvoker on 2004-06-23 16:50:53