tag:blogger.com,1999:blog-3722233.post1571593567185565391..comments2017-04-28T10:57:44.459-04:00Comments on Computational Complexity: The 17x17 challenge. Worth $289.00. This is not a joke.Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.comBlogger158125tag:blogger.com,1999:blog-3722233.post-3286275833287591922012-11-10T12:27:21.298-05:002012-11-10T12:27:21.298-05:00The 17 x 17 problem was SOLVED and we now know
exa...The 17 x 17 problem was SOLVED and we now know<br />exactly which grids are 4-colorable (other grids<br />had to be figured out also). <br /><br />The lastest version of the paper is on my website<br />and has all of the results. GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-81874349470585586902012-11-10T12:21:57.736-05:002012-11-10T12:21:57.736-05:00I was curious about how far this work has come and...I was curious about how far this work has come and I'm so happy to see this blog Dr. Gasarch! Brett Jnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-14311576188131205182012-02-08T08:32:14.437-05:002012-02-08T08:32:14.437-05:00The problem is solved- there IS a 4-col or 17x17 a...The problem is solved- there IS a 4-col or 17x17 and of 18x18.<br /><br />See my Feb 8 2012 post.GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-61003642168863297292012-02-07T17:19:03.822-05:002012-02-07T17:19:03.822-05:00Bill,
I really can't wait to see the perfect ...Bill,<br /><br />I really can't wait to see the perfect 17x17 4-coloring. I wonder if it even fits into my 4x4 grid pattern.<br /><br /><br />All the very best,<br /><br />JohnPaul AdamovskyJohnPaul Adamovskyhttp://www.pathcom.com/~vadco/cwg.htmlnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1553970513290484042012-01-23T07:24:35.671-05:002012-01-23T07:24:35.671-05:00Continuing on what David Wagner said about SAT sol...Continuing on what David Wagner said about SAT solvers, I also want to post here in case anyone finds my info useful or interesting...<br /><br />I looked into this problem for a semester as my undergraduate senior project.<br /><br />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).<br /><br />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. <br /><br />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...<br /><br />I've another approach I looked into was using genetic algorithms, but it seems to be less effective than SAT.Paul Varoutsoshttp://www.blogger.com/profile/14796605592311728130noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-30818984876277071582012-01-20T07:46:20.009-05:002012-01-20T07:46:20.009-05:00I couldn't stop laughing at JohnPaul Adamovsky...I couldn't stop laughing at JohnPaul Adamovsky's email. I'm sorry. There's no way that was a serious thing.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-71044379887016069922011-12-21T02:05:12.433-05:002011-12-21T02:05:12.433-05:00Here is a colouring with 5 monochromatic rectangle...Here is a colouring with 5 monochromatic rectangles, which shows that JohnPaul Adamovsky was wrong in his 15th of July 2010 post:<br /><br />11111222233334444<br />12222233334444111<br />13333244431114222<br />14444211132224333<br />12243143212431423<br />22143431424312341<br />21234112443413213<br />21324434211233431<br />21432321342131142<br />34321441312342213<br />33412432113212124<br />34231123144122431<br />32143324141241214<br />44321323423411324<br />43412314224321231<br />43214141321243342<br />42123412343124132Unknownhttp://www.blogger.com/profile/13373007166638900841noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-30979582038046058242011-05-16T02:23:05.270-04:002011-05-16T02:23:05.270-04:00I think I've a dead end with using SAT. I tho...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.<br /><br />After more experimentation, the 2-bit encoding seems superior to the 4-bit 1-hot encoding. I also experimented with an optimization. For a mxn grid, given any solution, we can permute the rows and columns arbitrarily, leading to m!n! other solutions. Therefore, without loss of generality, we can focus on colorings where the rows are in lexicographic order, and where the columns are also lexicographically ordered. My hope was that this might reduce the search space.<br /><br />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.)<br /><br />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.<br /><br />10x10: 1.23s 2.07s<br />11x11: 3.86s 4.75s<br />12x12: 9.50s 9.47s<br />13x13: 31.57s 23.42s<br />14x14: 643.39s 1103.32s<br />15x15: ? ?<br /><br />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.<br /><br />(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.)David Wagnerhttp://www.cs.berkeley.edu/~daw/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-79132847254356665182011-05-15T13:15:06.362-04:002011-05-15T13:15:06.362-04:00I've been experimenting with applying a SAT so...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.<br /><br />Slightly more details: I experimented with two encodings into SAT, based upon how we encode the color of each grid square: (1) each color is encoded in 2 bits, so the 4 colors are encoded as 00, 01, 10, 11, (2) a "one-hot encoding" into 4 bits, so the 4 colors are encoded as 0001, 0010, 0100, 1000. On smaller puzzles, encoding into 2 bits seemed to work better than a one-hot encoding. I use STP as a wrapper around MiniSAT (STP has a more convenient input syntax). For each rectangle, I generate a constraint saying that it is not the case that all 6 pairs of corners are same-colored (the not of an and of 6 terms, where each term says that 2 corners have the same color).<br /><br />I just thought I'd document my approach for others to benefit from.David Wagnerhttp://www.cs.berkeley.edu/~daw/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-73632039386970163652011-03-24T23:45:07.470-04:002011-03-24T23:45:07.470-04:00Mizzao- YES they are still open.
I think people ha...Mizzao- YES they are still open.<br />I think people have tried IP but I am not sure since most of the info I get is random blog postings which are short.<br /><br />I recently did an UPDATE on the problem post (punchline- 17x17 still open as are the four you mention).<br />You could post a comment there where people will see it and ask around.<br /><br />GREAT that you are trying this!<br /><br />GASARCHGASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-28518427553384504872011-03-24T18:47:53.443-04:002011-03-24T18:47:53.443-04:00As of today, March 24, is the known information st...As of today, March 24, is the known information still accurate? That is, are the following problems still open?<br /><br />12x21<br />17x17<br />17x18<br />18x18<br /><br />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 :)mizzaohttp://www.blogger.com/profile/10877560771229606755noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-3145871162823284412011-03-22T15:01:20.212-04:002011-03-22T15:01:20.212-04:00Charlie Sheen, is that you?Charlie Sheen, is that you?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-87067500059684471442011-03-19T09:15:13.827-04:002011-03-19T09:15:13.827-04:00I've successfully enumerated every possible pe...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.<br /><br />When my work is long, it can be more accurately described as:<br /><br />RIGOROUS, EXACT, DETAILED, CONSISTENT, THOROUGH, CONSCIENTIOUS, <br />METICULOUS, COMPREHENSIVE, PAINSTAKING, RELENTLESS, PROVEN, UNCOMPROMISING, DILIGENT, SYSTEMATIC, DEDICATED, CONVICTION, VIGILANT, METHODICAL, TESTED, DISCIPLINED, ALL THE VERY BEST, PERFECT.<br /><br />In one word: SCIENTIFIC.<br /><br />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.<br /><br />My program finds the first perfect coloring is seconds, and enumerates all of them, over night.<br /><br /><a href="http://www.pathcom.com/~vadco/Proposal-Email.zip" rel="nofollow">Proposal-Email.zip</a><br /><br />Explain this:<br /><br />A Perfect 10x10 3-Coloring - <br /><br />0|000|111|222|<br />-?---?---?---?-<br />0|211|221|020|<br />0|212|012|101|<br />0|221|100|211|<br />-?---?---?---?-<br />1|012|120|002|<br />1|022|201|110|<br />1|101|212|200|<br />-?---?---?---?-<br />2|102|001|021|<br />2|120|102|102|<br />2|110|020|210|<br />-?---?---?---?-<br /><br />Each row-col has a (3, 3, 4) color distribution, but the square as a whole, has the following color spread:<br /><br />34 0's<br />34 1's<br />32 2's<br /><br />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.<br /><br />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.<br /><br />Bottom line, 864 configurations are found using the above template, and 864 = 3^3x2^5, there are many less unique configurations.<br /><br />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.<br /><br />I consider myself something of an Oracle-Machine-Automaton, so I need Gasarch for NOTHING.<br /><br />I will use the Proof-Of-Concept template to solve the 17x17 problem in my own time, and share the solution with Gasarch, NEVER.<br /><br /><br />All the very best,<br /><br />JohnPaul Adamovsky<br /><br />PS - Gasarch, you have been weighed, you have been measured, and you have been found wanting.<br /><br />PPS - If you want to know who I am, look me up on Google, you genius. Then READ.<br /><br />PPPS - You are now playing "THE MANS GAME". Investigate and produce something of value, or finish crumbling.JohnPaul Adamovskyhttp://www.pathcom.com/~vadco/deep.htmlnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-67794836113206480782011-03-10T12:13:19.784-05:002011-03-10T12:13:19.784-05:00You can google GASARCH to find my home page that h...You can google GASARCH to find my home page that has my email on it OR I can tell you now:<br /><br />gasarch@cs.umd.edu<br /><br />(My homepage is also linked to from<br />the side of the blog.)<br /><br />GOOD LUCK! I still very much want the problem to be solved.GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-50148988883690516502011-03-10T12:09:02.009-05:002011-03-10T12:09:02.009-05:00Well, I have no solution jet. I'm trying to fi...Well, I have no solution jet. I'm trying to find solutions to a simmilar problem and a friend sent me this link.<br /><br />Where can I find your Email-Adress?Martin Thomahttp://www.blogger.com/profile/13629221699214248094noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-55155299452097497952011-03-10T11:21:03.539-05:002011-03-10T11:21:03.539-05:00Martin Thoma- YES the challenge
has not been solve...Martin Thoma- YES the challenge<br />has not been solved and is still<br />worth $289.00.<br /><br />You email me the solution I will<br />mail you a check for the $289.00.<br /><br />I will then post about it so people<br />will know that it has been solved.<br />(You also have a blog so you can do the same if you wish.)<br /><br />If this mechanism does not work then email me and we'll work out something that does.GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-54206895229430780672011-03-10T11:11:44.472-05:002011-03-10T11:11:44.472-05:00Is this Challenge still up? How can I contact you,...Is this Challenge still up? How can I contact you, if I found the solution? How will you send me the money?Martin Thomahttp://www.blogger.com/profile/13629221699214248094noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-45573917017411865562010-10-16T01:40:55.566-04:002010-10-16T01:40:55.566-04:00Hello,
In this simple calculation, the 10x10 3-Co...Hello,<br /><br />In this simple calculation, the 10x10 3-Colouring search-space will be reduced to 9 independent 3x3 squares, each with significantly less colour combinations than 3^9. The result is like reducing a search of Earth's surface to searching 6 square millimeters.<br /><br />Total Search Space = 3^100 = 5.154 x 10^47<br /><br />Reduced Search Space = (26*6) x (204*6)^6 x (575*6)^2 = 6.244 x 10^27<br /><br />= 156 x 3362702965323595776 x 11902500 = 6243833238983199400919040000<br /><br />(Reduced Space) / (Full Space) = 1.211 x 10^-20<br /><br />Analogy: Search the entire surface of the world for a missing Colorado Potato Beetle.<br /><br />Total surface area of Earth = 4 * Pi * (6400KM)^2 = 514718540KM^2<br /><br /><br />Using search-space reduction logic akin to this algorithm:<br /><br />The beetle will be found after searching an area of this size:<br /><br />Reduced Search Area = (1.211 x 514718540KM^2) / (10^20) = (6.233 x 10^-12)KM^2<br /><br />(1KM)^2 = (10^6)M^2 = (10^12)mm^2<br /><br />Search Area = 6.233 mm^2<br /><br /><br /> # - Map - Char<br />| 0| - |000| - | 0 |<br />| 1| - |001| - | 1 |<br />| 2| - |002| - | 2 |<br />| 3| - |010| - | 4 |<br />| 4| - |011| - | 5 |<br />| 5| - |012| - | 6 |<br />| 6| - |020| - | 8 |<br />| 7| - |021| - | 9 |<br />| 8| - |022| - | 10 |<br />| 9| - |100| - | 16 |<br />|10| - |101| - | 17 |<br />|11| - |102| - | 18 |<br />|12| - |110| - | 20 |<br />|13| - |111| - | 21 |<br />|14| - |112| - | 22 |<br />|15| - |120| - | 24 |<br />|16| - |121| - | 25 |<br />|17| - |122| - | 26 |<br />|18| - |200| - | 32 |<br />|19| - |201| - | 33 |<br />|20| - |202| - | 34 |<br />|21| - |210| - | 36 |<br />|22| - |211| - | 37 |<br />|23| - |212| - | 38 |<br />|24| - |220| - | 40 |<br />|25| - |221| - | 41 |<br />|26| - |222| - | 42 |<br /><br />This is the reduced search-space template:<br /><br />0000111222<br />0AAABBBCCC<br />0AAABBBCCC<br />0AAABBBCCC<br />1DDDEEEFFF<br />1DDDEEEFFF<br />1DDDEEEFFF<br />2GGGHHHIII<br />2GGGHHHIII<br />2GGGHHHIII<br /><br />Each 3x3 letter square is treated as an independent unit. 'E' and 'I' will have the most colour-combinations. 'A' will only have 156.<br /><br />It is important to note that such basic enumeration can make an NP complete problem seem very solvable.<br /><br />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.<br /><br />I will keep you people informed of my progress, and publish a streamlined web-page series when I have definitive results.<br /><br />All the very best,<br /><br />JohnPaul AdamovskyJohnPaul Adamovskyhttp://www.pathcom.com/~vadco/deep.htmlnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-69324386837453188192010-09-26T14:35:08.379-04:002010-09-26T14:35:08.379-04:00Given c colors and m colums how many rows (n) can ...Given c colors and m colums how many rows (n) can i produce without a rectangle?<br /><br />Algorithm:<br /><br /> 1. Create a data structure with c^m arrays.<br /><br /> 2. Populate every array with one of c^m combinations of c colors over m columns.<br /><br /> 3. While an array exists:<br /><br /> 3.1 Select an array with uniform distribution of c colors over m columns.<br /><br /> 3.2 Delete every array that produces a rectangle.<br /><br /> 4. Print n, the maximun number of rows.<br /><br />Correctness:<br /><br /> Why uniform distribution? Because minimizes the number of possible rectangles for a given color and<br /> maximizes the number of rows.<br /><br /> Example: c=2 and m=3<br /><br /> - non-uniform distribution selection produces:<br /> <br /> 000 <- !<br /> 110<br /> 101<br /> 011<br /><br /> n=4<br /><br /> - uniform distribution selection produces:<br /> <br /> 001<br /> 010<br /> 100<br /> 011<br /> 101<br /> 110<br /><br /> n=6<br /><br /> If (m mod c) > 0? The algorithm becomes a little more complicate. It is necessary maintain an history of how<br /> many times a color has been selected.<br /><br /> Example: c=3 and m=8<br /> 0s 1s 2s <br /><br /> 01201201: 0 3-times, 1 3-times, 2 2-times -> 3 3 2<br /> 20120120: 0 3-times, 1 2-times, 2 3-times -> 6 5 5<br /> 12012012: 0 2-times, 1 3-times, 2 3-times -> 8 8 8<br /><br /> In this case are necessary 3 iterations to maintain equal the amount of combinations deleted.<br /><br />Application:<br /><br /> - 17x17 challenge: c=4, m=17, c^m=4^17=17179869184, m mod c = 17 mod 4 = 1 -> 4 iterations, one for color.<br /><br /> Good luck!<br /><br />info: patrick.laarson@yahoo.itPatrick Laarsonnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-91078590952750331712010-09-25T00:23:45.223-04:002010-09-25T00:23:45.223-04:00Hey Man,
I've been working on something much ...Hey Man,<br /><br />I've been working on something much more important than this problem for the past little while, but it is always in the back of my mind.<br /><br />Here is the answer to your question:<br /><br />In a colouring with rank zero:<br /><br />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.<br /><br />Somewhere in the grid, a row and column will intersect with the same additional colour.<br /><br />Based on these self-evident observations, The search-space being explored can be drastically reduced.<br /><br />Simply put, a 17x17 grid (4 colours) can be formatted into 16x4 grid, where each space will have more colours, but less than 256.<br /><br />The lesson learned is that massive improvements will be made in analysis time, and memory requirements for meticulous record keeping will drop way down.<br /><br />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.<br /><br />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.<br /><br /><br />All the very fucking best,<br /><br />JohnPaul AdamovskyJohnPaul Adamovskyhttp://www.pathcom.com/~vadco/dawg.htmlnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-85346301549766163162010-09-14T04:08:50.971-04:002010-09-14T04:08:50.971-04:00Hello JohnPaul,
I am very interested in helping y...Hello JohnPaul,<br /><br />I am very interested in helping you with this problem. However, I cannot fully understand what you have written in your latest post.<br /><br />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?<br /><br />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?C6dimkadimonhttp://www.blogger.com/profile/13373007166638900841noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-11575575999135732642010-07-27T01:03:54.130-04:002010-07-27T01:03:54.130-04:00Hello,
I could use some help here.
I have an ide...Hello,<br /><br />I could use some help here.<br /><br />I have an idea, which I am fairly certain is a good idea:<br /><br />The 17x17 grid search-space can be reduced to a static row and column, with a 16x16 dynamic grid.<br /><br />Observe:<br /><br />00000111122223333<br />0YYYYxxxxxxxxxxxx<br />0YYYYxxxxxxxxxxxx<br />0YYYYxxxxxxxxxxxx<br />0YYYYxxxxxxxxxxxx<br />1xxxxxxxxxxxxxxxx<br />1xxxxxxxxxxxxxxxx<br />1xxxxxxxxxxxxxxxx<br />1xxxxxxxxxxxxxxxx<br />2xxxxxxxxxxxxxxxx<br />2xxxxxxxxxxxxxxxx<br />2xxxxxxxxxxxxxxxx<br />2xxxxxxxxxxxxxxxx<br />3xxxxxxxxxxxxxxxx<br />3xxxxxxxxxxxxxxxx<br />3xxxxxxxxxxxxxxxx<br />3xxxxxxxxxxxxxxxx<br /><br />I am thinking that any candidate 17x17 Perfect Colouring can be converted into this format using row/col switches, and colour flip-flops.<br /><br />The "Y" positions can only take on 3 colours.<br /><br />Please let me know if you have anything to add...<br /><br />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.<br /><br />All the very best,<br /><br />JohnPaul Adamovsky - logarithm69@hotmail.com<br /><br /><br />PS - I've decided to solve this problem if it is possible, and there is a very good chance that it is possible.JohnPaul Adamovskyhttp://www.pathcom.com/~vadco/dawg.htmlnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-33537042173601227382010-07-23T12:57:47.991-04:002010-07-23T12:57:47.991-04:00The imaginary 17x17 Perfect colouring must contain...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.<br /><br />This is a much looser form than the one contained in my proof.<br /><br /><br />All the very best,<br /><br />JohnPaul AdamovskyJohnPaul Adamovskyhttp://www.pathcom.com/~vadco/dawg.htmlnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-72116121871605365232010-07-23T02:11:23.566-04:002010-07-23T02:11:23.566-04:00Hello Michael,
Thank you for pointing me to the P...Hello Michael,<br /><br />Thank you for pointing me to the Perfect 10x10 3-colouring.<br /><br />My initial conjecture was that every Perfect (K^2)x(K^2) colouring was a subset of an "Apex Constraint" colouring.<br /><br />Investigating the 10x10 colouring will certainly aid in my enumeration analysis.<br /><br />I've got some thinking to do.<br /><br /><br />All the very best,<br /><br />JohnPaul AdamovskyJohnPaul Adamovskyhttp://www.pathcom.com/~vadco/dawg.htmlnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-69967444834339150822010-07-22T12:22:18.556-04:002010-07-22T12:22:18.556-04:00@Anonymous poster #133:
The special boundary case...@Anonymous poster #133:<br /><br />The special boundary cases of interest for k colors occur at dimensions (k^2+1)x(k^2+1).<br /><br />5x5 - not 2-colorable<br />10x10 - 3-colorable<br />17x17 - ??<br /><br />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.<br /><br />Of course, if that were true, 10x10 would not be 3-colorable, but we know[1] it is.<br /><br />So, to JohnPaul: What about your proof holds in the 17x17 case, but allows the 10x10 to remain 3-colorable under the same arguments?<br /><br />[1] See slide 44 of Bill's Rectangle-Free presentation:<br />http://www.cs.umd.edu/~gasarch/papers/gridtalk.pdfMichaelnoreply@blogger.com