1

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.

Community
  • 1
Null Set
  • 111
  • 3
  • "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: 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 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 00: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 00:15
  • @Null: how are you going to limit the exponential growth of the A* algorithm? – Marzio De Biasi May 27 '11 at 16:22
  • @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 May 27 '11 at 21:06
  • @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 May 27 '11 at 21:21

0 Answers0