tic-tac-toe Who Won - Cracking the coding interview--Q19.2

Cracking the coding interview--Q19.2
Design an algorithm to figure out if someone has won in a game of tic-tac-toe.
设计算法检查某人是否赢得了井字游戏。

Tic-tac-toe (also known as Noughts and crosses or Xs and Os) is a paper-and-pencil game for two players, X and O, who take turns marking the spaces in a 3×3 grid. The player who succeeds in placing three of their marks in a horizontal, vertical, or diagonal row wins the game.

假设这个检查某人是否赢得了井字游戏的函数为HasWon，那么我们第一步要向面试官确认， 这个函数是只调用一次，还是要多次频繁调用。如果是多次调用， 我们可以通过预处理来得到一个非常快速的版本。

方法一：如果HasWon函数需要被频繁调用对于井字游戏，每个格子可以是空，我的棋子和对方的棋子3种可能，总共有3⁹ = 19683 种可能状态。我们可以把每一种状态转换成一个整数， 预处理时把这个状态下是否有人赢得了井字游戏保存起来，每次检索时就只需要O(1)时间。 比如每个格子上的3种状态为0(空)，1(我方棋子)，2(对方棋子)，棋盘从左到右， 从上到下依次记为0到8，那么任何一个状态都可以写成一个3进制的数，再转成10进制即可。 比如，下面的状态：

 // 方法一：如果HasWon函数需要被频繁调用
 public static int convertBoardToInt(char[][] board) {
        int factor = 1;
        int sum = 0;
        for (int i = 0; i < board.length; i++) {
                for (int j = 0; j < board[i].length; j++) {
                        int v = 0;
                        switch(board[i][j]){
                         case 'x':
                          v = 1;
                          break;
                         case 'o':
                          v = 2;
                          break;
                         default:
                          v = 0;
                        }
                        
                        sum += v * factor;
                        factor *= 3;
                }
        }
        return sum;
 }

方法二：如果HasWon函数只被调用一次或很少次

http://blog.csdn.net/fightforyourdream/article/details/17066247
https://github.com/yxjiang/algorithms/blob/master/src/main/java/algorithm/cc150/chapter17/Question2.java

	public boolean won(char[][] board) { // write implementation here
	if (checkDiagonal(board) || checkCounterDiagonal(board)) {
	return true;
	}
	for (int i = 0; i < board.length; ++i) {
	if (checkRow(i, board) || checkCol(i, board)) {
	return true;
	}
	}
	return false;
	}
	private boolean checkRow(int row, char[][] board) {
	for (int i = 0; i < board.length - 1; ++i) {
	if (board[row][i] != board[row][i + 1]) {
	return false;
	}
	}
	if (board[row][0] != '.') {
	return true;
	}
	return false;
	}
	private boolean checkCol(int col, char[][] board) {
	for (int i = 0; i < board.length - 1; ++i) {
	if (board[i][col] != board[i + 1][col]) {
	return false;
	}
	}
	if (board[0][col] != '.') {
	return true;
	}
	return false;
	}
	private boolean checkDiagonal(char[][] board) {
	char type = board[0][0];
	for (int i = 1; i < board.length; ++i) {
	if (board[i][i] != type) {
	return false;
	}
	}
	if (type != '.') {
	return true;
	}
	return false;
	}
	private boolean checkCounterDiagonal(char[][] board) {
	char type = board[board.length - 1][0];
	for (int i = 1; i < board.length; ++i) {
	if (board[i][board.length - 1 - i] != type) {
	return false;
	}
	}
	if (type != '.') {
	return true;
	}
	return false;
	}

1. Will has Won be called just once or many times (for instance, as part of a tic-tac-toe website)? If the latter is the case, we may want to add pre-processing time to optimize the runtime of ha sWon.

2. Do we know the last move that was made?

3. Tic-tac-toe is usually on a 3x3 board. Do we want to design for just that, or do we want to implement it as an NxN solution?

There are only 39, or about 20,000, tic-tac-toe boards (assuming a 3x3 board). Therefore, we can 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 hash table or array in advance with all possible boards as keys and the value indicating who has won.

Piece hasWon(int board) {
        return winnerHashtable[board];
}
enum Piece { Empty, Red, Blue};

int convertBoardToint(Piece[][] board) {
        int sum = 0;
        for (int i= 0; i < board.length; i++) {
                for (int j = 0; j < board[i].length; j++) {
                        /* Each value in enum has an integer associated with it. We
                         * can just use that. */
                        int value = board[i][j].ordinal();
                        sum = sum * 3 + value;
                }
        }
        return sum;
}

Solution #2: If we know the last move

If we know the very last move that was made (and we've been checking for a winner up until now), then we only need to check the row, column, and diagonal that overlaps with this position.

Piece hasWon(Piece[][] board, int row, int column) {
        if (board.length != board[0].length) return Piece.Empty;

        Piece piece = board[row][column];
        if (piece == Piece.Empty) return Piece.Empty;

        if (hasWonRow(board, row) I I hasWonColumn(board, column)) {
                return piece;
        }

        if (row == column && haswonDiagonal(board, 1)) {
                return piece;
        }

        if (row == (board.length - column - 1) && hasWonDiagonal(board, -1)) {
                return piece;
        }
        return Piece.Empty;
}

boolean hasWonRow(Piece[][] board, int row) {
        for (int c = 1; c < board[row].length; c++) {
                if (board[row][c] != board[row][0]) {
                        return false;
                }
        }
        return true;
}

boolean hasWonColumn(Piece[][] board, int column) {
        for (int r = 1; r < board.length; r++) {
                if (board[r][column] != board[0][column]) {
                        return false;
                }
        }
        return true;
}

boolean hasWonDiagonal(Piece[][] board, int direction) {
        int row = 0;
        int column = direction == 1 ? 0 : board.length - 1;
        Piece first= board[0][column];
        for (int i= 0; i < board.length; i++) {
                if (board[row][column] != first) {
                        return false;
                }
                row += 1;
                column += direction;
        }
        return true;
}

Solution #3: Designing for just a 3x3 board

Piece hasWon(Piece[][] board) {

        for (int i= 0; i < board.length; i++) {

                /* Check Rows */

                if (hasWinner(board[i][0], board[i][l], board[i][2])) {

                        return board[i][0];

                }

                /* Check Columns */

                if (hasWinner(board[0][i], board[l][i], board[2][i])) {

                        return board[0][i];

                }

        }

        if (hasWinner(board[0][0], board[l][l], board[2][2])) {

                return board[0][0];

        }

        if (hasWinner(board[0][2], board[l][l], board[2][0])) {

                return board[0][2];

        }

        return Piece.Empty;

}

boolean hasWinner(Piece pl, Piece p2, Piece p3) {

        if (pl == Piece.Empty) {

                return false;

        }

        return pl== p2 && p2 == p3;

}

Solution #4: Designing for an NxN board

Read full article from Cracking the coding interview--Q19.2