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