This just in from Bill Gasarch: The quest for a rectangle-free four-coloring of the 17-by-17 grid is over. If you don’t know what that’s all about, and you’d like to find out, see Bill’s blog post from 2009 or my earlier comments (one, two, three).
The coloring above (along with several others) was found by Bernd Steinbach of Frieburg University and Christian Posthoff of the University of the West Indies. They win the $289 prize that Gasarch had offered for a solution.
Gasarch has posted more details on the Computational Complexity blog. But apparently we’re going to have to wait until May to learn how the coloring was found. The one interesting clue revealed so far is that the paper will be presented at the International Symposia on Multiple-Valued Logic.
Addendum 2012-02-11: For the benefit of those who don’t read the comments, I repeat a remark from reader Craig:
What I don’t like about this solution (or, indeed, the solutions to other related problems) is the arbitrariness. Is it not the case that you should be able to permute the rows and columns of any solution and arrive at a new solution? That being the case, I feel that you should be able to adjust the rows and columns here in order to highlight some kind of revealing pattern in the colouring.
Indeed, the matrix of dots shown above is one of (17!)2 equivalent solutions. How should we choose one of those permutations to serve as a representative of the class?
Personally, I’m not optimistic about finding a “revealing pattern” in any of the 126513546505547170185216000000 permuted matrices. If there were some simple, concisely described rule governing the arrangement of the dots—other than the no-monochrome-rectangle criterion itself—then we could make use of that rule to find a solution, or at least to reduce the search space. When Steinbach and Posthoff reveal their secret method, maybe we’ll learn that such a rule exists, but I doubt it.
Even if we can’t make a pretty picture by permuting rows and columns, it would still be useful to have some canonical ordering, so that we could easily determine whether two arrays are members of the same equivalence class. I’m not sure how best to do that, but if we assign an ordering to the colors, we can at least sort them.
There is still some arbitrariness here. We have not dealt with the 4! orderings of the colors. Is there a smarter way to go about it?
Congratulations on finding it!
What I don’t like about this solution (or, indeed, the solutions to other related problems) is the arbitrariness. Is it not the case that you should be able to permute the rows and columns of any solution and arrive at a new solution? That being the case, I feel that you should be able to adjust the rows and columns here in order to highlight some kind of revealing pattern in the colouring.
I anticipate that the method is based on the authors’ research found in “THE SOLUTION OF DISCRETE CONSTRAINT PROBLEMS
USING BOOLEAN MODELS” and “New Results Based on Boolean Models”
See also “The Solution of SAT Problems Using Ternary Vectors and Parallel Processing”
… and another paper, “Parallel Solution of Covering Problems Super-Linear Speedup on a Small Set of Cores” which includes “One popular challenging problem is, for instance, the distribution of the colors in such a way that there is no rectangle of any size where the four rectangles show the same color.”
In the paper “APPROACHES TO SHIFT THE COMPLEXITY LIMITATIONS OF BOOLEAN PROBLEMS” the 12 x 16 grid is solved in about 7 minutes. In contrast, a SAT solver takes about 3 seconds.