Monday, November 30, 2009

The 17x17 challenge. Worth $289.00. This is not a joke.

The 17x17 challenge: worth $289.00. I am not kidding.

Definition: The n x m grid is c-colorable if there is a way to c-color the vertices of the n x m grid so that there is no rectangle with all four corners the same color. (The rectangles I care about have the sides parallel to the x and y axis.)

The 17x17 challenge: The first person to email me a 4-coloring of 17x17 in LaTeX will win $289.00. (I have a LaTeX template below.)

UPDATE: THE RESULTS ABOUT OBS4 HAVE CHANGED SINCE THE ORIGINAL POST SINCE BRAD LARSON EMAILED ME A 4-COL OF 21x10 and 21x11. UPDATE: BRAD LARSON EMAILED ME A 4-COL OF 22x10.

UPDATE- PROBLEM WAS SOLVED. See my arXiv paper on grid colorings OR
my Feb 8, 2012 post.

Why 17x17? Are there other grids I care about? We (We=Stephen Fenner and Charles Glover and Semmy Purewal) will soon be submitting a PAPER (see TALK for a superset of the slide-talk I've given on this paper) on coloring grids. Here are the results and comments:
  1. For all c there is a finite set of grids a1xb1, ..., akxbk such that a grid is c-colorable iff it does not contain any of the aixbi (n x m contains a x b if a &le n and b &le m). We call this set of grids OBSc (OBS for Obstruction Set).
  2. OBS2 = {3x7, 5x5, 7x3}
  3. OBS3 = {19x4, 16x5, 13x7, 11x10, 10x11, 7x13, 5x16, 4x19}
  4. OBS4 contains 41x5, 31x6, 29x7, 25x9, 23x10, 10x23, 9x25, 7x29, 6x31, 5x41
  5. Exactly one of the following sets is in OBS4: 21x13, 21x12.
  6. Exactly one of the following sets is in OBS4: 19x17, 18x17, 17x17.
  7. If 19x17 is in OBS4 then 18x18 might be in OBS4 . If 19x17 is not in OBS4 then 18x18 is not in OBS4 .
  8. A chart of what we do and do not know about 4-colorings of grids is here.
  9. A Rectangle Free Subset of a x b is a subset of a x b that has no rectangles. Note that if a x b is 4-colorable then there must be a rectangle free subset of a x b of size Ceil(ab/4). We actually have a rectangle free subset of 17x17 of size Ceil(289/4)+1. Hence we think it is 4-colorable. For the rectangle-free subset see here. For the original LaTeX (which you can use for a template when you submit yours) see here. THIS IS WHY I AM FOCUSING ON 17x17--- BECAUSE I REALLY REALLY THINK THAT IT IS 4-COLORABLE. I could still be wrong.


What if 17x17 is not 4-colorable? Then nobody will collect the $289.00. Even so, if you find this out I would very much like to hear about it. I don't want to offer money for that since if your proof is a computer proof that I can't verify then its not clear how I can verify it. I also don't want to offer money for a reasonable proof since this may lead to having the Supreme Court decide what is a reasonable proof.

Can I get a paper out of this? FACT: If you get me the coloring and want to use it in a publication then that is fine. OPINION: It would not be worth publishing unless you get all of OBS4. See next question.

What do you hope to get out of this? My most optimistic scenario is that someone solves the 17x17 problem and that the math or software that they use can be used to crack the entire OBS4 problem. If this happens and my paper has not been accepted yet then we could talk about a merge, though this is tentative on both ends.

Has there been any work done on this problem that is not in your paper?
  1. A Rutgers grad student named Beth Kupkin has worked on the problem: here.
  2. A high school student (member of my VDW gang) Rohan Puttagunta has obtained a 4-coloring of 17x17 EXCEPT for one square: here.
  3. SAT-solvers and IP-programs have been used but have not worked--- however, I don't think they were tried that seriously.
  4. Here are some thoughts I have had on the problem lately: here.
  5. There is a paper on the 3-d version of this problem: here.


Is Lance involved with this at all? When I gave a talk on grid colorings at Northwestern, Lance fell asleep.

157 comments:

  1. Here is a quick approach, I am not able to pin down why it would not work.

    Since OBS3 = {19x4, 16x5, 13x7, 11x10, 10x11, 7x13, 5x16, 4x19}, I suppose a 8x8 grid is 3-colorable.

    I think of the 17x17 grid as split into 4 8x8 grids (build them from the 4 corners) and there's the remaining cross (intersecting right in the middle).

    Suppose I have a 3 coloring, let me call it C. Apply C on the top-left and bottom-right sub-grids, and a suitable of C[*] on the remaining two. I color the "cross" with the fourth color.

    [*] A variation of C that might work is the following: suppose C used the colors black, white and gray. The variant of C is obtained by swapping black and white, and leaving gray as is. If I'm not mistaken, this is a valid coloring?


    The fourth color doesn't create monochoromatic rectangles. There are no problems within the four grids. Only potential problem is with rectangles going across, but my intuition is that the swapping will take care of it.

    Does this make any sense?

    ReplyDelete
  2. Whoops, sorry - there is definitely a problem with gray rectangles, and presumably with other cross-over rectangles too. Whew, I think I need a concrete 3-coloring before I go down this particular route.

    The intuition was be to try and "mirror" the 8x8 colorings across and exploit the fact that they were proper colorings to begin with, but perhaps this is not quite correct. Yikes :)

    ReplyDelete
  3. Results #9,#10,#11 are in conflict.

    The chart in #11 marks 19x17 as Non-4-colorable and 18x18 as Unknown.

    But #10 suggests that one of those letters is wrong. Also, that would imply that #9 could be simplified to just being 17x18 or 17x17.

    Which is right? The chart does make a visually compelling argument that it should be 17x17.

    ReplyDelete
  4. Unless I misunderstand this was proven in 1976 - http://en.wikipedia.org/wiki/Four_color_theorem

    ReplyDelete
  5. @Bruce:

    The 4-color theorem refers to unique colors in adjacent regions. c-colorable configurations refers to corners on rectangles.

    Note that the 17x16 clearly 4-colorable under Bill's definition (i.e., in the txt file example by the high school student you can simply delete the last row).

    ReplyDelete
  6. SKY: I don't see what the
    problem is. Please elaborate so I can fix it
    or clarify it.

    19x17 is NOT 4-colorable.

    17x17, 17x18, 18x17, 18x18
    are NOT known.

    To be in the OBS_4 a grid
    has to NOT be 4-colorable
    and have every proper subgrid BE 4-colorable.

    ReplyDelete
  7. Okay, I want to pursue the first approach I outlined just a little bit longer.

    Let X be a 3-coloring of a 8x8 grid. Suppose the colors used are black, white and gray. Let Y be the coloring obtained from X by making all black nodes white, white nodes gray, and gray nodes black (a permutation, after all). It's clear that Y is also a 3-coloring.

    Let the 4 8x8 sub-grids of the 17x17 grid (each obtained by starting at a corner and expanding inwards) have the names A,B,C,D in clockwise order (A == top left, and so on).

    I color A and D with X and B and C with Y. And everything that's leftover is colored red (the fourth color).


    It's clear that rectangles formed with vertices of the "cross", the red ones, are never monochromatic. Rectangles sitting inside A,B,C,D are also not monochromatic. So we worry about those that lie in, say, A and B. The left column of the rectangle is in A and the right column is in B. Clearly, if both columns of the rectangle identified are the i^th columns in their respective 8x8 grids (for the same i), then because of the change in coloring, it cannot be monochromatic. If it's the i^th and j^th column in their respective grids, i different from j, it still cannot be monochromatic, because if it was, look at the i^th and j^th columns *inside one of the grids* and note that that would have been monochromatic.

    A similar argument takes care of rectangles across B and D, C and D and A and C. Luckily, we don't have to worry about A and D and C and B.

    Now we look at rectangles with one endpoint in each of A, B, C and D. Here, treat "A and C" as one large properly colored unit and "B and D" as a large properly colored unit and repeat the argument above.


    Does this make a little more sense than before?

    ReplyDelete
  8. @Neel, your approach would easily imply that 16x16 is 3-colorable.

    @GASARCH, why isn't the grid in #11 symmetric? Why is 21x9 4-colorable but not 9x21?

    ReplyDelete
  9. @Neel: you can still have corners in each of A, B, C, D which are at different coordinates within each 8x8 quadrant, and therefore may be the same color. You must additionally devise a specific grid or set of grids which disallow this. Good luck!

    ReplyDelete
  10. Could someone verify this solution?

    20022112200330023
    00220022002200220
    31133003311221132
    13311331133113311
    20022112200330023
    20022002200220022
    31133003311221132
    13311331133113311
    20022112200330023
    02200220022002200
    31133003311221132
    31133113311331133
    20022112200330023
    02200220022002200
    31133003311221132
    13311331133113311
    20022112200330023

    ReplyDelete
  11. @Ess: Look at the 5th and 6th rows of your so-called "solution":

    20022112200330023
    20022002200220022

    These rows contain many monochromatic rectangles, such as the rectangle in columns 2 and 3 with all four corners colored 0. Remember, the problem is to color the grid such that no rectangles have all four corners the same color.

    ReplyDelete
  12. I probably misunderstood the problem but something doesn't make any sense. You say that the 3x7 grid is in OBS2. This just isn't possible. Why? Because:
    1. If two the same patterns are used they will ALWAYS form a rectangle if the width > 2:
    010
    010
    2. With two colors, you could see each line as a binary number. However, there are only 8 different combinations. 7 of these need to be used (see point 1), therefore you get the following solution (interchangeing lines and flipping all colors won't change anything):
    000
    001
    010
    011
    100
    101
    110
    Which would work perfectly if the first line wasn't necessary. But as there are no other permutations left, this HAS to be used!

    Could you provide the 3x7 (or 7x3, it's almost the same) grid? I just don't see how it could be solved!

    ReplyDelete
  13. For the people who don't want to check their solution by hand, I've put a PHP script on pastebin that highlights all rectangles. It's not heavily optimized, but it should work with any size and number of colors.

    ReplyDelete
  14. 20022112200330023
    00220022002200220
    31133003311221132
    13311331133113311
    20022112200330023
    20022002200220022
    31133003311221132
    13311331133113311
    20022112200330023
    02200220022002200
    31133003311221132
    31133113311331133
    20022112200330023
    02200220022002200
    31133003311221132
    13311331133113311
    20022112200330023

    an attempt from Eric Purdy (too frantic to check!)

    ReplyDelete
  15. dutch, saying 7x3 is in OBS2 means it is NOT solvable.

    I'd like to reiterate Anonymous #8, the grid given has multiple discrepancies: 21x9, 21x10, 21x11, 21x12

    ReplyDelete
  16. Oh, Ok, that explains why I couldn't get any further.

    ReplyDelete
  17. I'm probably making a simple arithmetic mistake here, but when I went into the paper to see the argument for 7x3, I calculated

    z_{7,3} = floor(3/2+sqrt(57))+1 = 12

    from Cor 2.4, which is not 11 as in the table in Section 6.

    Is the "divided by n" inside the radical supposed to be dividing everything inside the radical?

    ReplyDelete
  18. Do I misunderstand the OBS or are you also interested in a 4-coloring of 21x10?

    120010130231144221101
    111203323023004323414
    403011221233201140214
    012334030223303131422
    102322001304014413203
    043104332322420204114
    313023024012310444033
    030224212130342011312
    334420413400241402421
    231130402114131320243

    ReplyDelete
  19. BTW 22x10 and 23x10 are also 4-colorable (if my program doesn't have bugs).

    ReplyDelete
  20. Jules, that's actually a 5-coloring.

    ReplyDelete
  21. 12345678901234567

    1 01230123012301230
    2 12301230123012301
    3 23012301230123012
    4 30123012301230123
    5 01230123012301230
    6 12301230123012301
    7 23012301230123012
    8 30123012301230123
    9 01230123012301230
    0 12301230123012301
    1 23012301230123012
    2 30123012301230123
    3 01230123012301230
    4 12301230123012301
    5 23012301230123012
    6 30123012301230123
    7 01230123012301231

    My suggestion, contact uchiki86@gmail.com

    ReplyDelete
  22. @Anonymous:

    12345678901234567

    1 01230123012301230
    2 12301230123012301
    3 23012301230123012
    4 30123012301230123
    5 01230123012301230
    6 12301230123012301
    7 23012301230123012
    8 30123012301230123
    9 01230123012301230
    0 12301230123012301
    1 23012301230123012
    2 30123012301230123
    3 01230123012301230
    4 12301230123012301
    5 23012301230123012
    6 30123012301230123
    7 01230123012301231

    ReplyDelete
  23. 21x10 is also shown as not solved, and has a smaller search space then 17x17. Would you be interested in its answer as well?

    ReplyDelete
  24. in http://www.cs.umd.edu/~gasarch/BLOGPAPERS/17x17chart.pdf

    the chart is not symmetric.
    Check 10x21 vs. 21x10.

    Same for 11x21 and 12x21.

    ReplyDelete
  25. This comment has been removed by the author.

    ReplyDelete
  26. uchiki86 - what about your rows 4 and 12

    ReplyDelete
  27. he most interesting part of the post


    -- Why 289?

    ReplyDelete
  28. what's up with the 74 item rectangle free 17x17? is 74 provably the smallest, or could there be a 73 yet to be found?

    ReplyDelete
  29. @Anon: Of course! Should've occurred to me, thanks. I considered using the new color in the permutations - that seems to take care of all crossover rectangles (there was, actually, a more direct problem with my solution). However, coloring the cross in between becomes rather tricky!

    @sep332: Thanks for pointing that out! I'm not sure I see why the one in each quadrant should be a problem (yet) - if you have shown it across the individual quadrant, like I was trying to say before, treat "A and C" as one large properly colored unit and "B and D" as a large properly colored unit and repeat whatever argument you have for, say, ruling out monochromatic rectangles across A and B. The coordinates cannot be too arbitrary since the rectangles have edges parallel to the axes?

    ReplyDelete
  30. It's impossible to solve by simply adding a row to the 16x17 solution as in the "EXCEPT for one square example" Any choice for the first 5 elements will lead to a rectangle.

    ReplyDelete
  31. i wrote my supercode which solved the problem but now i have no idea how to interpret the solution. my supercode is obviously coded in hard++.

    any ideas?

    ReplyDelete
  32. What is the best shot rotation if your haste rating with ranged weapons is 1.72 and you are BM spec'd?

    ReplyDelete
  33. I'm pretty sure it's impossible.

    Specifically, I posit that it's impossible to place 73 1s on a 17x17 matrix without creating a rectangle composed entirely of 1s.

    To reduce the case-checking that would be required to test this, it's simple to prove that the four rows with the most 1s have between 20 and 23 1s in total.

    I'm not too sure where to go past that, but if it can be proven that there exist four rows that span the column set with 1s, that makes things simpler. (Otherwise, if that can't be proven, it could lead to a way to construct the desired coloring!)

    ~scythe

    ReplyDelete
  34. anon to anon, the is a most formidable problem that lies at the very heart of this problem. If we solve your problem maybe we can solve the hardcode++ problem and maybe this will lead to a solution of the original problem ?

    What a nice way of putting things.

    Thank you.

    ReplyDelete
  35. 01230012301230123
    00000111122223333
    01111122223333000
    02222133320003111
    03333100021113222
    10123212332300301
    11032221033210032
    12301230130120123
    13210203231030210
    20231313002011312
    21320320303101021
    22013331200231130
    23102302101321203
    30312010212132320
    31203023113022013
    32130032010312102
    33021001311202231

    ReplyDelete
  36. Previous Anonymous, you are wrong. At least test your proposed solution before posting it.

    01230012301230123
    00000111122223333
    01111122223333000
    02222133320003111
    03333100021113222
    10123212332300301
    11032221033210032
    12301230130120123
    13210203231030210
    20231313002011312
    21320320303101021
    22013331200231130
    23102302101321203
    30312010212132320
    31203023113022013
    32130032010312102
    33021001311202231

    ReplyDelete
  37. For Anon #35: If its impossible, how can you explain the "74 items rectangle-free set" in the OP ?

    ReplyDelete
  38. The known results for 4-colorings claim that a 21 x 09 grid is colorable, but a 9 x 21 grid is not (reading the first value of the pair from the left column). There are other inconsistencies with some of the U cells close to this. I suppose a simple clerical error is to blame.

    ReplyDelete
  39. To Anon: yeah, rite who's gonna keep count of "For Anon #35"
    what a joke.

    ReplyDelete
  40. Not a solution - but here's 74 zeros that seem to work (don't know how to specify a fixed width font, so the columns don't line up properly through blogger):

    0...0....0......0
    .0....0........00
    ..0.0..0......00.
    ...0.0.......00.0
    ....0.0.....00...
    .......0..000...0
    ..0..00....0.....
    .0...0.0.0.......
    ........00.0.0.0.
    0..0..000........
    ......0..00...0..
    ....00..0.0......
    .0.00......0.....
    ..00.....0..0....
    000.......0..0...
    .0......0...0.0..
    0....0......0..0.

    ReplyDelete
  41. The chart had a typo which I have
    now fixed. THANKS for catching it!

    YES I am also interested in the status of 21x10, 21x11, 21x12, 22x10,
    17x18, 18x18. However I am not putting a bounty on those. It IS my hope that whoever does 17x17 will then use the software or math on those.

    Aaron Sterling- I will email you privatly on the mistake you may have found (fortunatly it does not affect the contest). Also, Aaron,
    THANKS for posting with your name,
    else I could not contact you.

    ReplyDelete
  42. Apologies for the post - was reading a thread on hacker news where they said you'd found a single colouring with 73 cells. Now I've checked it I see it was 74

    ReplyDelete
  43. It is claimed in the paper that exactly one of 19x17, 18x17, 17x17 is in OBS4 (This is close to a typo repeating that 22x10 is only 6 other unknown grids..).

    We know that 17x17 in OBS4 => 18x17 in OBS4 => 19x17 in OBS4. Thus, according to the claim 19x17 can be the only one of the 3 to be in OBS4 and 17x17 is solvable..

    But it seems clear that most of these claims are actually riddled with typos.

    ReplyDelete
  44. A valid coloring for a m x n grid can be turned into a valid coloring for a (m-1) x n grid (you just have to forget the last line of the grid). If there is
    exactly one of the following sets in OBS4: 19x17, 18x17, 17x17, the 17 x 17 grid must have a valid coloring.

    ReplyDelete
  45. Scott and louif, it's apparent that OBS4 is only a list of the "smallest" unsolvable grids: i.e. if 17x17 is in OBS4 then 18x17 is not, even though both would be unsolvable.

    ReplyDelete
  46. It's trivial to see that if you populate the left and top rows then all the remaining cells can be filled by process of elimination (or using process of elimination will yield a contradiction).

    Using this method I have a simple program that "proves" no solution, see here.

    ReplyDelete
  47. David Benson: Can you elaborate on your trivial "process of elimination" approach? I suspect you're making a silly mistake.

    ReplyDelete
  48. @David:

    Remember, there are four colors. Let's test your "process of elimination" theory on a smaller grid, say 3x3. Pretend you fill in the top and left rows as follows:

    123
    2__
    3__

    The four _s can be any color as long as they are not all the same color. This leaves 4^4-4=252 possibilities. No process of elimination here.

    ReplyDelete
  49. I decided to try the brute force approach. Last night, I wrote a program that fills a 17x17 grid with random numbers between 1 and 4, then searches for rectangles. If it finds one, it changes three of the vertices to new random numbers. This process is repeated until no rectangles are found. It has checked more than 131 million grids so far, with no hits.

    ReplyDelete
  50. Sassan, you are rite i ran the same program(not even knowing what the program is and waht it really does) on my computer and nothing checked. so, the answer to the original problem is a big "-no-".

    ReplyDelete
  51. Sassan: It would be good to test your approach on 15x15 or 16x16, which do have solutions.

    I also tried a Monte Carlo approach. I could get a 15x15 with a fair amount of computation, but I couldn't get a 16x16 even running on a grid for 12 hours. It seems like the state space is too large and/or complicated for my code. Thus I can't say that my not finding a 17x17 means that there isn't one.

    ReplyDelete
  52. Is there a LaTeX file of the alternate 74 Rectangle Free Set (there are only 2, apart from the trivial rearrangement of columns and rows).

    ReplyDelete
  53. Here's a 74 RF set I generated with an IP solver in python. I haven't verified that it's the alternate form though.

    ReplyDelete
  54. huh ? is sassan's code widely available or how did anon run it on his computer ?

    ReplyDelete
  55. Sassan,

    Why do you change three of the vertices, and not one? Changing three seems like you are more likely to introduce additional collisions.

    Brian

    ReplyDelete
  56. I myself tried various greedy-style local search approaches, where we start with a random coloring and repeatedly try to make a modification that reduces the number of bad rectangles by as much as possible. But for me no luck up till now either.

    ReplyDelete
  57. I found the coloring. There exists one. But i am unwilling to give away my solution for only 289.00.

    ReplyDelete
  58. I am skeptical of Annon #60's claim. It does, however, raise the interesting question can he convince us he has the correct answer with a zero knowledge proof for this particular problem?

    ReplyDelete
  59. well, i wouldn't be too sure of either now. #60 anon must certainly be a great card player.

    ReplyDelete
  60. I've tried the greedy and brute-force coloring approaches too without any luck so far. :(
    Question: Would anyone want to join forces? Perhaps we can increase the bounty using anon #60's trick. (But to be honest I don't care about the money at this stage, and would prefer to do an open wiki/wave where one could gather programs/ideas/failed approaches.)
    email: 289challenge@gmail.com

    ReplyDelete
  61. Suppose you have:
    ab
    cX
    and you wish to know the value of X.
    Since a,b,c touch you can assume they are three distinct elements; hence X is the unique {0,1,2,3} - {a,b,c}

    So if you have
    abcdefgh
    q.....
    r
    s
    t
    you can compute the dots left-to-right -- or reach a contradiction.

    ReplyDelete
  62. whooops, reading your editted post i can see that i had the definition wrong.

    ReplyDelete
  63. I find the problem presentation confusing, and I would appreciate it if someone would verify whether or not I understand the correctly.

    If I understand correctly, we are trying to create an N-coloring of an YxZ grid fitting constraints C. By grid, we mean the inset presence grid usually called a "checkerboard", where member cells, rather than member vertices, are considered, and where the member cells are not importantly different than squares.

    The prize line is only satisfied for a coloring of four or fewer colors of a grid of exactly Y=17, Z=17, given C.

    The constraints C are:

    * From the grid, define the set of rectangles R such that every rectangle:
    ** Contains only inset unit cells, never fractions and never empty surrounding space
    ** Every rectangle position allowable by that constraint is represented, given a minimum dimension in either direction of two unit cells - that is, fit any rectangle you can along the border lines of the grid, and count it
    *** We skip rectangles with dimension 1 because identical corners seem to violate the spirit of the search, and because 1x1 squares preclude a solution being possible
    ** By example, a grid of Y=2, Z=3 would have a set R of three rectangles: the two 2x2 squares and the master 2x3 rectangle. Similarly, a Y=3 Z=4 grid would have 17 rectangles.
    ** The 17x17 <= 4 coloring must therefore satisfy 18496 rectangle corner sets.
    * For every rectangle in R, show that the histograph of the four corners' colors contains a minimum of two colors.

    Is that a correct re-statement of the problem?

    For reference, R is expressable as

    rectlist(Width, Height) ->
    lists:flatten( [ [ {{X,Y},{X+W-1,Y+H-1}} || X <- lists:seq(1,(Width+1-W)), Y <- lists:seq(1,(Height+1-H)) ] || W <- lists:seq(2,Width), H <- lists:seq(2,Height) ] ).

    which is valid erlang that outputs

    1> color17:rectlist(3,3).
    [{{1,1},{2,2}},
    {{1,2},{2,3}},
    {{2,1},{3,2}},
    {{2,2},{3,3}},
    {{1,1},{2,3}},
    {{2,1},{3,3}},
    {{1,1},{3,2}},
    {{1,2},{3,3}},
    {{1,1},{3,3}}]

    For the sake of ease, one may also

    cornerlist(Width, Height) ->
    [ { {A,B}, {A,D}, {C,B}, {C,D} } || {{A,B},{C,D}} <- rectlist(Width,Height) ].

    ReplyDelete
  64. This comment has been removed by the author.

    ReplyDelete
  65. Um... color the first row ABABABetc, then the second row CDCDCDetc. Alternate rows in this fashion, no two letters will be adjacent. It's really late so maybe I'm missing something obvious.

    ReplyDelete
  66. @Neel:

    here is a 8x8 grid colored with 3 colors:

    1 1 2 2 2 2 2 2
    2 2 0 0 1 1 0 1
    2 1 0 2 0 0 1 1
    2 1 1 0 0 1 2 0
    2 0 1 1 0 2 0 1
    0 2 0 1 2 1 1 0
    2 0 1 0 1 0 1 2
    1 2 2 1 1 0 0 0

    ReplyDelete
  67. Alexandru and Neel- the paper has a 3-coloring of 10x10.

    bill

    ReplyDelete
  68. @Alexandru, @gasarch: Thanks! The explicit colorings should come in very handy, and I'm all inspired again.

    By the way, coming up from the other side - what's the smallest number of colors with which one is able to color 17x17? The first trivial number that comes to mind is 17 (color each row with a different color). An application of the probabilistic method seems to yield a number more than this. Applying the Lovasz Local Lemma seems to give us 14 (worked this out in a discussion with a couple of interested/victimized colleagues here).

    By looking at the 8x8 approach, I think getting a 7-coloring is quite easy, use a different set of 3 colors on the second set of quadrants, and yet another new color on the cross. I'm pretty sure it's not hard to bring this down to 6.

    Anyone got a 5-coloring? Sorry if a 5-coloring is obvious or has been pointed out in the post/associated literature and I've missed it all along!

    By the way, if you look at the 4x6 coloring, it has some very nice symmetry (mirror symmetry, across diagonals symmetry). It seems to reaffirm my hope to be able to go about this in a structural fashion, although I admit that I could be off on this by miles!

    ReplyDelete
  69. @neel The 17x17 grid can be 5-colored.

    ReplyDelete
  70. Has anyone tried using permutations of the rectangle-free set of 74 in order to reduce the complexity of a brute force approach? You might try to find as many rectangle-free sets of 73 as possible, find the 2 or even 3 that overlap least, and then randomly delete overlapping entries from all but one of the grids. That could reduce the overall complexity drastically.

    ReplyDelete
  71. I want to know if a 4x4 and 5x5 grid using 2 colors is possible, also whether a 9x9 and 10x10 grid of 3 colors is possible. If the 4x4 and 9x9 are possible while the 5x5 and 10x10 are not, I think it's reasonable that the 17x17 is not possible.

    ReplyDelete
  72. This comment has been removed by the author.

    ReplyDelete
  73. @Brad: I see - nice! Did you work that out, or is it around in the blog post/paper/talk slides and I missed it?

    @Anon 73: At least from the talk slides and the blog post, I figure that:

    5x5, 2 colors - not possible,
    4x4, 2 colors - possible (even 4x6 is possible)

    10x10, 9x9, 3 colors - possible. In fact, it was pointed out to me that the paper has an explicit 10-coloring. Hope this helps!

    ReplyDelete
  74. Well if anyone wants a good starting point.

    02231320323013110
    31303221100023102
    01322212013330001
    22100030113112332
    31131002221030322
    20233230230311021
    30120113233221100
    20003322101230131
    13202303012321310
    11013200322212303
    33220101301312032
    32010332011021223
    03012011130233212
    00311301232102231
    12021123112003033
    21320133320100210
    13332020001102123

    My algorithm only finds 18 problem rectangles in that (and my algorithm can find the 20x10 and 17x17 (5 color) in under 30 seconds.

    ReplyDelete
  75. This comment has been removed by the author.

    ReplyDelete
  76. This comment has been removed by the author.

    ReplyDelete
  77. Michael,

    I think 4-Coloring 2 x n is trivial:

    12
    34
    12
    34
    ....

    ReplyDelete
  78. @neel

    I constructed a 5-coloring of the 17x17:

    14115523345324421
    32355445114232225
    25145411123345522
    32414423225455135
    42545342512354351
    41152422443133552
    54243124455432351
    35552131341113324
    55132144512221335
    22222414335134531
    31234254145511121
    12441235544531542
    11544555252335423
    14254543512143144
    53425252421323234
    51211513411544312
    23333333233512443

    ReplyDelete
  79. Edward - Any adjustment to your grid will introduce new monochrome rectangles as it goes. Taking an incorrect solution as a starting point is not going to make finding a solution any easier, it's just going to force a similarly huge amount of computations but in a different way.

    ReplyDelete
  80. For what its worth I found this which only has 8 rectangles in it using simulated annealing on GPUs.

    00130231113223103
    21310021323230310
    03321322010103210
    30311130101322220
    32132113300210202
    02323003201021113
    13012223213311000
    10133301221302302
    21222010011332033
    03203230321110231
    12330212132002031
    33002011132101323
    21020200330313122
    30203102210233021
    30012312023020131
    21101333232031201
    11200123002123332

    ReplyDelete
  81. FWIW, the GPU simulated annealing has now found a tiling with just 7 bad rectangles and one with just 6. If it is of any use to anyone I can post these here.

    ReplyDelete
  82. @Brad: Woah, how do you come up with things like that? :)

    @kanodonkey: I'm sure you haven't missed this, but just in case, the post has a coloring that has only one bad rectangle... if your algorithm runs better on initial configurations with a small number of rectangles, then that would be the one to start off with :)

    ReplyDelete
  83. Esad: it's even more trivial than that :p

    01
    01
    01
    01
    01
    ..
    ..
    ..

    ReplyDelete
  84. @neel It's a secret, at least for now. :-)

    ReplyDelete
  85. I was curious if anyone has pondered a lower granularity approach. That is to say, attempting to enumerate all of the 4-colorable 4x4 squares (or, even better, all of the 8x8 squares), and searching a space composed of these pieces.

    Intuitively, we should appreciate by now that it is reasonably easy to come up with a 17x17 with only a few errors - and that the number of these is probably massive compared to the number with no errors. Further, there is little to no guarantee that the edit distance between the 17x17s with no errors and those with few errors is small. I appreciate that simulated annealing and GA both have tricks to get around these local maxima, but why not just decrease the total search space first?

    I appreciate that enumerating all of the acceptable 4x4s will not be easy - and that there will probably still be many of them. However, there are a lot of tricks involving the symmetries and permutabilities of the problem that should allow them to both be both computed and stored in a reasonable amount of space and time. Also, I would be willing to believe that, if you get the 4x4s, that the number of 8x8s would not be so large (at some point the constraints will overwhelm the size of the search space, though exactly when is unknown).

    Well, best of luck to all!

    ReplyDelete
  86. @neel Not sure I saw that. There is a link to a solution with just one missing "square" but as far as I can see whatever number/color you put into that missing square there are 4 bad rectangles not one. Maybe there was a different post I was missing.

    ReplyDelete
  87. @Brad: Heh! Link to an explanation when it's ready for the public domain, will you? I'm just generally mystified. :)

    @kanodonkey: You're absolutely right! My bad, sorry. I imagined that any color in the missing spot causes one violation, for no earthly reason at all.

    So, well, is 4 rectangles still better than 6 for a starting point, from the point of view that you were suggesting?

    ReplyDelete
  88. #35 has only 4 rectangles, nice one

    i'm interested in the algorithm used to create the grid

    ReplyDelete
  89. Sorry, i've not read all the comments of this post, so i don't know if the problem has been already solved, but I don't think it is posible to get that 17x17 square.

    Thinking backwards, how far can you get with a 2-colorable problem? You could get 4x4, 4x5 or 5x4 colorable grids, but not 5x5. Why? Since you have two elements and 5 positions in each row you will have at least 3 positions with the same color in any row. There can't be any other rows which have that color repeated in those 3 positions. So there are only 3 (= 2^2 - 1)posibilities in 4 rows, f.e:

    11122
    221XX
    122XX
    212XX
    ???XX

    Any combination you could think in substitution of the question marks will create a non-colarable grid.

    The same thing happens with the 3-colarable problem. You could get a 9x9, 9x10 or 10x9 colorable grid, but no 10x10 posible, since any row would have at least one color repeated 4 times. You can think in only 8 (= 3^3 - 1) posible distributions but 9 more rows to get.

    The last step would be applying the same to the 4-colorable problem. At least a color would be repeated 5 times per row. So only 16x16, 16x17 or 17x16 colorable grids could be found, but no 17x17 posible.

    ReplyDelete
  90. Miguel, a 10x10 is 3-colorable; see the pdfs in the OP.

    ReplyDelete
  91. Former VDW Undergrad12:32 PM, December 10, 2009

    There are 7 unique (up to re-ordering the rows and columns) rectangle free arrangements on 21x12 of cardinality 63--and none of any greater cardinality. Proof forthcoming just as soon as I get it written up.

    ReplyDelete
  92. I believe it's easy.

    1x1 -> 1 colour
    from 2x2 to 4x4 -> 2 colours
    from 5x5 to 8x8 -> 3 colours
    from 9x9 to 16x16 -> 4 colours
    17x17 -> 5 colours
    18x18 -> 5 colours

    How do I now? Easy. For example, an 8x8 square. 7 in binary is 111, there are three characters on '111'. So you can do it with 3 colours.

    For 8x8, 8 is 1000, you'll say 4 characters, let me explain.

    The theory is:
    1 - 1
    2 - 10
    3 - 11
    4 - 100 -> From 4 to above 3 colours and 4 is not included on that rule!!! 4 will be included on the rule of 2 colours.
    5 - 101
    6 - 110
    7 - 111
    8 - 1000 -> From 8 to above 4 colours and 8 is not included on that rule!!! 8 in 3 colours
    9 - 1001
    10 - 1010
    11 - 1011
    12 - 1100
    13 - 1101
    14 - 1110
    15 - 1111
    16 - 10000 -> From 16 to above 5 colours and 16 is not included on that rule!!! 16 in 4 colours

    Sooooooooo...
    17 - 10001 -> 5 colours
    18 - 10010 -> 5 colours

    Sorry about my explanation, i'm spanish and my English is a little bit...... you know....

    ReplyDelete
  93. Ruben, 8x8, 9x9, and 10x10 can all be done with 3 colors.

    ReplyDelete
  94. #37's grid is very interesting. there are 72 ones, 72 twos, 72 threes and 73 zeros. there are 4 rectangles, all with zero-corners and all can be removed by switching the colour of point (4,0). the problem is, switching the colour of this point doesn't make things better. who made the grid, machine or human? it looks to synthetic to be a random guess and the probability of guessing a 4-rectangle grid is very low. i'm looking forward to hearing from the grid's creator.

    ReplyDelete
  95. there is no 17x17 solution.

    i proved it.

    generally speaking, for any n x n matrix whose cell has 1 <= value <= k, any matrix whose n > k*k cannot have solution.

    proof itself is quite simple. smart middle school student is enough to understand.

    ReplyDelete
  96. Nara, if you really have that proof, post it! It's just wrong, as a 3-coloring of 10x10 matrix possible and 10 < 3*3 is not true.

    ReplyDelete
  97. Dude, the green background on your blog is killing me.

    ReplyDelete
  98. Am I totally missing what a strong c-coloring is? In the grid.pdf paper, Lemma 8.3, page 40: rows 4,8, columns 1,6? All colored R?

    ReplyDelete
  99. ZAC- THANKS- you have found a typo in the paper---
    I will fix soon.

    bill gasarch

    ReplyDelete
  100. ZAC: I have fixed it. THANKS!

    Bill G.

    ReplyDelete
  101. I believe I have proven that a 17x18 grid is NOT 4-colorable. See this post for a reference.

    ReplyDelete
  102. Sorry, I made a mistake in my previous comment. However, I do believe that the 17x19 case is impossible ... but I will not venture stating that I have proven it (yet).

    ReplyDelete
  103. Andre - 17x19 already known to be
    not 4-colorable. See original paper
    that is linked to

    bill gasarch

    ReplyDelete
  104. Hi to everyone,
    I've tried to solve the problem with a SAT solver, and couldn't yet.. I've written a Python script which translate the coloring problem to an equivalent Sat problem in the cnf file format, then I manually try to solve it with WinSAT and the script reads back the solution and checks if it works with the php script which has been posted..
    The Python script is now at https://code.launchpad.net/~sir-rainbow/+junk/4col , feel free to experiment with it(GPL code), I think someone with more knowledge of SAT solver might crack it :) it's also useful to generate grid of which we know there is a solution :)

    ReplyDelete
  105. I've tried solving the problem with a SAT solver based on WalkSAT. Since WalkSAT is an incomplete procedure, it can't prove unsatisfiability in general. For nxn puzzles, I managed to find a solution to 16x16 but no solution to 17x17.

    ReplyDelete
  106. Dear Gasarch,

    Thanks ever so much for bringing a truly fascinating problem to the world. It has kept me stimulated during the christmas holidays!

    First of all, I have not solved it. However, I have tried a number of approaches and thought I would share my experience just in case it should inspire someone else.

    I notice that the problem is highly symmetrical. If a single colouring is found for an mxn grid then then must be many others, since (I believe) the rows and columns can be permuted in any order, which leads to m!n! alternatives. Also, the 4 colours can be permuted and the grid itself can be rotated/reflected.

    An exhaustive search may not be so hard, because the vast majority candidates can be avoided by building up from smaller grids that have solutions, i.e. starting at 1x1, extending and backtracking (plus a few heuristics to avoid unnecessary attempts). Using this approach I can find 16x20 grids quite easily, e.g.

    0123012301230123
    1230123012301230
    2301230123012301
    3012301230123012
    0123123023013012
    1230230130120123
    2301301201231230
    3012012312302301
    0123200232101331
    3012133121030220
    2301022010323113
    1230311303212002
    0123331110322200
    1230002221033311
    2301113332100022
    3012220003211133
    0000121233332121
    1111030322223030
    2222303011110303
    3333212100001212

    Considering the number of vertices and colours, it is clear that if a solution for a 17x17 exists then at least one colour must occur >=73 times. So my next attempt involves searching for arrangements of single colour vertices (the remaining ones are blank) that has no monochromatic rectangles and then adding the second colour and so on. Using this technique it is possible to find grids with 74 zeros and 74 ones, e.g.


    1___0____11_100_0
    __100_1_1_100__0_
    1__1_1_0_0__010__
    ___01101001__0__1
    10__001__001___11
    __011___10_11__00
    _01__100_1_1__10_
    00_1______1_0011_
    010_0_0___11_1___
    _000____11___10_1
    _0__1_1_0__0_11_0
    __01__11010_0____
    11___0011___0_1_0
    _10_10_0_1_0_0_1_
    0111_0__0_____001
    01_0_110__0_1___0
    __1___01__001101_

    I'm using a GA approach here, but the last two colours are proving difficult (as one would expect). I was very impressed with kanodonkey's approach, since the best I can do with the remaining colours is 14 monochromatic rectangles.

    @kanodonkey, which GA library are you using?

    Best of luck everyone and a happy new year!

    baz

    ReplyDelete
  107. @baz: Care to share the bruteforce code?

    ReplyDelete
  108. @baz I coded the simulated annealing using a combination of java, C (jni) and CUDA (http://www.nvidia.com/object/cuda_home.html) to use the graphics cards. The code itself is pretty simple so I did not need to use any third party library for the annealing.

    ReplyDelete
  109. @baz I put a more detail on my implementation in the comments for Chris Taylor's excellent blog post here http://crntaylor.wordpress.com/2009/12/10/17-x-17-challenge/

    ReplyDelete
  110. @kanodonkey, no problem, the (embarrassingly simple) code for searching and backtracking I put here: http://www.sti2.at/~barryb/four_colour.zip

    It's Java and should be easy to import in to eclipse.

    The search is done in the ExhaustiveSearch class. All I did was play around with different implementations of ColourOrderer and saved some interesting combinations, e.g. class Exp_16x20. Have fun!

    ReplyDelete
  111. (Sorry, that was a reply to Anonymous 112. @kanodonkey, I have been meaning to get in to this CUDA stuff, perhaps now is my chance)

    ReplyDelete
  112. Hello,

    I am guessing that the majority of posters on this blog have never solved an NP-Complete computer science problem before.

    I have published a solution to the "10 most point dense 5x5 Boggle boards" problem. Starting from any initial board, the best ten boards will arise during a run of DeepSearch.c on a quad-core running over night.

    This kind of solution required 3 months focused effort.

    Deep Search Documentation

    As demonstrated, if a single non-monochromatic coloring exists, then many of them exist. Therefore, we are not searching for a global optimal value in the traditional sense.

    THE UNDERLYING ALGORITHM PRINCIPLE:

    Many roads lead to Rome, but when do we know that we are 1 step away from Rome?

    It seems that there are 2 important metric values that belong to this problem...

    1) The number of monochromatic rectangles.

    2) The minimum number of positions to be erased for a partial solution.


    Integrating these two values along with custom meticulous-record-keeping, to avoid cyclic-redundant behavior, will allow an adaptation of the DeepSearch.c framework to either find a working coloring, or provide solid evidence to call off the search.

    Obviously, when altering one position in the coloring at a time, shortcuts can be taken to reduce the analysis time required. This is the segment that I am investigating right now.

    Please contact me if you are serious about solving this problem,

    logarithm69@hotmail.com

    ReplyDelete
  113. Ok,

    I've now spent some time with the problem.

    The program I am writing will find a coloring with zero monochromatic rectangles if any exist, and further, it will be finding it roughly over night.

    If my program is unable to find the zero-coloring over night, the evidence will be so convincing to anybody who reads the WideSearch.c documentation that a reward of $289,000,000 will not convince any legit computer programmer to work on this problem.

    The solution that I am developing is far from trivial, includes advanced data structures / algorithms, and is based on POSIX pthreads parallel batch processing.

    An enormous number of 16x16 zero-colorings can be generated with a pencil, and a piece of paper.

    Get back to me if you want progress reports:

    logarithm69@hotmail.com

    All the very best,

    JohnPaul Adamovsky

    ReplyDelete
  114. I think that it would be nice to set up a clean place where everyone could put the best configuration he got, with a brief description of the method used - it is quite a pain to go through the hundreds of non-organized comments.

    Does it sound doable ?

    ReplyDelete
  115. for those interested, I just set up a place where everyone can put the best result he obtained + brief description of the method:
    http://linbaba.wordpress.com/17x17-challenge/

    I hope to have nice chats about ways of attacking the challenge ...

    ReplyDelete
  116. Hello,

    Let's not beat around the bush here... I like doing my mathematics by hand.

    Computers only need to be used when the paperwork becomes overwhelming. Computers should not be used when a pencil and paper will get the job done.

    By hand, a high-school student should understand how to generate an enormous number of 17x17 4-colourings with FOUR monochromatic rectangles. There may be a proof that FOUR is a hard limit, so find it in this essay, and get your $289. It may also be possible that no such limit exists.

    Allow me to demonstrate:

    Step 1) Define 4 colour sets { A, B, C, D }, where each set contains each colour, but has nothing in common with the other sets. There are many such sets.

    Example:
    A = 0123
    B = 1230
    C = 2301
    D = 3012

    Step 2) Using { A, B, C, D }, construct a perfect 16x16 4-colouring, where each row has nothing in common with 3 rows, and ( 1 of each colour ) in common with the remaining 12 rows.

    Example: 16x16 - A perfect 4-colouring.
    0 - AAAA
    1 - BBBB
    2 - CCCC
    3 - DDDD
    4 - ABCD
    5 - ACDB
    6 - ADBC
    7 - BADC
    8 - BCAD
    9 - BDCA
    a - CABD
    b - CBDA
    c - CDAB
    d - DACB
    e - DBAC
    f - DCBA

    * I am ashamed about how long it took me to formalize these simple permutations.

    Step 3) Group the rows with nothing in common together. There will be 4 groups, each containing 4 rows. This will guide Step 4.

    Gp0 = { 0, 1, 2, 3 }
    Gp1 = { 4, 7, c, f }
    Gp2 = { 5, 9, a, e }
    Gp3 = { 6, 8, b, d }

    Step 4) Build a 17th column by assigning 1 colour to each Group. Simply choose the corresponding Gp#. Note that a perfect 16x20 colouring can easily be generated using this method.

    Step 5) Build a 17th row by assigning 1 colour to each Column-Group with nothing in common. In the 17th row, each number represents 4 identical numbers. Notice how there will be a single position, which has not been assigned a colour, marked by X. When it gets assigned, it introduces exactly 4 mono-chromatic rectangles into an otherwise perfect 17x17 colouring. Behold the result:

    0 - AAAA 0
    1 - BBBB 0
    2 - CCCC 0
    3 - DDDD 0
    4 - ABCD 1
    5 - ACDB 2
    6 - ADBC 3
    7 - BADC 1
    8 - BCAD 3
    9 - BDCA 2
    a - CABD 2
    b - CBDA 3
    c - CDAB 1
    d - DACB 3
    e - DBAC 2
    f - DCBA 1
    L - 0123 X

    * L = Last Row Number 17

    Please do not give up hope just yet. If somebody would like to show me a 16x21 perfect 4-colouring, this might open the gates to the 17x17 perfect 4-colouring, because the 16x21 grid is the first format not easily plotted perfect by hand.

    Mathematical Aside:

    The "Apex Constraint Condition" - I define this condition to be a colouring where each row has exactly one position, of each colour, in common with EVERY other row.

    I conjecture that an analytical proof for the (existence / non-existence) of a perfect 17x17 4-colouring will arise from a thorough investigation of colourings having the "Apex Constraint Condition".

    Here is the solution to an NP-Complete problem, known to actually have a valid solution: 10 Best 5x5 Boggle Boards - TWL06


    All the very best,

    JohnPaul Adamovsky

    PS - Contact me if you have questions - logarithm69@hotmail.com

    Perhaps Rohan equates "unknown" with "by-hand".

    Here is the most simple explicit case:

    01230123012301230
    12301230123012300
    23012301230123010
    30123012301230120
    01231230230130121
    01232301301212302
    01233012123023013
    12300123301223011
    12302301012330123
    12303012230101232
    23010123123030122
    23011230301201233
    23013012012312301
    30120123230112303
    30121230012323012
    30122301123001231
    0000111122223333X

    * Think of a professional way to say: "Suck on it... Suck it long, and suck it hard."
    * The metric system, that's right, I don't have a job.

    ReplyDelete
  117. Hello People,

    Is the money real, or did I fall for a hoax?

    Long story short. I've stumbled into a proof that 4 Monochromatic rectangles is the HARD-LIMIT minimum for a 17x17 4-Colouring.

    Mathematics Required: High School - Basic Enumeration Techniques

    STATEMENT: It is impossible to construct 5 rows in any 4-Colouring, which have nothing in common with each other.

    PROOF:
    r1 - 0
    r2 - 1
    r3 - 2
    r4 - 3
    r5 - X

    * Filling X with any Colour will introduce a commonality in the set.

    CONCLUSION:

    Four sets of 4 rows with nothing in common is an absolute hard limit for a 16x16 perfect 4-Colouring. This represents a "Minimal Constraint Condition" for 16x16 Colourings. It can also be shown that the "Apex Constraint Condition" where every row has 1 position of each Colour in common with each other row is impossible to construct for a 16x16 grid, and trivial for a 16x20 grid.

    T1 - Any 4-Colouring can only contain a maximum of 4 rows with nothing in common.

    PROOF BY CONTRADICTION:

    Proposition: A Perfect 17x17 4-Colourings Does Exist

    Thus, this Colouring must contain a perfect 16x16 Colouring.
    By T1, and demonstrated in above post, the Optimal 16x16 Perfect Colouring has 4 sets of 4 rows with nothing in common.

    Even with this optimal arrangement, there will be 4 sets of columns with nothing in common, and there will be 4 row sets with nothing in common.

    Each row and column set can therefore be assigned a unique Colour, which will be added to the 17th row and column respectively. Adding the 16-element-row and 16-element-column will then introduce ZERO monochromatic rectangles.

    The final element in the Bottom-Right corner is marked with an "X".

    Leaving the "X" blank, even in the most optimal case, the 17th row, and 17th column have exactly 1 Colour in common with each other corresponding row or column.

    Filling any Colour into position X will thus introduce exactly 4 monochromatic rectangles. Simply inspect the Enumeration examples in the post directly above this one...

    The proposition is a logical flaw, because assuming it to be true, PROVES THAT IT IS FALSE!


    Therefore, A Perfect 17x17 4-Colourings Does NOT Exist


    PS - I prefer cash, so please find a colleague of yours that lives in Toronto, who can hand it to me, and then you can wire them the money.

    PPS - I prefer not to deal with banks until I get a sincere-written-apology from CIBC for claiming that they saved my life by emptying the $5000 in my account, while I was in a 25 day-long coma. I saved up that money working construction to pay for a trip to find a merit-based Aerospace Engineering job. I'm pretty sure that bankers aren't in the business of saving lives, and I don't give up, so I am still unemployed.

    PPPS - I'm thinking this was a hoax, because I doubt that a tenured computer scientist would have any trouble putting together this bush-league high-school proof after a thorough and systematic investigation. I've recovered from massive head trauma, so even if it was a hoax, I'd at least like some peer review, and then my money in cash.

    PPPPS - I also wrote an extremely powerful search algorithm in C with meticulous and space-saving record keeping, so as to completely eliminate cyclic redundant analysis, while being extremely greedy. Row isolated deviations allowed my quad core to analyse 2,733,499,642,000 of the best colourings in 9 hours and change. The program tanks out at 4 monochromatic rectangles, moves around the 6 to 10 space, and finds the next closest 4-mono-Colourings (typically 20 of them).

    5 Monochromatic Rectangles are never found.

    Maybe put out a bounty to prove that they don't exist.

    Either your intuition was way off, and-or you're a stooge.


    All the very best,

    JohnPaul Adamovsky


    Get back to me please:

    logarithm69@hotmail.com

    ReplyDelete
  118. Typo correction:

    "Leaving the "X" blank, even in the most optimal case, the 17th row, and 17th column have exactly 1 *Colour* in common with each other corresponding row or column.

    Replace *Colour* with "of each Colour".

    It's 2 small words, and it doesn't sound as good, but it is correct.

    I hope that this slip-up can be overlooked.


    All the very best,

    JohnPaul Adamovsky

    ReplyDelete
  119. Hello Gasarch,

    Did you go to Law School?

    It sounds like your unwillingness to pay out the imaginary $289 is a clear indication that you have never studied mathematics!

    In simple Mathematics, a proof falls under only 2 categories:

    1) VALID
    2) INVALID

    My proof, although the syntax does have typos, is logically airtight, and thus falls into category #1.

    Please do the honorable thing, and pay out the Challenge Prize.

    Without the $289, this so called Challenge is a lot of hot air. It's a novelty act, like Topo Gigio.

    Mathematics, in its very nature is self-consistent, and thus not open to subjective interpretation. In other words, there is no room for debate using simple mathematics, and hence, it will never see the inside of a court room.

    Given a valid proof, the honorable man must pay out the $289, in order to remain consistent.

    Deciding not to pay the $289 for a VALID proof is what ultimately fails the "Reasonable Test".

    Does that seem clear to you?

    ReplyDelete
  120. 1) I have looked over your proof and I do not find it convincing.

    2) You claim that a 4-coloring of 16x16 MUST have a certain form.
    There are MANY 4-colorings of 16x16 with different forms.
    I recommend that you use your computer programs to find a 16x16
    that is NOT of that form. If you find one then you will know your
    approach cannot work. If you do not find one then you can try to
    make your approach work.

    3) MANY people have worked on the problem using computers. I have not
    kept any results secret. They have all posted on either my blog
    (Probably THIS posting) or on Brian Hayes Blog of Dec 2, 2009.

    4) I set it up so that only a VALID coloring gets the money to
    avoid getting into lawsuits--- what if someone emailed me or posted
    an incorrect proof that they insisted was correct.
    And then sued for the money. Do we really want
    the supreme court deciding on what a valid proof is?
    (I don't think any of them have any mathematics training.)

    GASARCH

    ReplyDelete
  121. JohnPaul,

    I didn't go to Law School, but I do know how to read. Your proof states: "Therefore, A Perfect 17x17 4-Colourings Does NOT Exist." I will not comment on whether your proof is "VALID" or "INVALID." But if it is valid, as you claim it is, then you have proven that 17x17 is not 4-colorable.

    Now refer back to Gasarch's original blog post:
    What if 17x17 is not 4-colorable? Then nobody will collect the $289.00. Even so, if you find this out I would very much like to hear about it. I don't want to offer money for that since if your proof is a computer proof that I can't verify then its not clear how I can verify it. I also don't want to offer money for a reasonable proof since this may lead to having the Supreme Court decide what is a reasonable proof.

    ReplyDelete
  122. Hello Gasarch,

    Here is a great idea...

    You claim that 16x16 perfect colourings exist in many different forms, so why don't YOU produce some of these imaginary-fantasy-grids and elevate your comment from anecdotal jibber-jabber self-defense to something more scientific and systematic.

    It is not my job to validate your weak comments.

    You say that you have seen one, so produce it! Please!

    If it does exist, I will work it into my proof because my humble intuition tells me that the logic is airtight. I certainly don't trust your intuition.

    I am using my time to work on your problem, and not the other way around.

    Let me show you a little magic-trick:

    Your dear-boy, Rohan Puttagunta produced this 17x17 4-colouring with 4 monochromatic rectangles:

    11112222333300000
    12222333300011110
    13332000311122220
    10002111322233330
    21233230030101231
    22103321003210321
    23013012012323011
    20323103021032101
    31300201131202312
    32030310102113202
    33120023113020132
    30210132120331022
    01021213232003123
    02311302201312033
    03201031210221303
    00131120223130213
    012301230123123+0

    Flip some of the rows and columns, and what do we get? a 16x16 colouring with four sets of 4 rows with nothing in common. BOOM:

    Does this look vaguely familiar to you, Gasarch?

    0123012301230123 0
    1230301223011230 0
    2301123030122301 0
    3012230112303012 0

    0123123012301230 1
    1230230130120123 1
    2301012323013012 1
    3012301201232301 1

    0123230123012301 2
    1230123001233012 2
    2301301212300123 2
    3012012330121230 2

    0123301230123012 3
    1230012312302301 3
    2301230101231230 3
    3012123023010123 3

    0000111122223333 +

    Sets A, B, C, and D are the same, and the beyond that, there is some superficial shuffling of relative locations.

    AAAA 0
    BDCB 0
    CBDC 0
    DCBD 0

    ABBB 1
    BCDA 1
    CACD 1
    DDAC 1

    ACCC 2
    BBAD 2
    CDBA 2
    DADB 2

    ADDD 3
    BABC 3
    CCAB 3
    DBCA 3

    0123 +

    Patterns do exist in the 16x16 perfect colourings.

    Please show me the magical-mystery-imaginary 16x16 colourings with radically different formats to the one demonstrated in my proof, or just be a man and pay out the prize money.

    $289 isn't going to ruin you, but it will save you from a competition that simple mathematics will not allow you to win. Also, being unemployed, I have 24 hours a day to work on this. It makes a lot of sense for you to just do the honorable thing here, and pay this man his money.

    All the very best,

    JohnPaul Adamovsky - TRUE until proven FALSE.

    PS - No more superficial anecdotes please. Systematic, hard-evidence only.

    Nobody cares whether a cheap-lazy-slob, with $289 to lose, is convinced by my proof. Mathematics is entirely self-consistent. There is no debate here, Gasarch. I win. Period.

    ReplyDelete
  123. JohnPaul Adamovsky:

    INNOCENT until proven GUILTY.

    TRUE until proven FALSE.

    ReplyDelete
  124. Gasarch,

    You say:

    "There are MANY 4-colorings of 16x16 with different forms."

    Is this based on your keen scientific intuition?

    Have you actually seen one? Were you awake at the time?

    Work with me here, pal, I am trying to help you out, so please show us even just 1 16x16 perfect 4-coulouring with a different form than the one I use in my proof.

    anecdotal: based on personal observation, case study reports, or random investigations rather than systematic scientific evaluation

    Please at least show us your personal observations. I can't see inside of your head and I don't want to.


    All the very best,

    JohnPaul Adamovsky

    PS - The 16x16 4-colouring in Rohan's example has four sets of four rows with nothing in common just like mine, and if your blog worked properly, it would be posted here.

    ReplyDelete
  125. I am making good progress in my attempt to enumerate all possible Perfect 16x16 4-colourings so as to complete my proof.

    So far, any 16x16 4-colouring, which emerges from a 16x20 Perfect colouring with the "Apex Constraint Condition" will not fit into a 17x17 perfect colouring.

    There is a good chance that all 16x16 Perfect colourings can be obtained in this manner, and hence my proof is complete.

    Help out if you understand what I am trying to do.


    All the very best,

    JohnPaul Adamovsky

    ReplyDelete
  126. JohnPaul,

    I'm having trouble following your quick proof sketch thing. Would you mind explaining the following further?

    "Four sets of 4 rows with nothing in common is an absolute hard limit for a 16x16 perfect 4-Colouring."

    If it's as simple as I believe it to be, could you explain why such a coloring is necessary as a basis for a valid 17x17 coloring?

    Thanks,
    Dumb Anonymous Reader

    ReplyDelete
  127. JohnPaul,

    I think you deserve $289 just for the pure entertainment value of your posts. Thanks for brightening my day!

    ReplyDelete
  128. @JohnPaul Is there something special about 4, or does your argument show that (k+1)x(k+1) can never have a perfect k-coloring?

    ReplyDelete
  129. @Anonymous poster #133:

    The special boundary cases of interest for k colors occur at dimensions (k^2+1)x(k^2+1).

    5x5 - not 2-colorable
    10x10 - 3-colorable
    17x17 - ??

    This brings up an interesting point for JohnPaul: You claim that a valid 4-coloring of a 17x17 grid requires a 16x16 subgrid of a specific form. If this is true, I would hazard to guess that it would also be true for a 3-coloring of a 10x10 grid - specifically, that it would need a 9x9 subgrid of the same restricted form.

    Of course, if that were true, 10x10 would not be 3-colorable, but we know[1] it is.

    So, to JohnPaul: What about your proof holds in the 17x17 case, but allows the 10x10 to remain 3-colorable under the same arguments?

    [1] See slide 44 of Bill's Rectangle-Free presentation:
    http://www.cs.umd.edu/~gasarch/papers/gridtalk.pdf

    ReplyDelete
  130. Hello Michael,

    Thank you for pointing me to the Perfect 10x10 3-colouring.

    My initial conjecture was that every Perfect (K^2)x(K^2) colouring was a subset of an "Apex Constraint" colouring.

    Investigating the 10x10 colouring will certainly aid in my enumeration analysis.

    I've got some thinking to do.


    All the very best,

    JohnPaul Adamovsky

    ReplyDelete
  131. The imaginary 17x17 Perfect colouring must contain within it, a 17x16 Perfect colouring with four independent sets of rows, which are missing at least one colour in common.

    This is a much looser form than the one contained in my proof.


    All the very best,

    JohnPaul Adamovsky

    ReplyDelete
  132. Hello,

    I could use some help here.

    I have an idea, which I am fairly certain is a good idea:

    The 17x17 grid search-space can be reduced to a static row and column, with a 16x16 dynamic grid.

    Observe:

    00000111122223333
    0YYYYxxxxxxxxxxxx
    0YYYYxxxxxxxxxxxx
    0YYYYxxxxxxxxxxxx
    0YYYYxxxxxxxxxxxx
    1xxxxxxxxxxxxxxxx
    1xxxxxxxxxxxxxxxx
    1xxxxxxxxxxxxxxxx
    1xxxxxxxxxxxxxxxx
    2xxxxxxxxxxxxxxxx
    2xxxxxxxxxxxxxxxx
    2xxxxxxxxxxxxxxxx
    2xxxxxxxxxxxxxxxx
    3xxxxxxxxxxxxxxxx
    3xxxxxxxxxxxxxxxx
    3xxxxxxxxxxxxxxxx
    3xxxxxxxxxxxxxxxx

    I am thinking that any candidate 17x17 Perfect Colouring can be converted into this format using row/col switches, and colour flip-flops.

    The "Y" positions can only take on 3 colours.

    Please let me know if you have anything to add...

    Along with my enumeration investigation, I am going to write a program that uses this format, along with massive pre-allocated arrays, and POSIX threads, which will hopefully start from a mono-colouring, and bounce around to colourings with the HARD-LIMIT minimum RANK. It will be extremely greedy, keep trie-compressed records, and have deviations confined to single rows to reduce the analysis time required.

    All the very best,

    JohnPaul Adamovsky - logarithm69@hotmail.com


    PS - I've decided to solve this problem if it is possible, and there is a very good chance that it is possible.

    ReplyDelete
  133. Hello JohnPaul,

    I am very interested in helping you with this problem. However, I cannot fully understand what you have written in your latest post.

    Can you explain what you mean by "The 17x17 grid search-space can be reduced to a static row and column, with a 16x16 dynamic grid." Also can you explain the diagram? So Y can be either 1, 2 or 3. Which values can x take?

    I am very impressed with your solution to the problem of finding dense Boggle boards. You will be interested to know that currently there is a contest exploring a related problem: http://www.v-sonline.com/index.pl?C6

    ReplyDelete
  134. Hey Man,

    I've been working on something much more important than this problem for the past little while, but it is always in the back of my mind.

    Here is the answer to your question:

    In a colouring with rank zero:

    Everybody knows that there will be an equal number of squares of each colour in each row and an additional member in one colour group.

    Somewhere in the grid, a row and column will intersect with the same additional colour.

    Based on these self-evident observations, The search-space being explored can be drastically reduced.

    Simply put, a 17x17 grid (4 colours) can be formatted into 16x4 grid, where each space will have more colours, but less than 256.

    The lesson learned is that massive improvements will be made in analysis time, and memory requirements for meticulous record keeping will drop way down.

    I used a similar search-space reduction in the Boggle problem by only considering the 14 most frequent characters, because the remaining 12 were too sparse for consideration.

    In no way is this program going to be easy to read, let alone code. I'll have time when the water in the great lakes gets too cold. First I'll code this scheme for finding a 10x10 perfect 3-colouring. One that is know to exist. And based on the performance of that experiment, I'll proceed to find the 17x17 perfect 4-colouring if it actually exists.


    All the very fucking best,

    JohnPaul Adamovsky

    ReplyDelete
  135. Given c colors and m colums how many rows (n) can i produce without a rectangle?

    Algorithm:

    1. Create a data structure with c^m arrays.

    2. Populate every array with one of c^m combinations of c colors over m columns.

    3. While an array exists:

    3.1 Select an array with uniform distribution of c colors over m columns.

    3.2 Delete every array that produces a rectangle.

    4. Print n, the maximun number of rows.

    Correctness:

    Why uniform distribution? Because minimizes the number of possible rectangles for a given color and
    maximizes the number of rows.

    Example: c=2 and m=3

    - non-uniform distribution selection produces:

    000 <- !
    110
    101
    011

    n=4

    - uniform distribution selection produces:

    001
    010
    100
    011
    101
    110

    n=6

    If (m mod c) > 0? The algorithm becomes a little more complicate. It is necessary maintain an history of how
    many times a color has been selected.

    Example: c=3 and m=8
    0s 1s 2s

    01201201: 0 3-times, 1 3-times, 2 2-times -> 3 3 2
    20120120: 0 3-times, 1 2-times, 2 3-times -> 6 5 5
    12012012: 0 2-times, 1 3-times, 2 3-times -> 8 8 8

    In this case are necessary 3 iterations to maintain equal the amount of combinations deleted.

    Application:

    - 17x17 challenge: c=4, m=17, c^m=4^17=17179869184, m mod c = 17 mod 4 = 1 -> 4 iterations, one for color.

    Good luck!

    info: patrick.laarson@yahoo.it

    ReplyDelete
  136. Hello,

    In this simple calculation, the 10x10 3-Colouring search-space will be reduced to 9 independent 3x3 squares, each with significantly less colour combinations than 3^9. The result is like reducing a search of Earth's surface to searching 6 square millimeters.

    Total Search Space = 3^100 = 5.154 x 10^47

    Reduced Search Space = (26*6) x (204*6)^6 x (575*6)^2 = 6.244 x 10^27

    = 156 x 3362702965323595776 x 11902500 = 6243833238983199400919040000

    (Reduced Space) / (Full Space) = 1.211 x 10^-20

    Analogy: Search the entire surface of the world for a missing Colorado Potato Beetle.

    Total surface area of Earth = 4 * Pi * (6400KM)^2 = 514718540KM^2


    Using search-space reduction logic akin to this algorithm:

    The beetle will be found after searching an area of this size:

    Reduced Search Area = (1.211 x 514718540KM^2) / (10^20) = (6.233 x 10^-12)KM^2

    (1KM)^2 = (10^6)M^2 = (10^12)mm^2

    Search Area = 6.233 mm^2


    # - Map - Char
    | 0| - |000| - | 0 |
    | 1| - |001| - | 1 |
    | 2| - |002| - | 2 |
    | 3| - |010| - | 4 |
    | 4| - |011| - | 5 |
    | 5| - |012| - | 6 |
    | 6| - |020| - | 8 |
    | 7| - |021| - | 9 |
    | 8| - |022| - | 10 |
    | 9| - |100| - | 16 |
    |10| - |101| - | 17 |
    |11| - |102| - | 18 |
    |12| - |110| - | 20 |
    |13| - |111| - | 21 |
    |14| - |112| - | 22 |
    |15| - |120| - | 24 |
    |16| - |121| - | 25 |
    |17| - |122| - | 26 |
    |18| - |200| - | 32 |
    |19| - |201| - | 33 |
    |20| - |202| - | 34 |
    |21| - |210| - | 36 |
    |22| - |211| - | 37 |
    |23| - |212| - | 38 |
    |24| - |220| - | 40 |
    |25| - |221| - | 41 |
    |26| - |222| - | 42 |

    This is the reduced search-space template:

    0000111222
    0AAABBBCCC
    0AAABBBCCC
    0AAABBBCCC
    1DDDEEEFFF
    1DDDEEEFFF
    1DDDEEEFFF
    2GGGHHHIII
    2GGGHHHIII
    2GGGHHHIII

    Each 3x3 letter square is treated as an independent unit. 'E' and 'I' will have the most colour-combinations. 'A' will only have 156.

    It is important to note that such basic enumeration can make an NP complete problem seem very solvable.

    This search-space reduction, along with the "Intelligent Locust Swarm" algorithm-framework should provide a prototype for solving borderline NP-Complete problems like the Perfect 17x17 4-Colouring.

    I will keep you people informed of my progress, and publish a streamlined web-page series when I have definitive results.

    All the very best,

    JohnPaul Adamovsky

    ReplyDelete
  137. Is this Challenge still up? How can I contact you, if I found the solution? How will you send me the money?

    ReplyDelete
  138. Martin Thoma- YES the challenge
    has not been solved and is still
    worth $289.00.

    You email me the solution I will
    mail you a check for the $289.00.

    I will then post about it so people
    will know that it has been solved.
    (You also have a blog so you can do the same if you wish.)

    If this mechanism does not work then email me and we'll work out something that does.

    ReplyDelete
  139. Well, I have no solution jet. I'm trying to find solutions to a simmilar problem and a friend sent me this link.

    Where can I find your Email-Adress?

    ReplyDelete
  140. You can google GASARCH to find my home page that has my email on it OR I can tell you now:

    gasarch@cs.umd.edu

    (My homepage is also linked to from
    the side of the blog.)

    GOOD LUCK! I still very much want the problem to be solved.

    ReplyDelete
  141. I've successfully enumerated every possible perfect 10x10 3-Coloring, using a novel and dazzling algorithm, as a Proof-Of-Concept for solving the 17x17 problem. In response to my proposal, requiring a 24 thread machine, William Gasarch said it was long, so he wasn't interested in reading it.

    When my work is long, it can be more accurately described as:

    RIGOROUS, EXACT, DETAILED, CONSISTENT, THOROUGH, CONSCIENTIOUS,
    METICULOUS, COMPREHENSIVE, PAINSTAKING, RELENTLESS, PROVEN, UNCOMPROMISING, DILIGENT, SYSTEMATIC, DEDICATED, CONVICTION, VIGILANT, METHODICAL, TESTED, DISCIPLINED, ALL THE VERY BEST, PERFECT.

    In one word: SCIENTIFIC.

    I will now give you a link to the entire email I send to William Gasarch with my proposal, so you can judge for yourself, if the program, I took it upon myself to write for him, is the most powerful algorithm ever coded to solve this class of problem.

    My program finds the first perfect coloring is seconds, and enumerates all of them, over night.

    Proposal-Email.zip

    Explain this:

    A Perfect 10x10 3-Coloring -

    0|000|111|222|
    -?---?---?---?-
    0|211|221|020|
    0|212|012|101|
    0|221|100|211|
    -?---?---?---?-
    1|012|120|002|
    1|022|201|110|
    1|101|212|200|
    -?---?---?---?-
    2|102|001|021|
    2|120|102|102|
    2|110|020|210|
    -?---?---?---?-

    Each row-col has a (3, 3, 4) color distribution, but the square as a whole, has the following color spread:

    34 0's
    34 1's
    32 2's

    Pick up on this pattern: Of the 2 colors with a 34 count, each (4-count) row intersects with a (4-count) col of the same color.

    From the top-left to bottom right, there are 9 enumerated sets, which must be internally rectangle free, and must not rectangle with the static row and column. Further, set 0, 4, and 8 are limited to an in-order "Permutation 0" configuration.

    Bottom line, 864 configurations are found using the above template, and 864 = 3^3x2^5, there are many less unique configurations.

    You got valid color-swaps, valid column shuffles, valid (4-4 Intersect) flips, and row-col exchange. Testing for uniqueness is not a trivial exercise, so I am leaving for each, his own.

    I consider myself something of an Oracle-Machine-Automaton, so I need Gasarch for NOTHING.

    I will use the Proof-Of-Concept template to solve the 17x17 problem in my own time, and share the solution with Gasarch, NEVER.


    All the very best,

    JohnPaul Adamovsky

    PS - Gasarch, you have been weighed, you have been measured, and you have been found wanting.

    PPS - If you want to know who I am, look me up on Google, you genius. Then READ.

    PPPS - You are now playing "THE MANS GAME". Investigate and produce something of value, or finish crumbling.

    ReplyDelete
  142. Charlie Sheen, is that you?

    ReplyDelete
  143. As of today, March 24, is the known information still accurate? That is, are the following problems still open?

    12x21
    17x17
    17x18
    18x18

    I'm just checking to make sure! Recently, we've been trying an IP approach using column generation and branch-and-price, which takes advantage of a pretty tight LP formulation for the problem. Do you know if anyone has tried similar things before (and failed)? It would be good to know before we spend a great deal more time on it :)

    ReplyDelete
  144. Mizzao- YES they are still open.
    I think people have tried IP but I am not sure since most of the info I get is random blog postings which are short.

    I recently did an UPDATE on the problem post (punchline- 17x17 still open as are the four you mention).
    You could post a comment there where people will see it and ask around.

    GREAT that you are trying this!

    GASARCH

    ReplyDelete
  145. I've been experimenting with applying a SAT solver to this problem. So far, it doesn't look terribly promising. After 8.5 hours of CPU time, the SAT solver still has not found a solution to the 17x17.

    Slightly more details: I experimented with two encodings into SAT, based upon how we encode the color of each grid square: (1) each color is encoded in 2 bits, so the 4 colors are encoded as 00, 01, 10, 11, (2) a "one-hot encoding" into 4 bits, so the 4 colors are encoded as 0001, 0010, 0100, 1000. On smaller puzzles, encoding into 2 bits seemed to work better than a one-hot encoding. I use STP as a wrapper around MiniSAT (STP has a more convenient input syntax). For each rectangle, I generate a constraint saying that it is not the case that all 6 pairs of corners are same-colored (the not of an and of 6 terms, where each term says that 2 corners have the same color).

    I just thought I'd document my approach for others to benefit from.

    ReplyDelete
  146. I think I've a dead end with using SAT. I thought I'd report on my experience, in case it is useful to others. So far the main takeaway seems to be: it looks like it may require some additional ideas to make progress, using a SAT solver.

    After more experimentation, the 2-bit encoding seems superior to the 4-bit 1-hot encoding. I also experimented with an optimization. For a mxn grid, given any solution, we can permute the rows and columns arbitrarily, leading to m!n! other solutions. Therefore, without loss of generality, we can focus on colorings where the rows are in lexicographic order, and where the columns are also lexicographically ordered. My hope was that this might reduce the search space.

    On small examples, adding constraints to require the rows to be in lexicographic order did seem to provide some improvements. (It turned out this was easy to code up in STP, using one bitvector for each row and STP's BVLT operator.) Then, I tried adding more constraints to require both the rows and columns to be lexicographically ordered. However, this didn't seem to provide improvements; on small cases, it seemed to slow things down a little bit. (This was slightly trickier to code up in STP: I introduced a separate set of variables, one bitvector for each column, which was related to the row-bitvectors by a matrix transpose operation. This might have introduced more boolean variables, depending upon how STP bit-blasts to SAT.)

    Here are some timings for various smaller square grids, using two implementations: in the first column, rows are lexicographically ordered (and columns unconstrained); in the second column, both rows and columns lexicographically ordered.

    10x10: 1.23s 2.07s
    11x11: 3.86s 4.75s
    12x12: 9.50s 9.47s
    13x13: 31.57s 23.42s
    14x14: 643.39s 1103.32s
    15x15: ? ?

    I have not managed to get the SAT solver to terminate on the 15x15 grid yet. So it looks like this is quite a ways away from being useful on the 17x17 grid.

    (I suppose there are some more directions one could try. For instance, one could pick one color, find the maximal number of squares you can place one color without creating a rectangle of that color, fill in those squares with that color, and then try using a SAT solver to fill in the remaining squares. I haven't tried this.)

    ReplyDelete
  147. Here is a colouring with 5 monochromatic rectangles, which shows that JohnPaul Adamovsky was wrong in his 15th of July 2010 post:

    11111222233334444
    12222233334444111
    13333244431114222
    14444211132224333
    12243143212431423
    22143431424312341
    21234112443413213
    21324434211233431
    21432321342131142
    34321441312342213
    33412432113212124
    34231123144122431
    32143324141241214
    44321323423411324
    43412314224321231
    43214141321243342
    42123412343124132

    ReplyDelete
  148. I couldn't stop laughing at JohnPaul Adamovsky's email. I'm sorry. There's no way that was a serious thing.

    ReplyDelete
  149. Continuing on what David Wagner said about SAT solvers, I also want to post here in case anyone finds my info useful or interesting...

    I looked into this problem for a semester as my undergraduate senior project.

    If I remember correctly, I also could not get any complete solver(by 'complete' I mean a solver that will always come to a SAT/UNSAT conclusion) to terminate on 15x15 or greater. 14x14 and below were relatively easily solved. I tried almost every competitive grade solver available at the time. I took the solvers from the SAT-competition and ran them on modern high-end computers for days and sometimes weeks on end (longest was almost maybe 2-3 months).

    HOWEVER, using incomplete solvers (solvers that can find SAT solutions, but will never be able to determine an UNSAT formula) can easily color grids up to and including 16x16 in mere seconds. These types of solvers are ones based on the GSAT and WALKSAT algorithms, for example. Once we get to 17x17 the solver comes close to, but not quite satisfying the formula.

    As for the "more directions one could try" that you mentioned, I've tried it all. Examples include what you mentioned as well as: Starting with a partially coloring a grid, starting with the 17x17 rectangle free subset given by Gasarch, starting with a randomly colored grid, starting with smaller fully-colored grids, etc...

    I've another approach I looked into was using genetic algorithms, but it seems to be less effective than SAT.

    ReplyDelete
  150. Bill,

    I really can't wait to see the perfect 17x17 4-coloring. I wonder if it even fits into my 4x4 grid pattern.


    All the very best,

    JohnPaul Adamovsky

    ReplyDelete
  151. The problem is solved- there IS a 4-col or 17x17 and of 18x18.

    See my Feb 8 2012 post.

    ReplyDelete
  152. I was curious about how far this work has come and I'm so happy to see this blog Dr. Gasarch!

    ReplyDelete
  153. The 17 x 17 problem was SOLVED and we now know
    exactly which grids are 4-colorable (other grids
    had to be figured out also).

    The lastest version of the paper is on my website
    and has all of the results.

    ReplyDelete