Hmm. I can think of some ideas, but I would probably have to try to implement it myself to give you a confident solution.
You might want to start by looking at flood fill algorithms and think about how you can adapt that kind of idea:http://en.wikipedia.org/wiki/Flood_fill
I would probably keep the entire board as a dictionary of coordinate to color.
Then I would keep track of several sets of checked coordinates.
Perhaps an open_set containing all the cells that needed to be checked for neighbors, and a closed_set of cells that had already been confirmed to have no neighbors that weren't already the same color. When the length of the closed_set reaches the length of the board dictionary, the player has won.
That is just a rough idea of how I would approach it.