I was thinking about this more in depth and using Inkscape for visualization and I think I can simplify this by weighting the cells.
Each cell weight would be the total number of possible 4-connect moves and it would be updated after each move. A weight of 0 indicates a cell that is the single point of exit for a color and is thus blocked for any other color. With this method, the correct route should end up being the "cheapest" route. Interestingly, in the example below, I ran into a case that is unsolvable.
This isn't perfect, but it seems to be a good starting point.