Re:The 17x17 challenge. "Worth $289.00. This is not a joke."
by scythe on Tuesday December 01, 2009 @03:00AM
(#969431)
Try just placing 73 1's. You need to be able to place that many, but I can't get more than 65.
[ Parent
| on HN ]
Re:The 17x17 challenge. "Worth $289.00. This is not a joke."
by RiderOfGiraffes on Tuesday December 01, 2009 @07:52AM
(#969626)
I've got 67 just using random placements with heuristics, programmed in Python. Apparently they've got 73 (which is 289/4 rounded up), and that's why they think this might be possible.
Re:The 17x17 challenge. "Worth $289.00. This is not a joke."
by abentspoon on Tuesday December 01, 2009 @11:46AM
(#970056)
I've placed 74 using an IP solver
1 1 . . . . . 1 1 . . . . . 1 . .
. 1 1 1 1 . . . . . . . . . . . .
1 . 1 . . 1 . . . . . 1 . . . . 1
1 . . 1 . . 1 . . . 1 . . . . 1 .
1 . . . 1 . . . . 1 . . . 1 . . .
. . . 1 . 1 . 1 . . . . . 1 . . .
. 1 . . . 1 1 . . 1 . . . . . . .
. . 1 . . . 1 1 . . . . 1 . . . .
. . . . 1 1 . . 1 . . . 1 . . 1 .
. . 1 . . . . . 1 1 1 . . . . . .
. . . . 1 . . 1 . . 1 1 . . . . .
. . . . . . 1 . 1 . . 1 . 1 . . .
. . . 1 . . . . . 1 . 1 1 . 1 . .
. 1 . . . . . . . . 1 . 1 1 . . 1
. . 1 . . . . . . . . . . 1 1 1 .
. . . . 1 . 1 . . . . . . . 1 . 1
. . . . . . . 1 . 1 . . . . . 1 1
The solver chokes on anything larger than a 6x6 grid, but I've had good luck adding one row at a time to a smaller solution.edit: He mentions that he already found a size 74 set in one of the linked pdfs. http://www.cs.umd.edu/~gasarch/BLOGPAPERS/17x17.pdf