Algorithm for Determining Tic Tac Toe Game Over

Question

I've written a game of tic-tac-toe in Java, and my current method of determining the end of the game accounts for the following possible scenarios for the game being over:

1. The board is full, and no winner has yet been declared: Game is a draw.
2. Cross has won.
3. Circle has won.

Unfortunately, to do so, it reads through a predefined set of these scenarios from a table. This isn't necessarily bad considering that there are only 9 spaces on a board, and thus the table is somewhat small, but is there a better algorithmic way of determining if the game is over? The determination of whether someone has won or not is the meat of the problem, since checking if 9 spaces are full is trivial.

The table method might be the solution, but if not, what is? Also, what if the board were not size n=9? What if it were a much larger board, say n=16, n=25, and so on, causing the number of consecutively placed items to win to be x=4, x=5, etc? A general algorithm to use for all n = { 9, 16, 25, 36 ... }?

Answer 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         }     } } 

Answer 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.