Friday, July 18, 2014

Check if someone has won tic-tac-toe

Problem

Design an algorithm to figure out if someone has won in a game of tic-tac-toe.

Solution

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.
Suppose instead of 9 space, 2D matrix we have nXn matrix.
We 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.
public class TicTacToe {

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

References

0 comments:

Post a Comment