1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "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. $\endgroup$ – Daniel Apon May 26 '11 at 23:00
  • $\begingroup$ 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. $\endgroup$ – Daniel Apon May 26 '11 at 23:03
  • $\begingroup$ @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. $\endgroup$ – Null Set May 27 '11 at 0:11
  • $\begingroup$ @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. $\endgroup$ – Null Set May 27 '11 at 0:15
  • $\begingroup$ @Null: how are you going to limit the exponential growth of the A* algorithm? $\endgroup$ – Marzio De Biasi May 27 '11 at 16:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.