4 ms·

Gah. Must...resist...getting...sucked...in...

• bradleyjg 13y ago
  That particular problem was solved, see: http://blog.computationalcomplexity.org/2012/02/17x17-problem-solved-also-18x18.html http://blog.computationalcomplexity.org/2012/02/17x17-proble... and http://www.informatik.tu-freiberg.de/prof2/publikationen/ISMVL_2012_mcfcrfg.pdf http://www.informatik.tu-freiberg.de/prof2/publikationen/ISM...
  • alexkus 13y ago
    Excellent, thank you. I shall ignore the fact that there will be other sized grids that are looking for solutions. Still, it's always interesting to see if one can develop something to come up with one's own solution.
    • stephencanon 13y ago
      > there will be other sized grids that are looking for solutions. Nope! We now know for all grid sizes whether or not they are rectangle-free four-colorable. 17x17, 17x18, and 18x18 were the last remaining cases (there are no such grids larger than 18x18). So you have nothing to worry about.
      • ChuckMcM 13y ago
        (there are no such grids larger than 18x18) Sounds like a challenge :-) Seriously though, I am not a mathematician, did the SAT solution to the 17 x 17 show there were no solutions past 18 x 18? I ask because on the original challenge site was an update [1] which I was trying to parse. It talks about OBS4 but I was trying to parse if that was the class of problem or the particular challenge problem. [1] "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. " -- http://blog.computationalcomplexity.org/2009/11/17x17-challenge-worth-28900-this-is-not.html http://blog.computationalcomplexity.org/2009/11/17x17-challe...
        • stephencanon 13y ago
          I believe that all of the cases are now known. See table 22 in http://arxiv.org/abs/1005.3750 http://arxiv.org/abs/1005.3750
          • ChuckMcM 13y ago
            Thanks for the link! That is pretty cool. I hadn't really thought about these kinds of questions, although operationally I can imagine applications for this, if you imagine columns and rows as redundant network links, and 'colors' being network services, you can prove that all your services have x4 redundancy this way. (I look at 16 x 16 grids all the time except they are 16 racks each with 16 servers :-)
      • thedufer 13y ago
        When http://blog.computationalcomplexity.org/2012/02/17x17-problem-solved-also-18x18.html http://blog.computationalcomplexity.org/2012/02/17x17-proble... was written, 12x21 was still open (so "17x17, 17x18, and 18x18 were the last remaining cases" is not true). Do you know if this has changed (that article is ~2 years old)?
        • jacobolus 13y ago
          If you read down in the comments of that post you can see it was solved. Or see http://11235813tdd.blogspot.com/2012/02/rectangle-free-grid-coloring-21x12-grid.html http://11235813tdd.blogspot.com/2012/02/rectangle-free-grid-...
        • stephencanon 13y ago
          See http://arxiv.org/abs/1005.3750 http://arxiv.org/abs/1005.3750 (tables 19 and 22 in particular).
  • deleted 13y ago
    [deleted]
  • 650REDHAIR 13y ago
    http://www.cs.umd.edu/~gasarch/BLOGPAPERS/17.txt http://www.cs.umd.edu/~gasarch/BLOGPAPERS/17.txt 2,2,1,3,3,4,2,1,4,1,3,2,2,3,4,4,3 2,4,2,1,1,2,3,3,4,4,3,4,1,1,3,2,2 3,1,3,4,4,4,1,1,1,4,3,2,4,1,2,3,2 4,1,2,3,1,3,2,3,4,1,2,1,4,4,1,3,4 3,1,1,1,2,3,2,4,2,3,4,4,4,3,2,2,1 1,3,3,2,4,3,1,4,4,1,2,2,1,2,3,2,3 3,1,4,2,4,2,2,3,3,2,1,4,1,4,4,1,3 4,3,1,2,1,1,1,3,2,4,4,3,2,3,4,1,2 4,4,3,3,4,2,4,2,3,1,2,3,2,1,2,1,1 1,2,2,2,1,3,4,4,1,4,3,3,3,4,2,4,1 4,2,3,4,3,2,1,3,2,3,1,4,3,2,1,4,1 4,2,4,1,2,4,1,4,3,2,2,1,3,3,3,3,2 1,3,2,1,2,4,4,1,3,3,3,4,2,2,1,1,4 1,4,1,4,3,3,3,4,3,2,1,1,2,1,4,2,4 2,4,1,2,2,4,3,2,1,3,4,3,1,4,1,3,3 3,3,2,3,4,1,3,2,2,2,4,2,3,1,1,4,4 2,3,4,4,3,1,4,1,4,2,4,1,1,2,2,3,1