# Lower bound on distance from k-coloring a grid without monochromatic rectangles

This question stems from this other question: Grid $k$-coloring without monochromatic rectangles

Given a grid coloring, I want to determine the least amount of rectangles you have to leave uncolored to remove all monochromatic rectangles from the coloring. This would give a lower bound on the number of changes you have to make to the coloring to reach a coloring that has no monochromatic rectangles. As a heuristic for A*, it would be admissible and monotonic.

How would you calculate this number? My first attempt, a greedy algorithm that uncolors one of the cells which is involved in the most rectangles until there are no rectangles left, sometimes overestimates.

• "This would give a lower bound on the number of changes you have to make to the coloring to reach a coloring that has no monochromatic rectangles." I'm not sure this is correct, as it could be the case that by the legally-colored cells elsewhere in the grid, you've forced a situation where no colors will work for the conflicting cells. – Daniel Apon May 26 '11 at 23:00
• See, for example, Rohan Puttgunta's almost-17x17 4-coloring here: cs.umd.edu/~gasarch/BLOGPAPERS/17x17almost.txt (There are no monochromatic rectangles in the coloring, but the cell marked + cannot be colored legally.) -- assuming you mean a tight lower bound. – Daniel Apon May 26 '11 at 23:03
• @Daniel I know it won't usually be a tight lower bound. I'm just looking for a good heuristic to apply an A* or best-first search. – Null Set May 27 '11 at 0:11
• @Daniel It was in fact that example that inspired me to frame it this way. A fully colored version of that example would evaluate to at least 1 move away from the solution, and I'm ok with that. – Null Set May 27 '11 at 0:15
• @Null: how are you going to limit the exponential growth of the A* algorithm? – Marzio De Biasi May 27 '11 at 16:22