I appreciate the comments about the checkerboard idea. So, more formally the grid is a bipartite graph. I could not find any more efficient algorithms or ideas to take advantage of that. Any takers?
Most of the specialized bipartite graph seemed to deal with flow type problems, which did not seem to help much.
Oh well, I'm out of ideas. Good luck to all, this has been fun
