<p>This question stems from this other question: <a href="https://cstheory.stackexchange.com/questions/791/grid-k-coloring-without-monochromatic-rectangles">Grid $k$-coloring without monochromatic rectangles</a></p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2011-05-26T23:00:10.777Z
"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
CC BY-SA 3.0
2011-05-26T23:03:10.133Z
See, for example, Rohan Puttgunta's almost-17x17 4-coloring here: http://www.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
CC BY-SA 3.0
2011-05-27T00:11:51.370Z
@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
CC BY-SA 3.0
2011-05-27T00:15:06.333Z
@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
CC BY-SA 3.0
2011-05-27T16:22:29.743Z
@Null: how are you going to limit the exponential growth of the A* algorithm?
Marzio De Biasi
CC BY-SA 3.0
2011-05-27T21:06:55.420Z
@Vor I guess I don't actually care about the shortest path, so I will be doing it as a best-first search which expands significantly less nodes. Because one of the colors is known and fixed, I can reduce it to 430 alternative moves at each node, which should limit the exponential growth factor a bit. I suspect I'll run out of memory before too long, so I plan on culling some of the worst nodes when that happens.
Null Set
CC BY-SA 3.0
2011-05-27T21:21:13.583Z
@Null: ok. Remember that if you want you can start with a valid 15x15 4-colored grid that can be produced almost instantly by a simple simulated annealing algorithm (a 16x16 requires much more time). I've got a "17x17 running horse", too ... but it is slow (java) ... and I myself don't belive in it :-D :-D
Marzio De Biasi
<co.combinatorics>
Lower bound on distance from k-coloring a grid without monochromatic rectangles
Null Set
# Lower bound on distance from k-coloring a grid without monochromatic rectangles

(Asked by: username_0 on 2011-05-26)

This question stems from this other question: [Grid $k$-coloring without monochromatic rectangles](https://cstheory.stackexchange.com/questions/791/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.

**Tags:** co.combinatorics

> **Comments:**
> **username_1**: "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.  
> **username_1**: See, for example, Rohan Puttgunta's almost-17x17 4-coloring here: http://www.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.  
> **username_0**: @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.  
> **username_0**: @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.  
> **username_2**: @Null: how are you going to limit the exponential growth of the A* algorithm?  
> **username_0**: @Vor I guess I don't actually care about the shortest path, so I will be doing it as a best-first search which expands significantly less nodes. Because one of the colors is known and fixed, I can reduce it to 430 alternative moves at each node, which should limit the exponential growth factor a bit. I suspect I'll run out of memory before too long, so I plan on culling some of the worst nodes when that happens.  
> **username_2**: @Null: ok. Remember that if you want you can start with a valid 15x15 4-colored grid that can be produced almost instantly by a simple simulated annealing algorithm (a 16x16 requires much more time). I've got a "17x17 running horse", too ... but it is slow (java) ... and I myself don't belive in it :-D :-D  

---

## 0 answers

