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.