4 ms·

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

by bshep 17y ago

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?

Dove 17y ago
4^(17x17). I think that's quite a few. Your mileage may vary based on the force available to you for bruting.
- deleted 17y ago
  [deleted]
- joeld42 17y ago
  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.
cperciva 17y ago
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?
- rms 17y ago
  Hold on, let me check my other universe.
- RiderOfGiraffes 17y ago
  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.
  - cperciva 17y ago
    He asked how many grids there were, not how many rectangles there were. :-)
    - RiderOfGiraffes 17y ago
      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.
paulgb 17y ago
> 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).

by bshep 17y ago

Dove 17y ago

4^(17x17). I think that's quite a few. Your mileage may vary based on the force available to you for bruting.

deleted 17y ago
[deleted]
joeld42 17y ago
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.

cperciva 17y ago

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?

rms 17y ago
Hold on, let me check my other universe.
RiderOfGiraffes 17y ago
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.
- cperciva 17y ago
  He asked how many grids there were, not how many rectangles there were. :-)
  - RiderOfGiraffes 17y ago
    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.

paulgb 17y ago

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