Algorithm for Determining Tic Tac Toe Game Over

Solution 1:

You know a winning move can only happen after X or O has made their most recent move, so you can only search row/column with optional diag that are contained in that move to limit your search space when trying to determine a winning board. Also since there are a fixed number of moves in a draw tic-tac-toe game once the last move is made if it wasn't a winning move it's by default a draw game.

This code is for an n by n board with n in a row to win (3x3 board requires 3 in a row, etc)

public class TripleT {
    
    enum State{Blank, X, O};
    
    int n = 3;
    State[][] board = new State[n][n];
    int moveCount;
    
    void Move(int x, int y, State s){
        if(board[x][y] == State.Blank){
            board[x][y] = s;
        }
        moveCount++;
        
        //check end conditions
        
        //check col
        for(int i = 0; i < n; i++){
            if(board[x][i] != s)
                break;
            if(i == n-1){
                //report win for s
            }
        }
        
        //check row
        for(int i = 0; i < n; i++){
            if(board[i][y] != s)
                break;
            if(i == n-1){
                //report win for s
            }
        }
        
        //check diag
        if(x == y){
            //we're on a diagonal
            for(int i = 0; i < n; i++){
                if(board[i][i] != s)
                    break;
                if(i == n-1){
                    //report win for s
                }
            }
        }
            
        //check anti diag (thanks rampion)
        if(x + y == n - 1){
            for(int i = 0; i < n; i++){
                if(board[i][(n-1)-i] != s)
                    break;
                if(i == n-1){
                    //report win for s
                }
            }
        }

        //check draw
        if(moveCount == (Math.pow(n, 2) - 1)){
            //report draw
        }
    }
}

Solution 2:

you can use a magic square http://mathworld.wolfram.com/MagicSquare.html if any row, column, or diag adds up to 15 then a player has won.

Solution 3:

How about this pseudocode:

After a player puts down a piece at position (x,y):

col=row=diag=rdiag=0
winner=false
for i=1 to n
  if cell[x,i]=player then col++
  if cell[i,y]=player then row++
  if cell[i,i]=player then diag++
  if cell[i,n-i+1]=player then rdiag++
if row=n or col=n or diag=n or rdiag=n then winner=true

I'd use an array of char [n,n], with O,X and space for empty.

1. simple.
2. One loop.
3. Five simple variables: 4 integers and one boolean.
4. Scales to any size of n.
5. Only checks current piece.
6. No magic. :)

Solution 4:

This is similar to Osama ALASSIRY's answer, but it trades constant-space and linear-time for linear-space and constant-time. That is, there's no looping after initialization.

Initialize a pair (0,0) for each row, each column, and the two diagonals (diagonal & anti-diagonal). These pairs represent the accumulated (sum,sum) of the pieces in the corresponding row, column, or diagonal, where

A piece from player A has value (1,0)
A piece from player B has value (0,1)

When a player places a piece, update the corresponding row pair, column pair, and diagonal pairs (if on the diagonals). If any newly updated row, column, or diagonal pair equals either (n,0) or (0,n) then either A or B won, respectively.

Asymptotic analysis:

O(1) time (per move)
O(n) space (overall)

For the memory use, you use 4*(n+1) integers.

two_elements*n_rows + two_elements*n_columns +
two_elements*two_diagonals = 4*n + 4 integers = 4(n+1) integers

Exercise: Can you see how to test for a draw in O(1) time per-move? If so, you can end the game early on a draw.