[java] Algorithm for Determining Tic Tac Toe Game Over

Constant time solution, runs in O(8).

Store the state of the board as a binary number. The smallest bit (2^0) is the top left row of the board. Then it goes rightwards, then downwards.

I.E.

+-----------------+
| 2^0 | 2^1 | 2^2 |
|-----------------|
| 2^3 | 2^4 | 2^5 |
|-----------------|
| 2^6 | 2^7 | 2^8 |
+-----------------+

Each player has their own binary number to represent the state (because tic-tac-toe) has 3 states (X, O & blank) so a single binary number won't work to represent the state of the board for multiple players.

For example, a board like:

+-----------+
| X | O | X |
|-----------|
| O | X |   |
|-----------|
|   | O |   |
+-----------+

   0 1 2 3 4 5 6 7 8
X: 1 0 1 0 1 0 0 0 0
O: 0 1 0 1 0 0 0 1 0

Notice that the bits for player X are disjoint from the bits for player O, this is obvious because X can't put a piece where O has a piece and vice versa.

To check whether a player has won, we need to compare all the positions covered by that player to a position we know is a win-position. In this case, the easiest way to do that would be by AND-gating the player-position and the win-position and seeing if the two are equal.

boolean isWinner(short X) {
    for (int i = 0; i < 8; i++)
        if ((X & winCombinations[i]) == winCombinations[i])
            return true;
    return false;
}

eg.

X: 111001010
W: 111000000 // win position, all same across first row.
------------
&: 111000000

Note: X & W = W, so X is in a win state.

This is a constant time solution, it depends only on the number of win-positions, because applying AND-gate is a constant time operation and the number of win-positions is finite.

It also simplifies the task of enumerating all valid board states, their just all the numbers representable by 9 bits. But of course you need an extra condition to guarantee a number is a valid board state (eg. 0b111111111 is a valid 9-bit number, but it isn't a valid board state because X has just taken all the turns).

The number of possible win positions can be generated on the fly, but here they are anyways.

short[] winCombinations = new short[] {
  // each row
  0b000000111,
  0b000111000,
  0b111000000,
  // each column
  0b100100100,
  0b010010010,
  0b001001001,
  // each diagonal
  0b100010001,
  0b001010100
};

To enumerate all board positions, you can run the following loop. Although I'll leave determining whether a number is a valid board state upto someone else.

NOTE: (2**9 - 1) = (2**8) + (2**7) + (2**6) + ... (2**1) + (2**0)

for (short X = 0; X < (Math.pow(2,9) - 1); X++)
   System.out.println(isWinner(X));