Ben Lakey - 10 months ago 89
Java Question

# Algorithm for Determining Tic Tac Toe Game Over

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 ... }?

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.

edit: this code is for an n by n board with n in a row to win (3x3 board requries 3 in a row, etc)

edit: added code to check anti diag, I couldn't figure out a non loop way to determine if the point was on the anti diag so thats why that step is missing

``````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 == (n^2 - 1)){
//report draw
}
}
}
``````