tag:blogger.com,1999:blog-3722233.post2725600741162296905..comments2023-09-27T08:58:55.256-05:00Comments on Computational Complexity: Update on 17x17 problemLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger49125tag:blogger.com,1999:blog-3722233.post-82858297403286443722012-02-08T07:20:04.679-06:002012-02-08T07:20:04.679-06:00THE PROBLEM HAS BEEN SOLVED! There is a 4-coloring...THE PROBLEM HAS BEEN SOLVED! There is a 4-coloring of 17x17 and<br />even of 18x18. See my Feb 8, 2012 post.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-58820486677022811222012-02-08T07:19:12.979-06:002012-02-08T07:19:12.979-06:00THE PROBLEM HAS BEEN SOLVED! There is a 4-coloring...THE PROBLEM HAS BEEN SOLVED! There is a 4-coloring of 17x17 and<br />even if 18x18. See my Feb 8, 2012 post.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-45723795440534079142012-01-09T02:23:06.858-06:002012-01-09T02:23:06.858-06:00@Dmitry: Ok, I didn't see them! (I checked the...@Dmitry: Ok, I didn't see them! (I checked them but none can be expanded to a valid 4-coloring) :-(Marzio De Biasihttps://www.blogger.com/profile/18441670787376943932noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-59081161338725907342012-01-02T05:31:58.175-06:002012-01-02T05:31:58.175-06:00The above Unknown poster (December 21st, 2011) is ...The above Unknown poster (December 21st, 2011) is Dmitry Kamenetsky.<br /><br />Marzio, I have found some 74R+74G rectangle-free skeletons earlier in http://apps.topcoder.com/forums/?module=Thread&threadID=657136<br /><br /><br />Cheers,<br />DmitryAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-46382051229885796482011-12-23T11:08:57.322-06:002011-12-23T11:08:57.322-06:00I never saw a 74R+74G rectangle free skeleton, so ...I never saw a 74R+74G rectangle free skeleton, so I post one just for curiosity.<br /><br />I found many of them, but all *cannot* be expanded to a valid 4-coloring (rejected by SAT solver).<br /><br />12-2-21111--2--2-<br />21-2--1--211-2-12<br />-21---12---2111-2<br />2--12--1--12-1-21<br />2---1-221--12-1-1<br />222--1---12-1--11<br />11122-2---2-----1<br />1--1-22--2-2--11-<br />12--1-2-2-1-12---<br />1---21--2--121--2<br />-12122-21---12---<br />-12-1-2--1---1222<br />-21-21--121---2--<br />2-11-2--21-1--2--<br />--1-1--1--222221-<br />-122-1-12--2--1--<br />---11112222----2-<br /><br />Merry Christmas Everybody!Marzio De Biasihttps://www.blogger.com/profile/18441670787376943932noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-23815790398940870742011-12-21T00:39:38.664-06:002011-12-21T00:39:38.664-06:00Here are some more 4-colourings of 17×17 with 3 re...Here 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.<br /><br />11111222233334444<br />12222233334444111<br />13333244431114222<br />41234313223141243<br />42143342321321421<br />21234142342413312<br />24321124143143421<br />32134424112312234<br />14344211132224333<br />23414231424132413<br />31442324131423142<br />34321441324211142<br />22143113244233134<br />31243431413242321<br />43412412343214231<br />13412143212341324<br />44321312411432314<br /><br />11111222233334444<br />12222233334444111<br />13333244431114222<br />43241321323241431<br />24123124312341342<br />31432112442342134<br />34123342124123124<br />33241143141422342<br />21432443113213421<br />44123413241232231<br />42314313422311243<br />22314134244123431<br />14444211132224333<br />41432334221431312<br />23241412414133213<br />24113231423412413<br />32314421311432124<br /><br />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/<br /><br />4312|1342|2143|2413|1<br />2134|2134|3421|1324|1<br />3421|4213|4312|3241|1<br />1243|3421|1234|4132|1<br />———————<br />1243|1342|4312|1324|2<br />3421|2134|1234|2413|2<br />4312|3421|3421|3241|2<br />2134|4213|2143|4132|2<br />———————<br />1243|2134|2143|3241|3<br />4312|4213|1234|1324|3<br />2134|3421|4312|2413|3<br />3421|1342|3421|4132|3<br />———————<br />1243|4213|3421|2413|4<br />4312|2134|4312|4132|4<br />3421|3421|2143|1324|4<br />2134|1342|1234|3241|4<br />———————<br />4444|2222|1111|3333|1Unknownhttps://www.blogger.com/profile/13373007166638900841noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-54934130295079466752011-12-04T10:51:24.144-06:002011-12-04T10:51:24.144-06:00Thanks for the catch Esaj, I removed Ongda's p...Thanks for the catch Esaj, I removed Ongda's post. These spambots are getting clever.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-80495325041365941562011-12-04T10:48:41.144-06:002011-12-04T10:48:41.144-06:00Ongda appears to be a spambot, as the text is copi...Ongda appears to be a spambot, as the text is copied from an earlier comment by Marzio. :)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-26516175544230844602011-12-04T05:36:15.689-06:002011-12-04T05:36:15.689-06:00Ongda: suppose you have an enumeration of non isom...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?Marzio De Biasihttps://www.blogger.com/profile/18441670787376943932noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-73958589659129445492011-11-14T04:04:49.637-06:002011-11-14T04:04:49.637-06:00I've been counting the total number of unique ...I've been counting the total number of unique solutions for arbitrary nxm grids here: http://www.jasondavies.com/17x17/<br /><br />Unfortunately 5x5 has eluded me so far, due to lack of RAM. :)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-89674292802178890112011-10-20T09:19:34.655-05:002011-10-20T09:19:34.655-05:00... and another highly symmetric 74s ....
http://w...... and another highly symmetric 74s ....<br />http://www.fractalmuse.org/grid17x17/art74symmetry.jpgMarzio De Biasihttps://www.blogger.com/profile/18441670787376943932noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-7676366915203263102011-10-19T16:21:12.693-05:002011-10-19T16:21:12.693-05:00... waiting (in vain) for the SAT solver I made an...... 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" :-)Marzio De Biasihttps://www.blogger.com/profile/18441670787376943932noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-5908498280080437662011-10-12T04:54:07.958-05:002011-10-12T04:54:07.958-05:00@Alexandros: thanks.
Using a SAT solver I noticed...@Alexandros: thanks.<br /><br />Using a SAT solver I noticed an odd property.<br /><br />1) find a 2-coloring of a 16x16 grid that has no *** 3x3 *** monochromatic rectangle;<br /><br />2) pick this grid as the high-bits of the 4-coloring of a 16x16 grid, and run the solver;<br /><br />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. <br /><br />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)<br /><br />... obviously the solver hangs if I add another colunm (17x17).<br /><br />We know from Ramsey theory that there is no 17x17 2-colored grid without monochromatic 3x3 rectangles.<br /><br />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).<br /><br />Alas I'm not an expert of Ramsey theory ... hoping that someone else solves this nightmare!<br /><br />(P.S. obviously I think that there is no valid 4-coloring :-))))Marzio De Biasihttps://www.blogger.com/profile/18441670787376943932noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-86555549370550861392011-10-02T05:26:34.112-05:002011-10-02T05:26:34.112-05:00Marzio - We know from Beth Kupin's work that a...Marzio - We know from Beth Kupin's work that all 73's can be extended to 74's, so you can reduce your scope. <br /><br />eg:<br /><br />a 73-72-72-72 can always be turned to a 74-72-72-71.<br /><br />a 73-73-73-70 can become either a 74-73-72-70 or a 74-73-73-69.<br /><br />This may or may not help depending what you want to do with the configurationsAnonymoushttps://www.blogger.com/profile/07772624197186878684noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-7309952565155248942011-09-14T12:16:44.270-05:002011-09-14T12:16:44.270-05:00I do not understand your notation, however, no
con...I do not understand your notation, however, no<br />configs have been ruled out. I am sure that some<br />could be easily- with the help of a program.<br /><br />It might be more efficient to email me directly and<br />have me email you directly if you have more thoughts-<br />my email is gasarch@cs.umd.edu but I don't know yours.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-48242080398461926552011-09-14T12:03:06.220-05:002011-09-14T12:03:06.220-05:00A question regarding the colors count in a 17x17 v...A question regarding the colors count in a 17x17 valid 4-coloring (perhaps I missed the information in the linked papers).<br /><br />Which of these configurations (if any) have been proved to be impossible?<br /><br />74 74 71 70<br />74 73 72 70<br />74 73 71 71<br />74 72 72 71<br />73 73 73 70<br />73 73 72 71<br />73 72 72 72Marzio De Biasihttps://www.blogger.com/profile/18441670787376943932noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-34252331969039097242011-09-12T14:39:51.818-05:002011-09-12T14:39:51.818-05:00That there are NO 17x8 RFS with 5 R per row is VER...That there are NO 17x8 RFS with 5 R per row is VERY INTERESTING- might help to cut down the number of possible<br />large RFS's of 17x17 there are and hence cut down what to look at.<br /><br />(OH- This is BILL GASARCH even though it will show up a<br />anonymous- sorry about that).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-12831934863703151142011-09-10T10:38:02.782-05:002011-09-10T10:38:02.782-05:00... some fixes:
A) "66" are the 17x5 re...... some fixes:<br /><br />A) "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)<br /><br />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)<br /><br />About your answer:<br /><br />*** 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.<br /><br />*** 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).<br /><br />*** 3) there are no valid 17x8 "skeleton" grids with 5Rs in each row.<br /><br />*** 6) ... I agree with you ... (I tried to solve the 17x17 rectangle free grid filled with 74 REDS without success)<br /><br />*** 7) ... still working on it (at least I'll try to get all non-isom full coloring extensions) ...<br /><br />If I make some progress and get the exact count of the non-isom 17x5 skeletons, I'll post a new comment.Marzio De Biasihttps://www.blogger.com/profile/18441670787376943932noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-88259947064033898902011-09-10T09:14:29.629-05:002011-09-10T09:14:29.629-05:001) Are you saying there are 66 NON-ISOM rect free
...1) Are you saying there are 66 NON-ISOM rect free<br />subsets of 17x5, and 84 TOTAL (including ISOM ones?)<br />(All of which can be extended to full colorings.)<br /><br />2) If so then the next thing to do would be to see which of the 84^2 ways to form a rect free<br />set of 17x10 that have the property are really rect free. <br /><br />3) Then see which 17x15 are...<br /><br />4) the remaining 2 rows are easy- try all possibilities.<br /><br />5) When DONE then you have ALL Rect Free sets of<br />17x17 that have the property.<br /><br />6) (This may be the hard step) See which of those<br />can be extended to a full coloring. <br />SEE NEXT ITEM for another approach<br /><br />7) Rather than get all possible RECT FREE SETS<br />you can try to get all possible COLORINGS-<br />you say that each of your rect free sets of<br />17x5 can be extended to a full coloring of <br />17x5. Can you get ALL colorings?<br /><br />8) The UPSHOT of all this would HOPEFULLY be<br />to FIND A COLORING. However, if everything you say is correct and you show that NONE of the <br />rect free sets of 17x17 that you obtain can be<br />extended then you will get that 17x17 is<br />NOT 4-colorable, also worth knowing.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-36078464412281438362011-09-10T04:58:14.293-05:002011-09-10T04:58:14.293-05:00... and there are 84 17x5 rectangle free "ske...... and there are 84 17x5 rectangle free "skeleton" grids with 5Rs in each row.<br />All of them allow a valid 4-coloring with 5R, 4G, 4B, 4Y in each row.Marzio De Biasihttps://www.blogger.com/profile/18441670787376943932noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-22309555660220413852011-09-10T04:36:26.353-05:002011-09-10T04:36:26.353-05:00... there are 66, 17x5 non isom rectangle free &qu...... there are 66, 17x5 non isom rectangle free "skeleton-grids" having 5 Rs in each row.<br /><br />All of them allow a valid 4-coloring with 5R,4G,4B,4Y in each row.<br /><br />Any idea on how to use them ???Marzio De Biasihttps://www.blogger.com/profile/18441670787376943932noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-30620769732700970702011-09-09T10:09:24.560-05:002011-09-09T10:09:24.560-05:00I think there are too many of them ...
... but I&#...I think there are too many of them ...<br />... 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.Marzio De Biasihttps://www.blogger.com/profile/18441670787376943932noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-65425318049495271092011-09-09T09:26:35.806-05:002011-09-09T09:26:35.806-05:00Great, Thanks.
can you get ALL non-isom proper 4-...Great, Thanks.<br /><br />can you get ALL non-isom proper 4-colorings of 17x5<br />that have 5 R's in each column? If so this might help<br />FIND a coloring of 17x17 OR show that NONE exist.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-75707479765055774242011-09-09T06:00:21.511-05:002011-09-09T06:00:21.511-05:00Hi,
In your 17x17advice.pdf document ("Some b...Hi,<br />In your 17x17advice.pdf document ("Some brief thoughts on 17x17") you say:<br /><br />"... Is there a rectangle free subset of 5x17<br />which has 5 elements in each column? There is. However, **there is only one** (up to perms of columns and rows). Here it is:<br /><br />44444------------<br />4----4444--------<br />4--------4444----<br />-4---4---4---44--<br />--4---4---4----44<br /><br />..."<br /><br />But I found another one that seems not to be "isomorphic":<br /><br />44444------------<br />4----4444--------<br />4--------4444----<br />-4---4---4---44--<br />-4----4---4----44<br /><br /><br />The coloring with four 1,2,3 cells in each row is: <br /><br />44444312213213231<br />41111444422333223<br />43232123344442111<br />24333411141324422<br />34223343224111144<br /><br />And another one with an "empty" column :<br /><br />44444------------<br />4----4444--------<br />4--------4444----<br />-4---4---4---44--<br />--4---4---4---44-<br /><br />44444123313212213<br />41111444423323322<br />41233332244442111<br />34322411141234432<br />33432243224111441Marzio De Biasihttps://www.blogger.com/profile/18441670787376943932noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-34858538338225755292011-06-23T10:20:47.757-05:002011-06-23T10:20:47.757-05:00The intersection rule should have read:
If m is t...The intersection rule should have read:<br /><br />If 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.<br /><br />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:<br /><br />1. Color A uses 144 of a possible 153 intervals.<br />2. Color B uses 135 intervals used by A and the nine intervals not used by A.<br />3. Color C uses 126 intervals used by A and B, 9 intervals not used by A and 9 intervals not used by B.<br />4. Color D has to use 126 intervals already used by A, B, and C? <br /><br />It takes 6X18 or 108 intervals to correctly place 4 spots of one color on each of the 18 rows.<br /><br />For an even distribution by row, we<br />need to color an additional 9 spots for each color repeating at least 18 intervals.<br /><br />It only takes one set of 10 intervals used by all four colors to lock out 14 spots from being correctly colored.<br /><br />We may have some wiggle room by going to an uneven distribution.<br /><br />The general idea is that there may be unavoidable sets which are also mutually exclusive.Jim Blairhttp://firedude7@aol.comnoreply@blogger.com