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(); } }
Questions on Stack, Queues, Linkedlist, Binary Trees, Sorting, Searching, Graphs etc with solution using Java Language.
Thursday, 21 May 2015
Design an algorithm to figure out if someone has won a game of tic-tac-toe
Labels:
Brain Teasers
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment