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.

Improve this question
$\endgroup$
7
  • $\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, 2011 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, 2011 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, 2011 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, 2011 at 0:15
  • $\begingroup$ @Null: how are you going to limit the exponential growth of the A* algorithm? $\endgroup$
    – Marzio De Biasi
    May 27, 2011 at 16:22

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.