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.

42 comments:

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

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

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

    ReplyDelete
  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?

    ReplyDelete
    Replies
    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.

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

      Delete
  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 ...")

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

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

    ReplyDelete
  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.

    ReplyDelete
  9. There is an error there...

    ReplyDelete
  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?

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

      Delete
    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.

      Delete
  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?

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

    ReplyDelete
  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?

    ReplyDelete
    Replies
    1. 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.

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

      Delete
    3. 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!

      Delete
  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?

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

      Delete
  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 :-)

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

    ReplyDelete
    Replies
    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 :-) )

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

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

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

    ReplyDelete
    Replies
    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.

      Delete
  18. where is a picture?

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

      Delete
  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

    ReplyDelete
    Replies
    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.

      Delete
  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.

    ReplyDelete
  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$.

    ReplyDelete
    Replies
    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?

      Delete
    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.

      Delete
    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.

      Delete
  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.

    ReplyDelete
  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?

    ReplyDelete
  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).

    ReplyDelete