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

- 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]; }- 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

Lucky

Feb 13, 2013@ 12:09:13Hey did you understand the given solution, I am banging my head but not able to understand…please share any info on the given solution..