This blog will soon be merged with

JavaByPatel

which explains each solution in detail, to visit new blog, click JavaByPatel

Thursday, 21 May 2015

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


package tic.tac.toe;

// Design an algorithm to figure out if someone has won a game of tic-tac-toe
public class TicTacToe {
 public static void main(String[] args) {
  TicTacToeBoard t = new TicTacToeBoard();
  t.move(0, 0, TicTacToeBoard.BoardState.X);
  t.move(0, 1, TicTacToeBoard.BoardState.O);
  t.move(0, 1, TicTacToeBoard.BoardState.X);
  t.move(1, 0, TicTacToeBoard.BoardState.O);
  t.move(1, 1, TicTacToeBoard.BoardState.X);
  t.move(1, 2, TicTacToeBoard.BoardState.O);
  t.move(2, 0, TicTacToeBoard.BoardState.X);
  t.move(2, 2, TicTacToeBoard.BoardState.O);
  t.move(2, 1, TicTacToeBoard.BoardState.X);
 }
}

class TicTacToeBoard{

 public enum BoardState{
  BLANK(0), X(1), O(2);

  private final int value;

  private BoardState(int value) {
   this.value = value;
  }
  public int getValue() {
   return value;
  }
 };

 int totalMovesTillNow=0;
 int n = 3;
 BoardState board[][] = new BoardState[n][n];

 public TicTacToeBoard() {
  for (int i = 0; i < board.length; i++) {
   for (int j = 0; j < board.length; j++) {
    board[i][j] = BoardState.BLANK;
   }
  }
 }

 public void move(int x, int y, BoardState state) {
  if(board[x][y]!=BoardState.BLANK){
   return;
  }

  totalMovesTillNow++;
  board[x][y]=state;

  //Now Check if winning situation occured.
  //Row Wise Checking.
  boolean isWon=true;
  for(int i=0;i<board.length;i++){
   if(board[x][i]!=state){
    isWon=false;
    break;
   }
  }
  if(isWon){
   System.out.println(state.name() +" won");
   return;
  }

  //Column Wise Checking.  
  isWon=true;
  for(int i=0;i<board.length;i++){
   if(board[i][y]!=state){
    isWon=false;
    break;
   }
  }
  if(isWon){
   System.out.println(state.name() +" won");
   return;
  }

  //Diagonal Check if x and y are at extreme ends, where diagonal situation is possible
  //there are 2 diagonals, left side(\) and right side(/) diagonal, 
  //diagonal check we need to check only if x and y falls there, this condition is very easy for left side diagonal as x and y will always be same for left diagonal.
  //For right diagonal this pattern is not possible, so better to check it in every move.

  //Right diagonal Checking.
  isWon=true;
  for(int i=board.length-1;i>=0;i--){
   if(board[(board.length-1)-i][i]!=state){
    isWon=false;
    break;
   }
  }
  if(isWon){
   System.out.println(state.name() +" won");
   return;
  }

  //if x==y then only go for Left diagonal Checking.
  isWon=true;
  if(x==y){
   for(int i=0;i<board.length;i++){
    if(board[i][i]!=state){
     isWon=false;
     break;
    }
   }
   if(isWon){
    System.out.println(state.name() +" won");
    return;
   }
  }

  //Check Draw Match
  if(totalMovesTillNow == (n*n)-1){
   System.out.println("Match Draw");
   return;
  }

  printBoard();
 }

 public void printBoard(){
  System.out.println();
  for (int i = 0; i < board.length; i++) {
   for (int j = 0; j < board.length; j++) {
    System.out.print(board[i][j] + "\t");
   } 
   System.out.println();
  }
  System.out.println();
 }
}



No comments:

Post a Comment