tag:blogger.com,1999:blog-3722233.post6168336670788086310..comments2022-11-30T20:33:43.467-06:00Comments on Computational Complexity: The 17x17 problem SOLVED! (also 18x18)Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger43125tag:blogger.com,1999:blog-3722233.post-68671552381074397642014-11-02T09:07:47.545-06:002014-11-02T09:07:47.545-06:00what you mention is a degenerate parallelogram (an...what you mention is a degenerate parallelogram (and there are plenty non-degenerate parallelograms) but not a rectangle!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-19971122166066015482013-11-25T02:54:53.792-06:002013-11-25T02:54:53.792-06:00I'm not sure anyone is still interested, but I...I'm not sure anyone is still interested, but I posted my code for solving rectangle free grid coloring via evolutionary computation over on github. Here is a link to the code of interest:<br />https://github.com/PaulVaroutsos/Scripts-Algorithms-and-Other-Projects/tree/master/Rectangle%20Free%20Grid%20Coloring<br />(see the src/ec/app package)<br /><br />Cheers!Paul Varoutsoshttps://www.blogger.com/profile/14796605592311728130noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-38581598025706896122013-08-04T14:36:59.241-05:002013-08-04T14:36:59.241-05:00 Very well !! Then where is this Java algorithm ?... Very well !! Then where is this Java algorithm ? How could we get it ? Did you post it anywhere ??Anonymoushttps://www.blogger.com/profile/12607375414526032942noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-73661290539741249682012-03-14T23:11:32.482-05:002012-03-14T23:11:32.482-05:00Wrong use of "their"...just saying...Wrong use of "their"...just saying...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-19369629609649081562012-02-28T04:36:23.660-06:002012-02-28T04:36:23.660-06:00I wrote a genetic algorithm to solve rectangle fre...I wrote a genetic algorithm to solve rectangle free grid coloring. It was written in java. It was effective at solving grid sizes up to about 14x14 where it would start to have trouble.Paul Varoutsoshttps://www.blogger.com/profile/14796605592311728130noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-84496078653377274592012-02-27T10:48:02.393-06:002012-02-27T10:48:02.393-06:00The 18x18 grid is 4-colorable, too; so - up to col...The 18x18 grid is 4-colorable, too; so - up to color permutations - there should be at least 18x18=324 distinct solutions for the 17x17 grid (delete one row and one column from the 18x18 solution).Marzio De Biasihttps://www.blogger.com/profile/18441670787376943932noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-28130127094472075342012-02-26T12:16:32.713-06:002012-02-26T12:16:32.713-06:00interesting problem, indeed.
is that published sol...interesting problem, indeed.<br />is that published solution of the 17x17 THE (only) solution, or is it one of some or many solutions?? any estimates here?<br />is there a systematic way to come from this solution to other solutions?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-78378789414209325402012-02-22T18:37:24.490-06:002012-02-22T18:37:24.490-06:00A nice colored version can be found here:
http://w...A nice colored version can be found here:<br />http://www.spiegel.de/fotostrecke/fotostrecke-78910-3.htmlNathanhttp://www.muennich.co.uknoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-9087160575752271342012-02-17T21:49:20.911-06:002012-02-17T21:49:20.911-06:00GREAT! NOW the obstruction set for 4-coloring is c...GREAT! NOW the obstruction set for 4-coloring is completely<br />known. I will revise my paper and post about it at some<br />later time.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-86726094826614647812012-02-17T13:47:03.274-06:002012-02-17T13:47:03.274-06:00THE 12x21 PROBLEM HAS BEEN SOLVED!!!!!
In though...THE 12x21 PROBLEM HAS BEEN SOLVED!!!!!<br /><br /><br />In thoughts #4 of this blog has been written:<br /><br />The only grid that we do not know if it is 4-colorable is 12x21. This is still open and you are URGED to work on it. Sorry, no cash on this one. Do it for the glory!<br /><br /><br />Commonly with Christian Posthoff I (Bernd Steinbach) have done this work. <br /><br />One 4-colored grid of 12x21 is here:<br /><br /><br />1,1,3,1,4,2,1,1,1,3,4,3,2,4,2,3,2,4,3,4,2<br />2,3,4,4,1,4,3,1,2,4,2,3,1,1,4,2,2,4,1,3,3<br />4,2,2,3,2,1,1,3,4,3,1,4,4,2,1,2,3,4,1,3,2 <br />1,2,1,3,4,1,4,4,3,1,3,2,4,1,4,3,2,1,2,2,3<br />4,4,3,4,1,2,4,2,1,1,4,2,3,3,1,2,3,2,4,1,3<br />3,2,4,3,3,1,3,1,2,2,4,1,4,3,2,1,4,2,3,1,4 <br />2,3,4,2,2,1,4,2,1,3,3,4,1,3,2,4,1,3,2,4,1<br />2,3,4,1,3,3,2,4,4,1,1,1,1,4,3,3,3,2,4,2,2 <br />4,3,2,2,1,2,1,3,3,2,2,1,3,4,4,4,1,1,3,2,4<br />2,4,3,1,4,4,3,3,4,2,3,2,2,2,3,4,4,1,1,1,1<br />4,1,1,3,1,2,2,4,2,4,1,3,3,2,3,1,4,3,2,4,1<br />3,2,3,1,4,3,2,2,3,4,2,4,2,1,1,1,1,3,4,3,4<br /><br /><br />Some thoughts:<br /><br />1. It was even more complicate to find this 4-color 12x21 solution in comparison to our 4-color solution for the grid 18x18 (from which a sub-grid was posted as solution of the 17x17 problem).<br /><br />2. We will publish our steps to find the 4-color 12x21 grid as soon as possible. However, this will take some time.Bernd Steinbachhttp://www.informatik.tu-freiberg.de/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-52293277274027476542012-02-17T13:40:13.096-06:002012-02-17T13:40:13.096-06:00Thank you for your congratulations.
Searching fo...Thank you for your congratulations. <br /><br />Searching for a 4-colored 18x18 grid we utilized many approaches. We have been published already some of them (important intermediate steps). You can download these papers from my web page. <br /><br />At this time we prepare the remaining approaches for well understandable papers. This takes some time besides of teaching. A couple of words on this blog are not enough for well comprehension.<br /><br />The 12x21 problem seems to be simpler than 18x18. It must be evaluated ONLY $4{252}=5.237*10^{151}$ instead of $4{324}=1.168*10^{195}$ grid patterns. From our point of view, the 12x21 problem is even more difficult than the 18x18 problem. Our successful approach for 18x18 failed for 21x12. However, it is my pleasure to answer your question regarding 21x12. Together with Christian Posthoff I solved this last unknown 4-color grid problem.<br /><br />THERE IS A 4-COLERED GRID OF THE SIZE 12x21!!!!<br /><br />I will post this solution soon.Bernd Steinbachhttp://www.informatik.tu-freiberg.de/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-79978509544649931962012-02-16T08:52:51.928-06:002012-02-16T08:52:51.928-06:00First of all my congratulations to you and Christi...First of all my congratulations to you and Christian for solving the problem ... you succeeded in finding a needle in a bunch of universes :-D !!!<br /><br />Can you tell something in advance about the technique used to solve it (with a post in this blog)? And what about the 21x12 grid?Marzio De Biasihttps://www.blogger.com/profile/18441670787376943932noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-8069161909528096172012-02-16T00:29:00.896-06:002012-02-16T00:29:00.896-06:00This extension to 18x18 is correct. You are right;...This extension to 18x18 is correct. You are right; it is easy to extend our 17x17 solution to 18x18 because we created the 17x17 solution from a valid 18x18 solution cutting one row and one column. Knowing our 17x17 solution it remains a (SMALL) search space of $4^35=1,180,591,620,717,411,303,424=1.118*10^21$. This is significantly simpler than the whole (VERY LARGE) search space of $4^324=1.168*10^195$.Bernd Steinbachhttp://www.informatik.tu-freiberg.de/index.php?option=com_content&task=view&id=26&Itemid=51noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-88386849597385186302012-02-15T03:43:03.503-06:002012-02-15T03:43:03.503-06:00The 17x17 solution by Steinbach and Posthoff can b...The 17x17 solution by Steinbach and Posthoff can be easily extended to a 18x18 solution; this is a preview of the "18x18 gem" :<br /><br />221334214132234431<br />242112334434113223<br />313444111432412322<br />412313234121441342<br />311123242344432213<br />133243144122123234<br />314242233214144131<br />431211132443234124<br />443342423123212113<br />122213441433342411<br />423432132314321412<br />424124143221333321<br />132124413334221144<br />141433343211214242<br />241224321343141332<br />332341322242311441<br />234431414241122313<br />344131221113423424<br /><br />It will be very interesting to hear what they say about the "21x12 missing tile" in their paper.Marzio De Biasihttps://www.blogger.com/profile/18441670787376943932noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-18439562399024786872012-02-14T03:40:54.906-06:002012-02-14T03:40:54.906-06:00@Gasarch: it seems that the anonymous posts here a...@Gasarch: it seems that the anonymous posts here and above are not "human" :-)Marzio De Biasihttps://www.blogger.com/profile/18441670787376943932noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-12367207335620919212012-02-13T19:20:05.411-06:002012-02-13T19:20:05.411-06:00In the paper (Fenner-Gasarch-Glover-Purewal) we ha...In the paper (Fenner-Gasarch-Glover-Purewal) we have very general<br />theorems which can be used to get many 5-col and NON-5-col results.<br /><br />I would be good to see what you can get from our theorems and then<br />see where the gaps are and go after those- in an attempt to get<br />the obstrction set.<br /><br />Same for 6,7, etc.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-5859144978978516822012-02-13T19:14:07.509-06:002012-02-13T19:14:07.509-06:00Congratulations to Bernd Steinbach and Christian P...Congratulations to Bernd Steinbach and Christian Posthoff on this excellent achievement! Even more amazing is that they got a colouring of 18x18.<br /><br />Bill, just wondering, has anyone worked on this problem for more than four colours? From my initial attempts, I got a 23x23 colouring with 5 colours, 31x31 with 6 colours and 38x38 with 7 colours. Is this worth investigating further?<br /><br /><br />Cheers,<br />Dmitry KamenetskyAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-18594607246991675832012-02-13T13:50:18.562-06:002012-02-13T13:50:18.562-06:00A while back I offered 289 dollars for someone who...A while back I offered 289 dollars for someone who could email me<br />a 4-coloring of the 17x17 grid that has no mono rectangles.<br />This has now been done.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-64754785155426236752012-02-13T13:09:31.669-06:002012-02-13T13:09:31.669-06:00where is a picture?where is a picture?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-20544626101037536302012-02-13T12:13:58.858-06:002012-02-13T12:13:58.858-06:00The anonymous user was probably hoping for somethi...The anonymous user was probably hoping for something in color, like <a href="http://www.cs.umd.edu/~egolub/4c.html" rel="nofollow">this</a>.Evannoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-18935247657180558822012-02-13T09:30:08.386-06:002012-02-13T09:30:08.386-06:00A rectangle of 3 colors isn't monochromatic. ...A rectangle of 3 colors isn't monochromatic. A rectangle with only one color is.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1519374162957261222012-02-13T09:13:34.916-06:002012-02-13T09:13:34.916-06:00Seriously.. I have no idea what are you guys talki...Seriously.. I have no idea what are you guys talking about.. Anyone please enlighten me<br /> thankAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-64026673932691894712012-02-13T04:35:20.142-06:002012-02-13T04:35:20.142-06:00Okay, thanks! I looked at Beth's paper and if...Okay, thanks! I looked at Beth's paper and if my calculations are correct (always in question since after 2 AM I start believing trapezoids are rectangles and other bizarre things) then her mistake can be pushed back to page 19 "If not, then one of<br />{O,P,Q} is in a group of 3". Each of the three occurrences of color 4 in row 6 of the coloring has a counterpart in the same column in a row with 5 occurrences of color 4.Mickihttps://www.blogger.com/profile/11592612022853202507noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-50557811359191231872012-02-12T21:41:52.504-06:002012-02-12T21:41:52.504-06:00The posted answer used the colors 1,2,3,4.
Hence i...The posted answer used the colors 1,2,3,4.<br />Hence it was four colors.<br />It has been verified by several people.<br />(Plus I've already given them the $289.00 so it has<br />to be correct :-) )GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-11854008086395283802012-02-12T21:40:57.874-06:002012-02-12T21:40:57.874-06:00I am not aware of such.I am not aware of such.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.com