The problem isn't what you think it is, otherwise the solution would be trivial: alternate one pair of colors on even rows, and then alternate another pair on odd rows. That satisfies the four color theorem.
This problem differs in two ways.
First, we're not looking for all of the vertices to be different colors. We're looking for them to not all be the same color. This is easier to do.
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.
(To be fair, I made the same mistake on a first reading of the problem.)
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?
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.
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.
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.
> 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).
This problem differs in two ways.
First, we're not looking for all of the vertices to be different colors. We're looking for them to not all be the same color. This is easier to do.
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.
(To be fair, I made the same mistake on a first reading of the problem.)