Thanks to Iman Hajirasouliha for sending me this elegant solution! Model the grid with a bipartite graph G[X, Y], a vertex in part X for each row and a vertex in part Y for each column. Add edges between xi and yj iff there is a point in the corresponding place. If G has a cycle (it must be an even cycle), we color the edges alternatively and remove those edges. When this procedure can no longer be applied, we must be left with a tree. At this point, we can solve the problem by induction on the number of edges as follows: remove e a leaf edge, color the remaining edges balanced, now look at the parent of that leaf and choose the right color for e to maintain the induction hypothesis.