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)

Just to give some idea of the complexity here

Solution to 7 - 0 seconds
Solution to 8 - 59 seconds
Solution to 9 - 16.7 hours

running on a 2.8GHz Pentium 4. With the current algorithm for 10, I expect things will take months :(

Oh well, here is the solution anyway in case you want to compare with Rajal's or look for a pattern

Problem size: 9
Sizeof Pairing: 32
Arc list size: 4320
Size of a Seating: 32
Elements in search space: 20160
Size of search space: 645120
Solution found!!!
A B C D E F G H I
HI EF GI EH BD BG CF AD AC 
GI EI FG FH BH CD AC DE AB 
GH CF BH EI DG BI AE AC DF 
FI CG BD CI FH AE BH EG AD 
FH CD BI BF GH AD EI AE CG 
FG DH EI BG CH AI AD BE CF 
EI FH EG FG AC BD CD BI AH 
EH CI BF EG AD CG DF AI BH 
EG DG FH BI AF CE AB CI DH 
EF EH FI GI AB AC DH BG CD 
DI GH EF AG CI CH BD BF AE 
DH CH BG AF GI DI CE AB EF 
DG DF HI AB FI BE AH CG CE 
DF FI GH AE DH AB CI CE BG 
DE FG DH AC AI BH BI CF EG 
CI DE AG BH BF EI CH DG AF 
CH GI AE FI CG DH BE AF BD 
CG DI AD BC HI GH AF EF BE 
CF EG AH HI BI AG BF CD DE 
CE HI AF GH AG CI DE BD BF 
CD CE AB AH BG GI EF DI FH 
BI AH EH EF CD DG FI BC AG 
BH AI DI CF FG DE EH AG BC 
BG AE DE CH BC HI AI DF FG 
BF AG DG CE DI AH BC FI EH 
BE AF DF CG AH BC DI EI GH 
BD AC BE AI CF EH HI FG DG 
BC AD AI BE DF EG FH GI CH 
Solve completed after 60326 seconds

Posted by Glorat on 2004-09-21 03:33:43