N-coloring grid with no monochromatic rectangles
Completed Feb. 29, 2012
Assign one of N colors to a X by Y grid such that there are no monochromatic rectangles within that grid.
Recently, news hit that a 4 coloring 17x17 grid was solved.
An X by Y grid is N-colorable if there is a way to N-color the vertices of the X by Y grid so that there are no rectangles having four corners of the same color.
This challenge is to create a computer solution that will solve some arbitrary X by Y grid in N colors.
Using numerals to represent the vertices of a grid, the following 3x3 grid is 2-colorable:
However, the following 3x3 grid (colors represented by letters) is NOT 2-colorable:
That is because there exists a rectangle (marked with green line) with four corners of the same color:
It took some smart folks a long time to solve 4-color 17x17. Our goal for proggitquiz is to to target 4-color 8 x 8 (a case that is known to be 4-colorable).
If that task is too daunting, you can try either a smaller grid (say, 5x5) or fewer colors. If our proggitquiz is too easy, you can attempt the harder grids (please consult this .pdf for the known 4-colorable grids).
If you really want to aim high, it is still unknown whether a solution exists for 4-color 12x21!
Check your solutions using this python gist.
- HN discussion about problem
- Online widget to play challenge in browser
- Original 17x17 prize announcement
This is NOT the same N-color problem as used in the Four Color Theorem. That problem relates to having contiguous areas such that no two adjacent area has the same color. In this problem, you are allowed to have adjacent grid blocks of the same color, all that matters is the corner of any rectangle you can impose within the grid.