UPDATE: Problem HAS been solved. See Feb 8, 2012 post. There IS a 4-coloring of 17x17 and also of 18x18. Can also see my arXiv paper on grid coloring.
Long time readers may recall that 17x17 problem that I posted on Nov 30, 2009 here. I am sometimes asked if the problem is still open. Alas it is. Is the bounty on it still available. Alas it is. Some thoughts and experiences
- See this for a different take on it.
- When I wrote the post not that many people tried it seriously. Because of the post and because Brian Hayes picked up on it (see here) many people have worked on it seriously. This is good in that I now know that its hard, but bad in that its still unsolved.
- A High School Student wanted a formal contract before showing me his alleged solution. I told him that if he posted a comment with the coloring ON MY BLOG I would have to pay up and would do so gladly. His solution didn't work anyway.
- Do I still think that 17x17 is 4-colorable? The problem is that this is a finite problem. The fact that nobody has found a 4-coloring MIGHT mean there isn't one. But it might just mean there are very few of them.
- As a pessimist I think that 17x17 IS 4-colorable. Why is that? The following three problems are open: is 17x17 4-colorable? is 17x18 4-colorable? is 18x18 4-colorable? If 17x17 was NOT 4-colorable then the rest would NOT be 4-colorable with no additional work. We will not be that lucky. By the same reasoning I think 18x18 is NOT 4-colorable. (There are a few other grids where we do not know if they are 4-colorable but not many.)
- Will future faster computers help? Maybe, but there needs to be a math breakthrough, even a small one, as well.
- Will future Quantum Computers help? I doubt anyone will go to the expense of building a quantum computer for the 17x17 grid problem. And I doubt there will be general-purpose quantum computers.
- The following problem is inspired by my problem but has not gotten that much attention: How hard is the following: Given (n,m,c) and a partial rectangle-free c-coloring of nxm, can it be completed to a total rectangle-free c-coloring of nxm. Should be NP-complete but I have not been able to prove this I also haven't tried that hard- Maybe I'll get a bright High School Student to do it and get some free lunches out of it (see here).
- JohnPaul Adamovsky claimed that they had a proof that 17x17 was NOT 4-colorable and had comments on it on my blog here. I could not make sense of his proof. I suspect he no longer believes this since recent email from him describes an approach to finding a 4-coloring. He also made an offer that if I bought him some type of computer (he says which type) he will solve the problem. I have declined it; however, I offered to do a post on updated status of the 17x17 problem so he could make a comment on it offering it to others (I am doing that NOW). Note that if he posted on my older posts very few people would see it. He did not respond kindly to my offer; however, we'll see if he comments.
-
I gave a talk on grid colorings at an Algorithms and Theory of Computation Day that Zachos invited me to in New York.
A the end I had the following exchange with Lane Hemaspaandra who had also given a talk.
LANE: What does this have to do with Algorithms or Theory of Computation?
BILL: I could make something up but I respect you and the audience too much for that. The answer is NOTHING.
LANE: Then why are you giving a talk on it at Algorithms and Theory of Computation day?
BILL: Because Zachos invited me. You could ask why he invited me, but I think it is because he knows my parents live in the area so I would be a cheap date- no housing costs.
OTHER AUDIENCE MEMBER: Actually this material does have applications. This is part of Ramsey Theory and there is an entire website of applications of Ramsey Theory to Computer Science.
BILL (Thinking- there's ANOTHER one aside from mine? I should take a look at it) OH- that's good to know- what is the pointer to it?
OTHER AUDIENCE MEMBER: Its http://www.cs.umd.edu/~gasarch/ramsey/ramsey.html. Oh- that's you! (READERS- see here.)
BILL: YES, Ramsey Theory has had applications to computer science and that's great! However, I am not going to make the following incorrect claim: (1) Ramsey theory has had apps to CS, (2) The Grid problem was inspired by Ramsey Theory. Hence (3) The Gird problem has apps to CS. That would be bad logic.
Being a fellow "g17" enthusiast, I'm glad to see an update.
ReplyDeleteFor those interested in joining the hunt: good luck, have fun. It's a really tough problem, but a really fun one at the same time. I had many "amazing" ideas in the course of working on a solution, but all of them found eventual dead ends. I ended up with a stack of proofs that "Graph with property X is not 4-colorable". Many of these are obvious after a little thought, others can also be seen in Beth Kupin's thorough work [1].
Unfortunately, visible attention to the problem waned and real life caught up with me as well. I still have one of those "amazing" ideas on a back burner somewhere. It'd be fun to prove that one wrong as well. =P
Anyway, many thanks to Bill for occupying many hours my advisor would have happily dedicated elsewhere. Casual problem solving has always kept me sane during busy times and g17 definitely hit the spot.
[1] http://www.cs.umd.edu/~gasarch/BLOGPAPERS/bethk.pdf
This discussion on TCS-SE might be of interest: http://cstheory.stackexchange.com/questions/791/grid-k-coloring-without-monochromatic-rectangles
ReplyDeleteHi, I've been working on this for a while, and would like someone to help me verify an observation:
ReplyDeleteThe two 74s that Beth Kupin has identified are indeed permutations of each other. By inserting rows GHIJ before the row C and inserting column 2 before column 1, we end up where we started, but the special symbols are inverted.
If this is the case, and Beth's proof otherwise holds up, the 74 is unique, which means we have the first 74 (or 73) cells of a solution, if one exists.
@Emmel: If you could share with us which classes you have ruled out, that would be great!
ReplyDeleteGASARCH Remarks: "And I doubt there will be general-purpose quantum computers."
ReplyDeleteHmmm. It seems to me that the doubts that GASARCH's remark expresses might easily be over-interpreted.
First, from a systems engineering point-of-view, there's no such thing as a "general-purpose computer" because every physical computer (classical or otherwise) ends up being optimized for some-purpose-or-other.
Modern informatic environments have therefore evolved into adaptive "clouds" of linked computing devices, sensors, and actuators ... and this adaptive cloud aspect is strikingly evident even in single, isolated laptop computers.
So its best to keep in mind that there *are* STEM roadmaps under which many job-creating enterprises, and essentially every campus, will (reasonably soon) deploy many thousands of desktop devices whose state-space is quantum-coherent and strongly entangled.
So yes, under some STEM roadmaps, the global informatic state-space is destined to include very substantial quantum-coherent elements ... perhaps mighty soon.
The broader point about STEM roadmaps is that every robust academic discipline has more than one of them. Evaluated by a multi-roadmap robustness criterion, it's becoming clear that quantum information theory is among the most robust, and has the broadest informatic span, of all STEM disciplines.
In summary, we shouldn't underestimate the capacity of quantum information theory to surprise us ... that's what systems engineers think, anyway.
With respect to the 17X17 problem, it might be useful to take a look at Minkowski's "Taxicab Geometry".
ReplyDeleteTo carry things a step further:
ReplyDeleteArrange the coordinates of the corners of rectangles in an ordered square: x,y+b,z - x+a,y+b,z
x,y,z - x+a,y,z
Where x and y are normal Cartesian coordinates and z is the color coordinate.
I found a great application of this problem: teaching intractability to non-CS kids. I've been using the semi-game found on this site:
ReplyDeletehttp://www.martinschweitzer.com/squaregame.html
I modified it a bit and added a 17x17 grid. I let the kids start solving the smaller grids - they usually do it greedily. Then, by the time they get to the 17x17 grid, they find that the greedy method totally breaks. Then, we can talk about intractability, hardness, and algorithms. It's a really great tool and the students are motivated by the $289.
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.
@JohnPaul, will you first admit that your previous proofs of 'impossibility' were wrong? Without that, your self-aggrandisement rings hollow, as you were equally certain of your previous proofs. The SCIENTIFIC way to go about this with dignity is to first retract your previous claims.
ReplyDeleteNow, the 3-colour 10x10 has approx. 5.15*10^47 raw alternatives, and that goes down to 6.5*10^33 if you remove the obvious symmetries. How is that even indicative of anything when we're talking about a problem of the magnitude of 10^143?
If going through the 3-colour 10x10 takes your algorithm 8 hours on your computer, it will take it 3.99*10^110 HOURS to go through the 4-colour 17x17. No amount of extra processing power with current technology will be enough for your algorithm to solve this problem while we're still around to see the result.
You know what, your result on the 3-colour 10x10 is indeed indicative. It indicates that your algorithm is way too slow for this problem. You need to speed it up about 10^100 times to get anywhere. A 24-core machine will get you only 1 or 2 of those orders of magnitude. What do you intend to do for the other 98?
Was the above a misquote of a Bible passage or a correct quote of a 2001 Romance/Drama?
ReplyDeleteKamouna might have a new kindred spirit.
ReplyDeleteAlexandros Marinos,
ReplyDeleteIt seems like you have a mild case of Down Syndrome. Your Nike's won't help you when you bring them to a "Nuclear Arms Race". You are so completely out of your league in this arena, and the fact that you are ignorant of it, is going to make this no-contest-victory quite unremarkable for me.
When I've just reduced a search space by 10^49, it will make my algorithm that much more powerful than all others before it. When your numbers are based on worthless anecdotes, keep them in your head.
Simulated-Annealing completely ignores a computer's ability to keep records. It is the fat-lazy-slob's algorithm. The Intelligent-Locus-Swarm algorithm, which I published documentation on, will mutilate any kind of record-free approach.
As for my initial impossibility proof: why didn't you bless us with your mediocrity as a form of PEER-REVIEW when it was fresh. Without peer review, there is no SCIENTIFIC-COMMUNITY. A turd stating the obvious about old-work is still very much, a turd.
Now, you will read the entirety of my Proof-Of-Concept documentation, and realize that it finds the first perfect coloring in seconds, running on a single thread. You will also read the text-book-stock documentation of DeepSearch.c, which isolates the 10 best 5x5 Boggle boards for TWL06 over night on a quad-core.
That's who I am, and you're nothing. The instant you decided not to READ my work, is the instant that you showed up DEAD-ON-ARRIVAL.
READ, READ, READ, THINK, THINK, and then write your own program, and we'll compare the performance. I will HUMBLE you, and if that doesn't work, I will PUBLICLY-HUMILIATE you.
You think you're CLEVER, think again, pal.
All the very best,
JohnPaul Adamovsky
PS - I need you for NOTHING.
When I write a comment, it should really be posted, without having to coerce Gasarch into posting it.
ReplyDeleteAll the very best,
JohnPaul Adamovsky
To speak in the language of JohnPaul, "put up or shut up". "Solving" an already-solved problem and talking big is worthless without something to back up your bravado. If your technique works, prove it. Provide the 17x17. Anything else from you is meaningless posturing.
ReplyDeleteIf you reply to this with insults or bluster or rant-like comments about nuclear arms races, I will simply take that as an acknowledgment that you admit that you have nothing more than hot air to contribute at the moment.
Oh boy, this is fun. I didn't need to peer review your previous claims, as our host on this blog did when he told you 10x10 3-colourings exist. What did he get for his kindness? Abuse from you. Same as you did from me when I showed you why your algorithm is too slow. And now you spin on a dime and manage to write a program to produce 10x10 3-colourings. Congratulations. Since you're so good, why don't you send us some real results so we can put on the leaderboard here? (http://linbaba.wordpress.com/17x17-challenge/) Oh, I forgot, you have no real results, but you can write walls of text.
ReplyDeleteAlexandros Marinos said:
ReplyDelete"Hi, I've been working on this for a while, and would like someone to help me verify an observation:
"The two 74s that Beth Kupin has identified are indeed permutations of each other. By inserting rows GHIJ before the row C and inserting column 2 before column 1, we end up where we started, but the special symbols are inverted.
"If this is the case, and Beth's proof otherwise holds up, the 74 is unique, which means we have the first 74 (or 73) cells of a solution, if one exists."
-----
Alexandros, you are correct! Beth's two 74s are identical under the permutation you describe.
This comment has been removed by the author.
ReplyDeleteSeems like one thing hindering the efforts to solve this problem is a way to identify unique family of grids. Where a family is a set of grid that through any rotation, color rotation, or row/column translation that doesn't change the number of (or lack of) single color rectangles. So:
ReplyDeleteSorry, not sure how to get a fixed font.
======(swap = (swap =(rot == (rot
======rows) = cols) =colors)= 90 deg)
0 0 1 = 1 3 1 = 3 1 1 = 0 2 2 = 1 1 0
1 3 1 = 0 0 1 = 0 0 1 = 1 1 2 = 2 1 2
1 0 2 = 1 0 2 = 0 1 2 = 1 2 0 = 0 2 2
I propose sort by row, then by column. Hrm, that still leaves mirrors, rotations, and color rotations.
Can anyone think of a way to reduce any grid to a unique grid that represents the family so we can compare equivalent grids?
That way we can avoid burning CPU cycles on grids that have already been used as seeds.
Once we have that people could share databases of the grids they find.
For those who have written solvers. Any estimate on CPU time for 16x16? What language did you use?
From my reading it seems like 16x16 grids are at (barely) feasible to generate. Seems like a few 1000 16x16 would be a particularly nice seeds for the various search algorithms to attempt a 17x17 from. If that's impractical maybe a distributed client could help generate the 16x16s or if necessary 15x15s.
"And I doubt there will be general-purpose quantum computers."
ReplyDeleteHey man I thought computer scientists were supposed to talk about stuff they could prove. You're starting to sound like a physicist ;)
Dave, you're on a complexity blog! -- When you can't prove it, conjecture it and count it good! ;)
ReplyDeleteDoes anyone know how many rectangle free sets with more than 72 positions exist? Does a generator for these exist? If you don't know how many of these sets exist, can you give me a upper bound?
ReplyDeleteFinally started to make some progress on this one.
ReplyDeleteThis intersection rule has proven useful:
If m is the number of same colored spots on a row on a nXn grid, then the maximum number of spots on the m columns crossing at those spots is m+n-1.
Back of the envelope calculation for 20X20 Grid:
ReplyDelete20X20 Grid = 400 points
400 points divided into 4 color sets = 100 pts./set
100 pts. = 5pts./row
5 pts./row = (5 times 4) divided by 2 = number of ordered intervals/row = 10 intervals/row
10 intervals/row times 20 rows = 200 required intervals
On the other hand:
20 pt. line = (20 times 19) divided by 2 ordered intervals = 190 available intervals
Not enough available intervals.
Changing the distribution doesn’t seem to help:
Changing a 5 pt. row to a 4 pt. row saves 4 intervals – but we then have to create a six pt row which adds 5 intervals.
Same calculation for 18X18 Grid indicates there should be a surplus of 9 available intervals.
But:
The feeling is we may be using up the excess intervals to avoid conflicts and maintain an even distribution between rows and columns of the same color and/or the cumulative effect of adding additional colors.
A curiously difficult problem.
The intersection rule should have read:
ReplyDeleteIf m is the number of spots colored A on a row on a nXn grid, then the maximum number of spots colored A on the m columns crossing at those spots is m+n-1.
Here is a "potential" choke point for 18X18 grids where the number of spots of each of the four colors is evenly distributed by row:
1. Color A uses 144 of a possible 153 intervals.
2. Color B uses 135 intervals used by A and the nine intervals not used by A.
3. Color C uses 126 intervals used by A and B, 9 intervals not used by A and 9 intervals not used by B.
4. Color D has to use 126 intervals already used by A, B, and C?
It takes 6X18 or 108 intervals to correctly place 4 spots of one color on each of the 18 rows.
For an even distribution by row, we
need to color an additional 9 spots for each color repeating at least 18 intervals.
It only takes one set of 10 intervals used by all four colors to lock out 14 spots from being correctly colored.
We may have some wiggle room by going to an uneven distribution.
The general idea is that there may be unavoidable sets which are also mutually exclusive.
Hi,
ReplyDeleteIn your 17x17advice.pdf document ("Some brief thoughts on 17x17") you say:
"... Is there a rectangle free subset of 5x17
which has 5 elements in each column? There is. However, **there is only one** (up to perms of columns and rows). Here it is:
44444------------
4----4444--------
4--------4444----
-4---4---4---44--
--4---4---4----44
..."
But I found another one that seems not to be "isomorphic":
44444------------
4----4444--------
4--------4444----
-4---4---4---44--
-4----4---4----44
The coloring with four 1,2,3 cells in each row is:
44444312213213231
41111444422333223
43232123344442111
24333411141324422
34223343224111144
And another one with an "empty" column :
44444------------
4----4444--------
4--------4444----
-4---4---4---44--
--4---4---4---44-
44444123313212213
41111444423323322
41233332244442111
34322411141234432
33432243224111441
Great, Thanks.
ReplyDeletecan you get ALL non-isom proper 4-colorings of 17x5
that have 5 R's in each column? If so this might help
FIND a coloring of 17x17 OR show that NONE exist.
I think there are too many of them ...
ReplyDelete... but I'll start with the easier task of enumerating the non-isom 1-colored rectangle free 17x5 "skeleton" grids containing 5 R's in each column, then eliminate those who don't allow a valid 4-coloring with 4G, 4B, 4Y in each column.
... there are 66, 17x5 non isom rectangle free "skeleton-grids" having 5 Rs in each row.
ReplyDeleteAll of them allow a valid 4-coloring with 5R,4G,4B,4Y in each row.
Any idea on how to use them ???
... and there are 84 17x5 rectangle free "skeleton" grids with 5Rs in each row.
ReplyDeleteAll of them allow a valid 4-coloring with 5R, 4G, 4B, 4Y in each row.
1) Are you saying there are 66 NON-ISOM rect free
ReplyDeletesubsets of 17x5, and 84 TOTAL (including ISOM ones?)
(All of which can be extended to full colorings.)
2) If so then the next thing to do would be to see which of the 84^2 ways to form a rect free
set of 17x10 that have the property are really rect free.
3) Then see which 17x15 are...
4) the remaining 2 rows are easy- try all possibilities.
5) When DONE then you have ALL Rect Free sets of
17x17 that have the property.
6) (This may be the hard step) See which of those
can be extended to a full coloring.
SEE NEXT ITEM for another approach
7) Rather than get all possible RECT FREE SETS
you can try to get all possible COLORINGS-
you say that each of your rect free sets of
17x5 can be extended to a full coloring of
17x5. Can you get ALL colorings?
8) The UPSHOT of all this would HOPEFULLY be
to FIND A COLORING. However, if everything you say is correct and you show that NONE of the
rect free sets of 17x17 that you obtain can be
extended then you will get that 17x17 is
NOT 4-colorable, also worth knowing.
... some fixes:
ReplyDeleteA) "66" are the 17x5 rectangle free non-isom "skeletons" i.e. 17x5 rectangle free grids filled only with one color (**BUT** I found an ERROR in the enumeration routine, so the correct value is greater than 66, but less than 124 ... still working on it)
B) "84" are the 17x4 rectangle free non-isom "skeletons" (but the value is not correct due to the same problem on the enumeration routine ... still working on it)
About your answer:
*** 1) I think that there are much more ISOM variants of the 17x5 "skeletons" (every valid permutation of the columns give one) ... however I'm still interested in checking how many full non-isom coloring can be obtained from a single non isom 17x5 (or 17x4) skeleton.
*** 2) I think that checking what pairs of skeletons (both 17x5 and 17x4) are compatible up to columns swap can be useful, but I think unfeasible (see point 1).
*** 3) there are no valid 17x8 "skeleton" grids with 5Rs in each row.
*** 6) ... I agree with you ... (I tried to solve the 17x17 rectangle free grid filled with 74 REDS without success)
*** 7) ... still working on it (at least I'll try to get all non-isom full coloring extensions) ...
If I make some progress and get the exact count of the non-isom 17x5 skeletons, I'll post a new comment.
That there are NO 17x8 RFS with 5 R per row is VERY INTERESTING- might help to cut down the number of possible
ReplyDeletelarge RFS's of 17x17 there are and hence cut down what to look at.
(OH- This is BILL GASARCH even though it will show up a
anonymous- sorry about that).
A question regarding the colors count in a 17x17 valid 4-coloring (perhaps I missed the information in the linked papers).
ReplyDeleteWhich of these configurations (if any) have been proved to be impossible?
74 74 71 70
74 73 72 70
74 73 71 71
74 72 72 71
73 73 73 70
73 73 72 71
73 72 72 72
I do not understand your notation, however, no
ReplyDeleteconfigs have been ruled out. I am sure that some
could be easily- with the help of a program.
It might be more efficient to email me directly and
have me email you directly if you have more thoughts-
my email is gasarch@cs.umd.edu but I don't know yours.
Marzio - We know from Beth Kupin's work that all 73's can be extended to 74's, so you can reduce your scope.
ReplyDeleteeg:
a 73-72-72-72 can always be turned to a 74-72-72-71.
a 73-73-73-70 can become either a 74-73-72-70 or a 74-73-73-69.
This may or may not help depending what you want to do with the configurations
@Alexandros: thanks.
ReplyDeleteUsing a SAT solver I noticed an odd property.
1) find a 2-coloring of a 16x16 grid that has no *** 3x3 *** monochromatic rectangle;
2) pick this grid as the high-bits of the 4-coloring of a 16x16 grid, and run the solver;
If an entry in the 2-colored grid is 0 then the corresponding entry in the 4-coloring must be 0 or 1; if an entry in the 2-colored grid is 1 then the corresponding entry in the 4-coloring must be 2 or 3.
3) the SAT solver quickly (2 secs) finds a valid 4-coloring of the 16x16 grid ... and a 4-coloring of a 17x16 grid (the added row is without constraint on the high bits)
... obviously the solver hangs if I add another colunm (17x17).
We know from Ramsey theory that there is no 17x17 2-colored grid without monochromatic 3x3 rectangles.
So a possible way to prove that no 17x17 4-colored and rectangle free grid exists, is by contraddiction: find a constructive method to build a 17x17 2-colored grid without 3x3 monochromatic rectangles starting from the 4-colored one (without 2x2 monochromatic rectangle).
Alas I'm not an expert of Ramsey theory ... hoping that someone else solves this nightmare!
(P.S. obviously I think that there is no valid 4-coloring :-))))
... waiting (in vain) for the SAT solver I made an "artistic" grid with 74 zeroes: http://www.fractalmuse.org/grid17x17/artistic74.jpg ... it belongs to a new artistic movement called "the 17x17 art" :-)
ReplyDelete... and another highly symmetric 74s ....
ReplyDeletehttp://www.fractalmuse.org/grid17x17/art74symmetry.jpg
I've been counting the total number of unique solutions for arbitrary nxm grids here: http://www.jasondavies.com/17x17/
ReplyDeleteUnfortunately 5x5 has eluded me so far, due to lack of RAM. :)
Ongda: suppose you have an enumeration of non isom 17x5 skeleton grids containing 5 Rs in each column + an unique 74 skeleton grid that - as proved by Beth - can be used as valid starting grid. Have you any idea on how to merge the 17x5 skeleton grids in the 74 one?
ReplyDeleteOngda appears to be a spambot, as the text is copied from an earlier comment by Marzio. :)
ReplyDeleteThanks for the catch Esaj, I removed Ongda's post. These spambots are getting clever.
ReplyDeleteHere are some more 4-colourings of 17×17 with 3 rectangles. These are different from Alexandros’ grid (see http://linbaba.wordpress.com/17x17-challenge/). I fixed the first 3 rows from Rohan Puttagunta’s solution and used a version of simulated annealing for the remaining rows.
ReplyDelete11111222233334444
12222233334444111
13333244431114222
41234313223141243
42143342321321421
21234142342413312
24321124143143421
32134424112312234
14344211132224333
23414231424132413
31442324131423142
34321441324211142
22143113244233134
31243431413242321
43412412343214231
13412143212341324
44321312411432314
11111222233334444
12222233334444111
13333244431114222
43241321323241431
24123124312341342
31432112442342134
34123342124123124
33241143141422342
21432443113213421
44123413241232231
42314313422311243
22314134244123431
14444211132224333
41432334221431312
23241412414133213
24113231423412413
32314421311432124
Just for fun, here is a solution with 4 rectangles that is composed from 16 4×4 Latin squares. It turns out that solutions of this form are quite easy to find. Looks like JohnPaul Adamovsky was right after all, maybe he is a genius. See his 10th of July 2010 post: http://linbaba.wordpress.com/17×17-challenge/
4312|1342|2143|2413|1
2134|2134|3421|1324|1
3421|4213|4312|3241|1
1243|3421|1234|4132|1
———————
1243|1342|4312|1324|2
3421|2134|1234|2413|2
4312|3421|3421|3241|2
2134|4213|2143|4132|2
———————
1243|2134|2143|3241|3
4312|4213|1234|1324|3
2134|3421|4312|2413|3
3421|1342|3421|4132|3
———————
1243|4213|3421|2413|4
4312|2134|4312|4132|4
3421|3421|2143|1324|4
2134|1342|1234|3241|4
———————
4444|2222|1111|3333|1
I never saw a 74R+74G rectangle free skeleton, so I post one just for curiosity.
ReplyDeleteI found many of them, but all *cannot* be expanded to a valid 4-coloring (rejected by SAT solver).
12-2-21111--2--2-
21-2--1--211-2-12
-21---12---2111-2
2--12--1--12-1-21
2---1-221--12-1-1
222--1---12-1--11
11122-2---2-----1
1--1-22--2-2--11-
12--1-2-2-1-12---
1---21--2--121--2
-12122-21---12---
-12-1-2--1---1222
-21-21--121---2--
2-11-2--21-1--2--
--1-1--1--222221-
-122-1-12--2--1--
---11112222----2-
Merry Christmas Everybody!
The above Unknown poster (December 21st, 2011) is Dmitry Kamenetsky.
ReplyDeleteMarzio, I have found some 74R+74G rectangle-free skeletons earlier in http://apps.topcoder.com/forums/?module=Thread&threadID=657136
Cheers,
Dmitry
@Dmitry: Ok, I didn't see them! (I checked them but none can be expanded to a valid 4-coloring) :-(
ReplyDeleteTHE PROBLEM HAS BEEN SOLVED! There is a 4-coloring of 17x17 and
ReplyDeleteeven if 18x18. See my Feb 8, 2012 post.
THE PROBLEM HAS BEEN SOLVED! There is a 4-coloring of 17x17 and
ReplyDeleteeven of 18x18. See my Feb 8, 2012 post.