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.

Problem

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.

Example

Using numerals to represent the vertices of a grid, the following 3x3 grid is 2-colorable:

good grid

However, the following 3x3 grid (colors represented by letters) is NOT 2-colorable:

bad grid

That is because there exists a rectangle (marked with green line) with four corners of the same color:

bad grid explained

Difficulty

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!

Solution checker

Check your solutions using this python gist.

Resources

Clarification

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.

This challenge is now closed.


Scoreboard

None yet!

Come Chat!

Join channel ##proggit on freenode.

Bugs

Having issues with the the site? Let us know.