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:
- 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).
- OBS2 = {3x7, 5x5, 7x3}
- OBS3 = {19x4, 16x5, 13x7, 11x10, 10x11, 7x13, 5x16, 4x19}
- OBS4 contains 41x5, 31x6, 29x7, 25x9, 23x10, 10x23, 9x25, 7x29, 6x31, 5x41
- Exactly one of the following sets is in OBS4: 21x13, 21x12.
- Exactly one of the following sets is in OBS4: 19x17, 18x17, 17x17.
- If 19x17 is in OBS4 then 18x18 might be in OBS4 . If 19x17 is not in OBS4 then 18x18 is not in OBS4 .
- A chart of what we do and do not know about 4-colorings of grids is here.
- 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?
- A Rutgers grad student named Beth Kupkin has worked on the problem: here.
- A high school student (member of my VDW gang) Rohan Puttagunta has obtained a 4-coloring of 17x17 EXCEPT for one square: here.
- SAT-solvers and IP-programs have been used but have not worked--- however, I don't think they were tried that seriously.
- Here are some thoughts I have had on the problem lately: here.
- 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.
Here is a quick approach, I am not able to pin down why it would not work.
ReplyDeleteSince 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?
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.
ReplyDeleteThe 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 :)
Results #9,#10,#11 are in conflict.
ReplyDeleteThe 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.
Unless I misunderstand this was proven in 1976 - http://en.wikipedia.org/wiki/Four_color_theorem
ReplyDelete@Bruce:
ReplyDeleteThe 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).
SKY: I don't see what the
ReplyDeleteproblem 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.
Okay, I want to pursue the first approach I outlined just a little bit longer.
ReplyDeleteLet 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?
@Neel, your approach would easily imply that 16x16 is 3-colorable.
ReplyDelete@GASARCH, why isn't the grid in #11 symmetric? Why is 21x9 4-colorable but not 9x21?
@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!
ReplyDeleteCould someone verify this solution?
ReplyDelete20022112200330023
00220022002200220
31133003311221132
13311331133113311
20022112200330023
20022002200220022
31133003311221132
13311331133113311
20022112200330023
02200220022002200
31133003311221132
31133113311331133
20022112200330023
02200220022002200
31133003311221132
13311331133113311
20022112200330023
@Ess: Look at the 5th and 6th rows of your so-called "solution":
ReplyDelete20022112200330023
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.
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:
ReplyDelete1. 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!
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.
ReplyDelete20022112200330023
ReplyDelete00220022002200220
31133003311221132
13311331133113311
20022112200330023
20022002200220022
31133003311221132
13311331133113311
20022112200330023
02200220022002200
31133003311221132
31133113311331133
20022112200330023
02200220022002200
31133003311221132
13311331133113311
20022112200330023
an attempt from Eric Purdy (too frantic to check!)
nope, not right
ReplyDeletedutch, saying 7x3 is in OBS2 means it is NOT solvable.
ReplyDeleteI'd like to reiterate Anonymous #8, the grid given has multiple discrepancies: 21x9, 21x10, 21x11, 21x12
Oh, Ok, that explains why I couldn't get any further.
ReplyDeleteI'm probably making a simple arithmetic mistake here, but when I went into the paper to see the argument for 7x3, I calculated
ReplyDeletez_{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?
Do I misunderstand the OBS or are you also interested in a 4-coloring of 21x10?
ReplyDelete120010130231144221101
111203323023004323414
403011221233201140214
012334030223303131422
102322001304014413203
043104332322420204114
313023024012310444033
030224212130342011312
334420413400241402421
231130402114131320243
BTW 22x10 and 23x10 are also 4-colorable (if my program doesn't have bugs).
ReplyDeleteJules, that's actually a 5-coloring.
ReplyDeleteHah, good catch :)
ReplyDelete12345678901234567
ReplyDelete1 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
@Anonymous:
ReplyDelete12345678901234567
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
21x10 is also shown as not solved, and has a smaller search space then 17x17. Would you be interested in its answer as well?
ReplyDeletein http://www.cs.umd.edu/~gasarch/BLOGPAPERS/17x17chart.pdf
ReplyDeletethe chart is not symmetric.
Check 10x21 vs. 21x10.
Same for 11x21 and 12x21.
This comment has been removed by the author.
ReplyDeleteuchiki86 - what about your rows 4 and 12
ReplyDeletehe most interesting part of the post
ReplyDelete-- Why 289?
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@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!
ReplyDelete@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?
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.
ReplyDeletei 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++.
ReplyDeleteany ideas?
What is the best shot rotation if your haste rating with ranged weapons is 1.72 and you are BM spec'd?
ReplyDeleteI'm pretty sure it's impossible.
ReplyDeleteSpecifically, 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
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 ?
ReplyDeleteWhat a nice way of putting things.
Thank you.
01230012301230123
ReplyDelete00000111122223333
01111122223333000
02222133320003111
03333100021113222
10123212332300301
11032221033210032
12301230130120123
13210203231030210
20231313002011312
21320320303101021
22013331200231130
23102302101321203
30312010212132320
31203023113022013
32130032010312102
33021001311202231
Previous Anonymous, you are wrong. At least test your proposed solution before posting it.
ReplyDelete01230012301230123
00000111122223333
01111122223333000
02222133320003111
03333100021113222
10123212332300301
11032221033210032
12301230130120123
13210203231030210
20231313002011312
21320320303101021
22013331200231130
23102302101321203
30312010212132320
31203023113022013
32130032010312102
33021001311202231
For Anon #35: If its impossible, how can you explain the "74 items rectangle-free set" in the OP ?
ReplyDeleteThe 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"Why 289?"
ReplyDelete17*17
To Anon: yeah, rite who's gonna keep count of "For Anon #35"
ReplyDeletewhat a joke.
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):
ReplyDelete0...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.
The chart had a typo which I have
ReplyDeletenow 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.
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
ReplyDeleteIt 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..).
ReplyDeleteWe 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.
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
ReplyDeleteexactly one of the following sets in OBS4: 19x17, 18x17, 17x17, the 17 x 17 grid must have a valid coloring.
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.
ReplyDeleteIt'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).
ReplyDeleteUsing this method I have a simple program that "proves" no solution, see here.
David Benson: Can you elaborate on your trivial "process of elimination" approach? I suspect you're making a silly mistake.
ReplyDelete@David:
ReplyDeleteRemember, 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.
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.
ReplyDeleteSassan, 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-".
ReplyDeleteSassan: It would be good to test your approach on 15x15 or 16x16, which do have solutions.
ReplyDeleteI 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.
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).
ReplyDeleteHere's a 74 RF set I generated with an IP solver in python. I haven't verified that it's the alternate form though.
ReplyDeletehuh ? is sassan's code widely available or how did anon run it on his computer ?
ReplyDeleteSassan,
ReplyDeleteWhy do you change three of the vertices, and not one? Changing three seems like you are more likely to introduce additional collisions.
Brian
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.
ReplyDeleteI found the coloring. There exists one. But i am unwilling to give away my solution for only 289.00.
ReplyDeleteI 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?
ReplyDeletewell, i wouldn't be too sure of either now. #60 anon must certainly be a great card player.
ReplyDeleteI've tried the greedy and brute-force coloring approaches too without any luck so far. :(
ReplyDeleteQuestion: 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
Suppose you have:
ReplyDeleteab
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.
whooops, reading your editted post i can see that i had the definition wrong.
ReplyDeleteI find the problem presentation confusing, and I would appreciate it if someone would verify whether or not I understand the correctly.
ReplyDeleteIf 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) ].
This comment has been removed by the author.
ReplyDeleteUm... 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@Neel:
ReplyDeletehere 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
Alexandru and Neel- the paper has a 3-coloring of 10x10.
ReplyDeletebill
@Alexandru, @gasarch: Thanks! The explicit colorings should come in very handy, and I'm all inspired again.
ReplyDeleteBy 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!
@neel The 17x17 grid can be 5-colored.
ReplyDeleteHas 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.
ReplyDeleteI 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.
ReplyDeleteThis comment has been removed by the author.
ReplyDelete@Brad: I see - nice! Did you work that out, or is it around in the blog post/paper/talk slides and I missed it?
ReplyDelete@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!
Well if anyone wants a good starting point.
ReplyDelete02231320323013110
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.
This comment has been removed by the author.
ReplyDeleteThis comment has been removed by the author.
ReplyDeleteMichael,
ReplyDeleteI think 4-Coloring 2 x n is trivial:
12
34
12
34
....
@neel
ReplyDeleteI constructed a 5-coloring of the 17x17:
14115523345324421
32355445114232225
25145411123345522
32414423225455135
42545342512354351
41152422443133552
54243124455432351
35552131341113324
55132144512221335
22222414335134531
31234254145511121
12441235544531542
11544555252335423
14254543512143144
53425252421323234
51211513411544312
23333333233512443
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.
ReplyDeleteFor what its worth I found this which only has 8 rectangles in it using simulated annealing on GPUs.
ReplyDelete00130231113223103
21310021323230310
03321322010103210
30311130101322220
32132113300210202
02323003201021113
13012223213311000
10133301221302302
21222010011332033
03203230321110231
12330212132002031
33002011132101323
21020200330313122
30203102210233021
30012312023020131
21101333232031201
11200123002123332
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@Brad: Woah, how do you come up with things like that? :)
ReplyDelete@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 :)
Esad: it's even more trivial than that :p
ReplyDelete01
01
01
01
01
..
..
..
@neel It's a secret, at least for now. :-)
ReplyDeleteI 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.
ReplyDeleteIntuitively, 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!
@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@Brad: Heh! Link to an explanation when it's ready for the public domain, will you? I'm just generally mystified. :)
ReplyDelete@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?
#35 has only 4 rectangles, nice one
ReplyDeletei'm interested in the algorithm used to create the grid
#37 not #35 :-)
ReplyDeleteSorry, 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.
ReplyDeleteThinking 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.
Miguel, a 10x10 is 3-colorable; see the pdfs in the OP.
ReplyDeleteThere 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.
ReplyDeleteI believe it's easy.
ReplyDelete1x1 -> 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....
Ruben, 8x8, 9x9, and 10x10 can all be done with 3 colors.
ReplyDelete#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.
ReplyDeletethere is no 17x17 solution.
ReplyDeletei 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.
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.
ReplyDeleteDude, the green background on your blog is killing me.
ReplyDeleteAm 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?
ReplyDeleteZAC- THANKS- you have found a typo in the paper---
ReplyDeleteI will fix soon.
bill gasarch
ZAC: I have fixed it. THANKS!
ReplyDeleteBill G.
I believe I have proven that a 17x18 grid is NOT 4-colorable. See this post for a reference.
ReplyDeleteSorry, 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).
ReplyDeleteAndre - 17x19 already known to be
ReplyDeletenot 4-colorable. See original paper
that is linked to
bill gasarch
Hi to everyone,
ReplyDeleteI'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 :)
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.
ReplyDeleteDear Gasarch,
ReplyDeleteThanks 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
@baz: Care to share the bruteforce code?
ReplyDelete@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@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@kanodonkey, no problem, the (embarrassingly simple) code for searching and backtracking I put here: http://www.sti2.at/~barryb/four_colour.zip
ReplyDeleteIt'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!
(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)
ReplyDeleteHello,
ReplyDeleteI 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
Ok,
ReplyDeleteI'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
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.
ReplyDeleteDoes it sound doable ?
for those interested, I just set up a place where everyone can put the best result he obtained + brief description of the method:
ReplyDeletehttp://linbaba.wordpress.com/17x17-challenge/
I hope to have nice chats about ways of attacking the challenge ...
Hello,
ReplyDeleteLet'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.
Hello People,
ReplyDeleteIs 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
Typo correction:
ReplyDelete"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
Hello Gasarch,
ReplyDeleteDid 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?
1) I have looked over your proof and I do not find it convincing.
ReplyDelete2) 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
JohnPaul,
ReplyDeleteI 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.
Hello Gasarch,
ReplyDeleteHere 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.
JohnPaul Adamovsky:
ReplyDeleteINNOCENT until proven GUILTY.
TRUE until proven FALSE.
Gasarch,
ReplyDeleteYou 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.
I am making good progress in my attempt to enumerate all possible Perfect 16x16 4-colourings so as to complete my proof.
ReplyDeleteSo 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
JohnPaul,
ReplyDeleteI'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
JohnPaul,
ReplyDeleteI think you deserve $289 just for the pure entertainment value of your posts. Thanks for brightening my day!
@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@Anonymous poster #133:
ReplyDeleteThe 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
Hello Michael,
ReplyDeleteThank 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
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.
ReplyDeleteThis is a much looser form than the one contained in my proof.
All the very best,
JohnPaul Adamovsky
Hello,
ReplyDeleteI 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.
Hello JohnPaul,
ReplyDeleteI 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
Hey Man,
ReplyDeleteI'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
Given c colors and m colums how many rows (n) can i produce without a rectangle?
ReplyDeleteAlgorithm:
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
Hello,
ReplyDeleteIn 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
Is this Challenge still up? How can I contact you, if I found the solution? How will you send me the money?
ReplyDeleteMartin Thoma- YES the challenge
ReplyDeletehas 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.
Well, I have no solution jet. I'm trying to find solutions to a simmilar problem and a friend sent me this link.
ReplyDeleteWhere can I find your Email-Adress?
You can google GASARCH to find my home page that has my email on it OR I can tell you now:
ReplyDeletegasarch@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.
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.
ReplyDeleteWhen 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.
Charlie Sheen, is that you?
ReplyDeleteAs of today, March 24, is the known information still accurate? That is, are the following problems still open?
ReplyDelete12x21
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 :)
Mizzao- YES they are still open.
ReplyDeleteI 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
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.
ReplyDeleteSlightly 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.
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.
ReplyDeleteAfter 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.)
Here is a colouring with 5 monochromatic rectangles, which shows that JohnPaul Adamovsky was wrong in his 15th of July 2010 post:
ReplyDelete11111222233334444
12222233334444111
13333244431114222
14444211132224333
12243143212431423
22143431424312341
21234112443413213
21324434211233431
21432321342131142
34321441312342213
33412432113212124
34231123144122431
32143324141241214
44321323423411324
43412314224321231
43214141321243342
42123412343124132
I couldn't stop laughing at JohnPaul Adamovsky's email. I'm sorry. There's no way that was a serious thing.
ReplyDeleteContinuing on what David Wagner said about SAT solvers, I also want to post here in case anyone finds my info useful or interesting...
ReplyDeleteI 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.
Bill,
ReplyDeleteI 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
The problem is solved- there IS a 4-col or 17x17 and of 18x18.
ReplyDeleteSee my Feb 8 2012 post.
I was curious about how far this work has come and I'm so happy to see this blog Dr. Gasarch!
ReplyDeleteThe 17 x 17 problem was SOLVED and we now know
ReplyDeleteexactly 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.