Connect-three puzzle solveability

Question

I'm writing a casual connect-three type game that uses a square grid. The player slides a row or column around (essentially rotating it in 1D) to put at least three blocks of the same type together to make a match.

Because the level of difficulty will increase as play goes on, there will come a point (I have checked, it is possible) for there to be no moves that will result in a new match.

Aside from using the brute-force method (which is at least O(N^2) time), is there a faster method of looking for possible moves?

Answer 1

You can do it in O(N log(M)) where N is the number of positions on the board and M is the number of shapes available:

1. O(N log(M)): For each point (O(N)), update a map of the available shapes for its row and column (O(log(M)).
   
2. O(N log(M)): For each point (O(N)), check for similar shapes adjacent to or one space away vertically, horizontally, or diagonally (O(1)), and check the row/column map(s) (O(log(M))) that would "connect three" to see if a valid move is available.

You can also improve on the above method so that it does not repeat checks unnecessarily (shapes on the 2nd row and below do not check up, and shapes on the 2nd column and to the right do not check left), but the big O cost would be the same.

Furthermore, after each move you only need to update the maps of the rows/columns that have changed, and you only need to check the shapes that have changed. The worst case is that the whole board is cleared, so the big O cost of this improvement would be the same as well.