Determining Stable discs in Othello

Question

I'm trying to determine which discs of an Othello board are stable ones (those that can't be flipped for the rest of the game).

I've read that the disc needs to be stable in all four directions (horizontally, vertically and both diagonals). For it to be stable in any direction, either the direction is full of discs so that no more can be placed in that direction, it is on the edge of the board, or it is adjacent to a stable disc of the same color.

I understand the first two parts, but is there a specific order in which I need to evaluate the stability of discs, because there could be a chain reaction that induces stability.

Answer 1

The simple approach is to iterate until nothing changes. Start with all the discs marked as unstable. Then make a pass through the discs to see if any of them meet the criteria for stability. Change the disc state from unstable to stable for every disc that meets the criteria.

If none of the discs change state during a pass, then you're done. If all of the discs are marked as stable at the end of a pass, then you're done. Worst case case is 64 passes, since at least one disc has to change states on each pass.