|Perl: the Markov chain saw|
Seven by seven farming puzzleby ambrus (Abbot)
|on Feb 03, 2010 at 21:30 UTC||Need Help??|
In 2007, I read the following task on an online puzzle site (exercise 5 here).
Cut a 6 times 6 chessboard to 18 black and 18 white squares. Assemble them to a 6 times 6 board in such a way that each row and column has 3 black and 3 white squares, every row is different, and every column is different. How many boards can you get this way? The rows and columns of the board are numbered, so boards that differ in rotation or flipping count as different.
As discussed on the J wiki, this puzzle is quite easy to solve with brute-force.
In 2008, we decided to post a larger variant of this puzzle on the first round of the Challenge24 contest. The (contest webpage has the full problem set downloadable, this is problem F.) The task was basically the following.
A seven by seven cell table has to be filled in such a way that each row and each column must have exactly two cells with a 0, two cells with a 1, and three cells with a 2 in them; no two rows can be exactly the same; and no two columns can be exactly the same. Given the contents of the first two rows, compute the number of ways the rest of the table can be filled.
With current computers, it's almost impossible to brute force this task by enumerating all possible solutions.
There is one simple observation that cuts down quite some time though.
However, brute forcing takes too much time even after knowing this trick. The first working perl program I wrote takes about twenty minutes on one input. Such a long running time would be unacceptable, as we want to give ten sample inputs, and the contestants would have five hours for the whole contest (reading the tasks, development, running the program, submitting the answer, all this for all eight tasks, with only three people in a team). I didn't despair though, for I already knew that that solution can be optimized a lot.
My final solution is more complicated and much faster: it runs on any one input in at most six seconds (that was back in 2008, computers are twice as fast now). That's fast enough, so we could post this problem. (In fact I was quite surprised on how much faster the program became.)
The remainder of this post explains how my solution works, and shows the code too. I've spoilered this in case you want to try to write a solution yourself.
Here follows the full code, with the inputs hardcoded in the DATA section. The code is a bit ugly, for I wrote it quick and dirty to simulate how a contestant could do it live in the contest.
There is one more notable point that surprised me when I found out during the preparations. This is that there are only fourteen (14) significantly different input data you can give in this problem. (This didn't help the contestants though, for we gave ten significantly different inputs, and this is the kind of contest where the contestants run their programs on their own computers and submit only the result.) There are thirteen possible outputs, for two of the inputs have an equal output for a reason unknown to me.
You may want to compute these fourteen inputs (pairs of two lines): this is much easier than solving the original problem. Here are them in canonical form in case you want to check.
Update: changed broken link from contest's old homepage to new homepage. Update 2015-11-26: fix typo.