How to determine if there are n consecutive pieces of the same color after every move?

Question

Suppose I have some board game with 2 players. Each player takes turns placing pieces of the board at random locations. A player wins if they have n consecutive pieces in a row (vertically or horizontally). Note that the board can extended indefinitely.

I want to a implement a game such as this, but I'm stuck on how to check the winning condition efficiently. After every move, we can, off coarse, check in all 4 directions to see if we satisfied the winning condition, but that's a O(n) search after every move.

I was thinking of caching the results, although I don't think that helps in this case.

e.g., suppose we have cached results at (i - 1, j) and the next piece is placed at (i, j). we can use the results at the former to compute the results at the latter, so this ends up being a O(1) search, but the problem is, we would have to then update the cached results for all the neighbors up to k squares away, so we have the same issue as before.

Is there a better way to code this problem?

Answer 1

Say each cell stores:

• status: unclaimed, player1, player2
• for each dimension (horizontal / vertical): the consecutive run length inclusive of the cell in question. Treat this as 0 for unclaimed cells.

To avoid expensive updates, we only guarantee run length correctness for the cells at the ends of consecutive runs. E.g. if you're the leftmost cell of a run, the correctness of the length of the run to the right is guaranteed.

On a player claiming a cell, check the 4 neighboring cells.

• If none of them are claimed by the same player, set both dimensions to 1.
• If one or more of them are claimed by the same player, update the endpoints of the relevant runs to reflect the new length.

Example 1: X = unclaimed; 0 = player 0, 1 = player 1. Say along some dimension we have ...XXXX000X000000XXXX...

...and then, player 0 claims the cell separating the run of 3 0s from the run of 6 0s. When checking the neighbors, we see that there's a run that extends 3 to the left and 6 to the right. With the new cell, we have a run of 10. In O(1) we update the 2 endpoints to be 10 in the horizontal dimension.

Each time a cell is claimed, we update at most 4 cells in O(1) time. Because we know the length of the runs, we can find the endpoints in O(1).

Answer 2

I would use two disjoint set data structures -- one for vertical sets and one for horizontal sets.

When a piece is added to the board, you create a set for it in each data structure. Then in the vertical one you merge its set with any (up to 2) vertically adjacent sets of the same color. In the horizontal one you do the same thing for horizontal adjacency.

You need to keep track of the total number of elements in each root set, and when one of them gets bigger than n you have a winner. You might as well use union-by-size instead of union-by-rank.

If you give each piece an integer ID equal to the number of preceding moves, then you can implement these disjoint set data structures very efficiently using a single dynamic array for each one. See the implementation in this answer: How to properly implement disjoint set data structure for finding spanning forests in Python?

This takes effectively constant amortized time per move.

If you're doing some kind of backtracking search that requires you to undo moves, then you should either skip path compression (your checks will then take O(log n) time), or use a method of path compression that changes only a constant number of pointers per operation. I would suggest just linking the node halfway along the path directly to the root. That will restore constant amortized time operation, and will limit updates per move to only 8 integers per move (4 in each disjoint set data structure). Tracking these updates in an undo stack will let you efficiently undo each update for backtracking purposes.