## Wednesday, February 08, 2012

### The 17x17 problem SOLVED! (also 18x18)

THE 17x17 PROBLEM HAS BEEN SOLVED!!!!!

On Nov 30, 2009 I posted here the following challenge:
If someone emails me a 4-coloring of 17x17 with no monochromatic rectangles then I will give you \$289.00
Bernd Steinbach (Institute of Computer Science, Freiberg University of Mining and Technology, Freiberg (Saxony), Germany) and Christian Posthoff (retired from Department of Computing and Information Technology, The University of the West Indies, Trinidad and Tobago, but now in Germany) have found a 4-coloring of 17x17 without monochromatic rectangles!! The coloring is here. I have verified it (actually I asked Daniel Apon and Jim Purtilo to separately verify it, and they have. Also, Semmy Purewal and Brian Hayes did later.) The methods Steinbach and Posthoff used to obtain the coloring will appear in their paper
Most Complex Four-Colored Rectangle-free Grids - Solution of an Open Multiple-Valued Problem (ISMVL 2012. ISMVL stands for International Symposia on Multiple-Valued Logic). They will present this paper on May 14, 2012 during session B1 of ISMVL in Victoria, Canada.)
Once the paper appears there will be a post (with their help, perhaps guest posted by them) on the techniques they used.

Some thoughts:
1. Some very serious people had worked very hard on this. I actually began thinking that 17x17 is NOT 4-colorable.
2. CONGRATULATIONS to Bernd Steinbach and Christian Posthoff!
3. They also found a 4-coloring of 18x18.
4. The only grid that we do not know if it is 4-colorable is 12x21. This is still open and you are URGED to work on it. Sorry, no cash on this one. Do it for the glory!
5. If you are going to ISMVL 2012 then find Bernd and Christian and say hello. More important, talk to them about there work. (I won't be there alas.)
6. The reason I thought that 17x17 was 4-colorable is that there is a rectangle free subset of size 74, so I assumed that one of the colors would appear 74 times. WRONG- The max number of times a color appears is 73.
7. I thought that each color would appear 4 or 5 times in each row and column. WRONG- some appear 3 times in a row or column.
8. I am DELIGHTED to pay out the \$289.00.
9. I asked them if they did it for the money (which I doubted). No, but the money made them more aware of the problem.
10. How did they do it? I do not know, but I am looking forward to reading their paper in May when it is available and blogging about it.

#### 43 comments:

1. I am also very interested in their solution. I've also made assumption #7. Is it proven that no such coloring exists?

2. Martin- good question, I don't know.
(All I know is in the post).

3. This sort of reward-problem-via-blogging is wonderful! :)

4. Hi Bill, do you mean that it is known that both 11x21 and 12x20 can be 4-colored and both 13x21 and 12x22 cannot?

1. YES to all, see my paper or talk on my website, but here is summary
1) 11x21 IS 4-colorable. Brad Loren did this by CLEVER computer search.
2) 16x20 IS 4-colorable. This follows from theorems in my paper,
so its a nice coloring- not found by computer.
3) 13x21 NOT 4-colorable, by proof of course.
4) 11x22 NOT 4-colorable, by proof of course.

NONE of the non-colorable results have been by computer.
ALL have been by density- if nxm is c colorable then
there must be a rect free subset of size ceil(nm/c).
We have used the contrapositive to get non-c-colorable results.

2. Wrong use of "their"...just saying...

5. Great job ... the end of a nightmare !!!!
I'm very curious to see how they found the solution!

(P.S. the 17x17 solution proves that the following assumption in Beth's paper is not correct: "... Therefore, every legal coloring contains a 74, or a 73 that could be extended up to a 74 ...")

6. Another break-through?!
(Just kidding :)

7. Interesting! Scott seems more generous. At least, he's sure he has to pay nobody...

8. A basic remark.

Averaging 17x17 squares with colors chosen uniformly randomly among 1-4, I have the approximate typical distribution for numbers of "rectangles" with 1,2,3,4 colors

{294, 6102, 10375, 1725}

and the proposed solution has distribution

{ 0, 5615, 10358, 2523}

One might suspect that there is a large transfer
going from the monochromatic rectangles to the
4-color rectangles but that the distribution of 3-color
rectangles in the solution is close to typical.

By looking in more details to
the average joint-distribution between rectangle
dimensions and number of different colors, one
sees that something like this is going on. The 4-color
rectangle distribution of the solution is clearly different.

In the average distribution, there is a strong peak for
4 color rectangles of size 2x3 and all the distribution monotonically
decrease from there in all directions.

In the solution there are several separated peaks at
2 x3, 2 x5, 2 x9, 4 x5, 5 x8 for 4-color rectangles
and the size distribution is really not monotone in
general, where as the distribution for 2 and 3-color
rectangles is much closer to the average and does
not display such strong features.

9. There is an error there...

10. Marzio, I don't see why. Bill announced a coloring which doesn't contain a 74 but does contain a 73. If that 73 can beextended up to a 74, then Beth's assertion is still viable.Why do you think it can't be extended?

1. Simply: I checked it! (using the (great) STP solver tool that I used many times in these months ... now I can delete it) :-))

2. Okay, thanks! I looked at Beth's paper and if my calculations are correct (always in question since after 2 AM I start believing trapezoids are rectangles and other bizarre things) then her mistake can be pushed back to page 19 "If not, then one of
{O,P,Q} is in a group of 3". Each of the three occurrences of color 4 in row 6 of the coloring has a counterpart in the same column in a row with 5 occurrences of color 4.

11. I have verified it (actually I asked Daniel Apon and Jim Purtilo to separately verify it...)

Did they verify it by hand(!), or by computer?

12. Apon, Purtilo, Hayes verified by computer.
Gasarch, true to his math roots, verified by hand.
He then took a long nap.

13. Hi to everybody. I'm Valentino, an italian phd student on computer science.

I've just checked the correctness of the 17x17 file by using a little C program and it is ok!

Btw, I've a question for you. Are you aware of any use of evolutionary computation methods for this problem?

1. I am not aware of such.

2. I wrote a genetic algorithm to solve rectangle free grid coloring. It was written in java. It was effective at solving grid sizes up to about 14x14 where it would start to have trouble.

3. Very well !! Then where is this Java algorithm ? How could we get it ? Did you post it anywhere ??

4. I'm not sure anyone is still interested, but I posted my code for solving rectangle free grid coloring via evolutionary computation over on github. Here is a link to the code of interest:
https://github.com/PaulVaroutsos/Scripts-Algorithms-and-Other-Projects/tree/master/Rectangle%20Free%20Grid%20Coloring
(see the src/ec/app package)

Cheers!

14. Question: are monochromatic rectangles allowed to be degenerate?
In row 1 isn't there a rectangle of color 3 at indices 10,13,13,16:
index 13 ------------- index 16

index 10 ------------- index 13
Is it disqualified because two of its vertices are the same point?

1. A rectangle of 3 colors isn't monochromatic. A rectangle with only one color is.

2. what you mention is a degenerate parallelogram (and there are plenty non-degenerate parallelograms) but not a rectangle!

15. I thought about a different optimality criterion (but maybe it is not worthwhile):

Let a coloring be row-optimal for a given color C if:
For all columns j
for all rows x which contain this color in column j
Let I_j(C) be the set of indices k!= j in which
there is this color in at least one of these rows
(more than one is not possible)

If I_j(C) is the full set of indices minus j for all j, we call the coloring color-row-optimal. Define column-optimal analogously.
E.g., 4x4 can be colored row- and column-optimal for ONE color but not for two.

Maybe I'm reinventing a term you already used, I'm not sure. Let me know :-)

16. I looked at the answer. It was in black and white. Fail.

1. The posted answer used the colors 1,2,3,4.
Hence it was four colors.
It has been verified by several people.
(Plus I've already given them the \$289.00 so it has
to be correct :-) )

2. The anonymous user was probably hoping for something in color, like this.

3. A nice colored version can be found here:
http://www.spiegel.de/fotostrecke/fotostrecke-78910-3.html

17. Seriously.. I have no idea what are you guys talking about.. Anyone please enlighten me
thank

1. A while back I offered 289 dollars for someone who could email me
a 4-coloring of the 17x17 grid that has no mono rectangles.
This has now been done.

18. where is a picture?

1. @Gasarch: it seems that the anonymous posts here and above are not "human" :-)

19. Congratulations to Bernd Steinbach and Christian Posthoff on this excellent achievement! Even more amazing is that they got a colouring of 18x18.

Bill, just wondering, has anyone worked on this problem for more than four colours? From my initial attempts, I got a 23x23 colouring with 5 colours, 31x31 with 6 colours and 38x38 with 7 colours. Is this worth investigating further?

Cheers,
Dmitry Kamenetsky

1. In the paper (Fenner-Gasarch-Glover-Purewal) we have very general
theorems which can be used to get many 5-col and NON-5-col results.

I would be good to see what you can get from our theorems and then
see where the gaps are and go after those- in an attempt to get
the obstrction set.

Same for 6,7, etc.

20. The 17x17 solution by Steinbach and Posthoff can be easily extended to a 18x18 solution; this is a preview of the "18x18 gem" :

221334214132234431
242112334434113223
313444111432412322
412313234121441342
311123242344432213
133243144122123234
314242233214144131
431211132443234124
443342423123212113
122213441433342411
423432132314321412
424124143221333321
132124413334221144
141433343211214242
241224321343141332
332341322242311441
234431414241122313
344131221113423424

It will be very interesting to hear what they say about the "21x12 missing tile" in their paper.

21. This extension to 18x18 is correct. You are right; it is easy to extend our 17x17 solution to 18x18 because we created the 17x17 solution from a valid 18x18 solution cutting one row and one column. Knowing our 17x17 solution it remains a (SMALL) search space of \$4^35=1,180,591,620,717,411,303,424=1.118*10^21\$. This is significantly simpler than the whole (VERY LARGE) search space of \$4^324=1.168*10^195\$.

1. First of all my congratulations to you and Christian for solving the problem ... you succeeded in finding a needle in a bunch of universes :-D !!!

Can you tell something in advance about the technique used to solve it (with a post in this blog)? And what about the 21x12 grid?

2. Thank you for your congratulations.

Searching for a 4-colored 18x18 grid we utilized many approaches. We have been published already some of them (important intermediate steps). You can download these papers from my web page.

At this time we prepare the remaining approaches for well understandable papers. This takes some time besides of teaching. A couple of words on this blog are not enough for well comprehension.

The 12x21 problem seems to be simpler than 18x18. It must be evaluated ONLY \$4{252}=5.237*10^{151}\$ instead of \$4{324}=1.168*10^{195}\$ grid patterns. From our point of view, the 12x21 problem is even more difficult than the 18x18 problem. Our successful approach for 18x18 failed for 21x12. However, it is my pleasure to answer your question regarding 21x12. Together with Christian Posthoff I solved this last unknown 4-color grid problem.

THERE IS A 4-COLERED GRID OF THE SIZE 12x21!!!!

I will post this solution soon.

3. THE 12x21 PROBLEM HAS BEEN SOLVED!!!!!

In thoughts #4 of this blog has been written:

The only grid that we do not know if it is 4-colorable is 12x21. This is still open and you are URGED to work on it. Sorry, no cash on this one. Do it for the glory!

Commonly with Christian Posthoff I (Bernd Steinbach) have done this work.

One 4-colored grid of 12x21 is here:

1,1,3,1,4,2,1,1,1,3,4,3,2,4,2,3,2,4,3,4,2
2,3,4,4,1,4,3,1,2,4,2,3,1,1,4,2,2,4,1,3,3
4,2,2,3,2,1,1,3,4,3,1,4,4,2,1,2,3,4,1,3,2
1,2,1,3,4,1,4,4,3,1,3,2,4,1,4,3,2,1,2,2,3
4,4,3,4,1,2,4,2,1,1,4,2,3,3,1,2,3,2,4,1,3
3,2,4,3,3,1,3,1,2,2,4,1,4,3,2,1,4,2,3,1,4
2,3,4,2,2,1,4,2,1,3,3,4,1,3,2,4,1,3,2,4,1
2,3,4,1,3,3,2,4,4,1,1,1,1,4,3,3,3,2,4,2,2
4,3,2,2,1,2,1,3,3,2,2,1,3,4,4,4,1,1,3,2,4
2,4,3,1,4,4,3,3,4,2,3,2,2,2,3,4,4,1,1,1,1
4,1,1,3,1,2,2,4,2,4,1,3,3,2,3,1,4,3,2,4,1
3,2,3,1,4,3,2,2,3,4,2,4,2,1,1,1,1,3,4,3,4

Some thoughts:

1. It was even more complicate to find this 4-color 12x21 solution in comparison to our 4-color solution for the grid 18x18 (from which a sub-grid was posted as solution of the 17x17 problem).

2. We will publish our steps to find the 4-color 12x21 grid as soon as possible. However, this will take some time.

22. GREAT! NOW the obstruction set for 4-coloring is completely
known. I will revise my paper and post about it at some
later time.

23. interesting problem, indeed.
is that published solution of the 17x17 THE (only) solution, or is it one of some or many solutions?? any estimates here?
is there a systematic way to come from this solution to other solutions?

24. The 18x18 grid is 4-colorable, too; so - up to color permutations - there should be at least 18x18=324 distinct solutions for the 17x17 grid (delete one row and one column from the 18x18 solution).