Hacker News Reader

Comment by bradleyjg | Hacker News Reader

That particular problem was solved, see: http://blog.computationalcomplexity.org/2012/02/17x17-proble... and http://www.informatik.tu-freiberg.de/prof2/publikationen/ISM...

View on HN

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.

> 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.

(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-challe...

I believe that all of the cases are now known. See table 22 in http://arxiv.org/abs/1005.3750

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 :-)

When 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)?

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-...

See http://arxiv.org/abs/1005.3750 (tables 19 and 22 in particular).

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

Reply on news.ycombinator.com