3 ms·
(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 th
by 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 agoI 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 agoThanks 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 :-)