News for hackers. Stuff that matters.
Re:The 17x17 challenge. "Worth $289.00. This is not a joke." by bshep on Monday November 30, 2009 @04:56PM (#968792)
I see now! I completely missed this part: "Second, he's not trying to color a simple planar graph. He means every rectangle on the grid -- for example, a 7 x 8 rectangle in the middle somewhere. This is much, much harder to do."

Otherwise the problem seemed trivial.

On the other hand... how many possible 17x17 4-colored grids are there? Can this be brute forced?

Re:The 17x17 challenge. "Worth $289.00. This is not a joke." by cperciva on Monday November 30, 2009 @05:00PM (#968799)
how many possible 17x17 4-colored grids are there?

There's 289 points on the grid, and 4 options for each. So... 2^578 options.

Can this be brute forced?

That depends. Do you have a kilobit quantum computer available?

Re:The 17x17 challenge. "Worth $289.00. This is not a joke." by rms on Monday November 30, 2009 @05:01PM (#968803)
Hold on, let me check my other universe.
Re:The 17x17 challenge. "Worth $289.00. This is not a joke." by RiderOfGiraffes on Monday November 30, 2009 @05:02PM (#968805)
Um, no. The rectangles are aligned with the X and Y axes, so you choose two rows and two columns, giving 17C2x17C2 rectangles in total: 23409 possible rectangles.
Re:The 17x17 challenge. "Worth $289.00. This is not a joke." by cperciva on Monday November 30, 2009 @05:03PM (#968807)
He asked how many grids there were, not how many rectangles there were. :-)
Re:The 17x17 challenge. "Worth $289.00. This is not a joke." by RiderOfGiraffes on Monday November 30, 2009 @05:05PM (#968813)
Ah - sorry, my turn to do a misreading. As you point out, I computed the number of rectangles that aren't permitted to have all its vertices the same color.

My bad - sorry.

Re:The 17x17 challenge. "Worth $289.00. This is not a joke." by Dove on Monday November 30, 2009 @04:59PM (#968798)
4^(17x17).

I think that's quite a few. Your mileage may vary based on the force available to you for bruting.

Re:The 17x17 challenge. "Worth $289.00. This is not a joke." by joeld42 on Monday November 30, 2009 @05:15PM (#968829)
What a neat problem. I hadn't seen this before.

You don't need quite that many -- you could test 2^289 (and you can probably skip many of them) and look for the "rectangle free subsets" that he mentions in the slides, and then just look for four of them that don't overlap. Still gonna take eons.

Re:The 17x17 challenge. "Worth $289.00. This is not a joke." by paulgb on Monday November 30, 2009 @05:03PM (#968806)
> On the other hand... how many possible 17x17 4-colored grids are there? Can this be brute forced?

4^(17*17) ~= 10^173.. a bit too many to brute force, but I'm sure you could narrow the number down a lot with simple heuristics (though it would still be too large to brute force).