The pathalogical 2680 challenge

Andrew was sick today, so rather than taking him with us to Church this morning, Shauna had me stay home with him (I'm sure the parents of other nursery-age children would thank us if they knew of my selfless sacrifice to spare their children the germs ;-).

While perusing the rec.puzzles newsgroup this morning, I found the 2680 challenge posted by The Last Danish Pastry.

The question deals with this text file containing 2,680 lines. Each line lists five integers between 0 and 244. The question is whether it is possible to select just forty-nine lines from the file such that all 245 numbers between 0 and 244 are included in the result.

Now, a little bit of basic arithmetic shows that in picking 49 lines, which each contain five numbers, we'll end up with a total of 245 numbers (49 x 5 = 245). Since we need to have each of the 245 numbers included in our results, we obviously cannot ever repeat any number—each of the 49 lines selected must not share even so much as a single number with any of the other selected lines.

Just looking at the file there is obviously structure to it. I spent some time analyzing the frequency with which each of the numbers between 0 and 244 appears and discovered (independently) the same information that Patrick Hamlyn posted.

My algorithm (running in the background—and all the CPU crunching is heating up my lap!) goes like this:

• recursively select possible line combinations
• discard all lines that share a number in common with the selected lines
• backtrack as early as we can when:

1. run out of further lines to check (and haven't selected 49)
2. or, when we eliminate all the lines containing some number not already on a selected line (that would leave us with an unfillable gap)

The search space for a naive-recursion search is huge! What I'm not (yet) sure about, is whether my checks to backtrack early (avoiding persuing hopeless combinations to their ultimate depth) cuts the search space enough to make a solution practically feasible or not.

The fiendish detail to all this is that The Last Danish Pastry (the original poster) doesn't even know if a solution exists! So this could be a wild-goose chase completely.

—Michael A. Cleverly
Sunday, January 23, 2005 at 23:28

Comment