Check if someone has won tic-tac-toe

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

My initial codes:

	/**
	 * @param board
	 *        2D array of char representation of board 
	 *        '*' - player 0 
	 *        'o' - player 1
	 * @return 1: no one won 
	 *         0: player 0 won 
	 *         1: player 1 won
	 */
	public static int checkTicTacToe(char[][] board) {
		int n = board.length;

		// horizontally
		for (int row = 0; row < n; ++row) {
			boolean player0Won = true;
			for (int col = 0; col < n; ++col) {
				player0Won &= board[row][col] == '*';
			}
			if (player0Won)
				return 0;

			boolean player1Won = true;
			for (int col = 0; col < n; ++col) {
				player1Won &= board[row][col] == 'o';
			}
			if (player1Won)
				return 1;
		}

		// vertically
		for (int col = 0; col < n; ++col) {
			boolean player0Won = true;
			for (int row = 0; row < n; ++row) {
				player0Won &= board[row][col] == '*';
			}
			if (player0Won)
				return 0;

			boolean player1Won = true;
			for (int row = 0; row < n; ++row) {
				player1Won &= board[row][col] == 'o';
			}
			if (player1Won)
				return 1;
		}

		// diagonally
		boolean player0Won = true;
		for (int i = 0; i < n; ++i) {
			player0Won &= board[i][i] == '*';
		}
		if (player0Won)
			return 0;

		boolean player1Won = true;
		for (int i = 0; i < n; ++i) {
			player1Won &= board[i][i] == 'o';
		}
		if (player1Won)
			return 1;

		// reverse-diagonally
		player0Won = true;
		for (int i = 0; i < n; ++i) {
			player0Won &= board[i][n - i] == '*';
		}
		if (player0Won)
			return 0;

		player1Won = true;
		for (int i = 0; i < n; ++i) {
			player1Won &= board[i][n - i] == 'o';
		}
		if (player1Won)
			return 1;

		return -1;
	}

Solution:
The first thing to ask your interviewer is whether the hasWon function will be called just once, or multiple times. If it will be called multiple times, you can get a very fast algorithm by amortizing the cost (especially if you can design your own data storage system for the tic-tac-toe board).

  1. Approach #1: If hasWon is called many times
    There are only 3^9, or about twenty thousand tic-tac-toe boards. We can thus represent our tic-tac-toe board as an int, with each digit representing a piece (0 means Empty, 1 means Red, 2 means Blue). We set up a hashtable or array in advance with all possible boards as keys, and the values are 0, 1, and 2 Our function then is simply this:

    	int hasWon(int board) {
    		return winnerHashtable[board];
    	}
    
  2. Approach #2: If hasWon is only called once
    	enum Piece {
    		Empty, Red, Blue
    	};
    
    	enum Check {
    		Row, Column, Diagonal, ReverseDiagonal
    	}
    
    	Piece getIthColor(Piece[][] board, int index, int var, Check check) {
    		if (check == Check.Row)
    			return board[index][var];
    		else if (check == Check.Column)
    			return board[var][index];
    		else if (check == Check.Diagonal)
    			return board[var][var];
    		else if (check == Check.ReverseDiagonal)
    			return board[board.length - 1 - var][var];
    		return Piece.Empty;
    	}
    
    	Piece getWinner(Piece[][] board, int fixed_index, Check check) {
    		Piece color = getIthColor(board, fixed_index, 0, check);
    		if (color == Piece.Empty)
    			return Piece.Empty;
    		for (int var = 1; var < board.length; var++) {
    			if (color != getIthColor(board, fixed_index, var, check)) {
    				return Piece.Empty;
    			}
    		}
    		return color;
    	}
    
    	Piece hasWon(Piece[][] board) {
    		int N = board.length;
    		Piece winner = Piece.Empty;
    		// Check rows and columns
    		for (int i = 0; i < N; i++) {
    			winner = getWinner(board, i, Check.Row);
    			if (winner != Piece.Empty) {
    				return winner;
    			}
    
    			winner = getWinner(board, i, Check.Column);
    			if (winner != Piece.Empty) {
    				return winner;
    			}
    		}
    
    		winner = getWinner(board, -1, Check.Diagonal);
    		if (winner != Piece.Empty) {
    			return winner;
    		}
    
    		// Check diagonal
    		winner = getWinner(board, -1, Check.ReverseDiagonal);
    		if (winner != Piece.Empty) {
    			return winner;
    		}
    
    		return Piece.Empty;
    	}
    
    Advertisements

1 Comment (+add yours?)

  1. Lucky
    Feb 13, 2013 @ 12:09:13

    Hey did you understand the given solution, I am banging my head but not able to understand…please share any info on the given solution..

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: