https://leetcode.com/problems/valid-tic-tac-toe-state/description/
http://www.cnblogs.com/grandyang/p/9223105.html
首先我们要先熟悉下Tic-Tac-Toe三连棋游戏规则，就是两人轮流在九格方盘上画'X'或者'O'，谁先把三个相同记号排成横线、直线、斜线，即游戏结束。
那么我们从游戏规则中来找处所有不合理的状态。
根据规则1和2，假设X的数目为countX, O的数目为countO，那么我们可以得到countX==countO，或者countX - countO == 1。
根据游戏结束后则不能再画O和X，那么当countX==count时，如果存在三个X排成横线、直线、斜线，那么即是不合理的，因为X先画，当三个X排成横线、直线、斜线时， 此时游戏结束，不能再画O，所以O的数目应该比X的数目少1。
当countX - countO == 1时，如果存在三个O排成横线、直线、斜线，那么是不合理的，因为当三个O排成横线、直线、斜线时，游戏结束，不能再画X，所以此时X的数目应该和O的数目相等。
https://leetcode.com/problems/valid-tic-tac-toe-state/discuss/124024/Simple-Rule-Java-Solution
http://bookshadow.com/weblog/2018/03/04/leetcode-valid-tic-tac-toe-state/
def validTicTacToe(self, board): """ :type board: List[str] :rtype: bool """ nx = ''.join(board).count('X') no = ''.join(board).count('O') wx, wo = self.isWin(board, 'X'), self.isWin(board, 'O') if wx: return nx == no + 1 and not wo if wo: return nx == no return nx - 1 <= no <= nx def isWin(self, board, pc): if any(r == pc * 3 for r in board): return True if any(c == pc * 3 for c in zip(*board)): return True if board[0][0] == board[1][1] == board[2][2] == pc: return True if board[0][2] == board[1][1] == board[2][0] == pc: return True return False
https://www.geeksforgeeks.org/validity-of-a-given-tic-tac-toe-board-configuration/
Basically, to find the validity of an input grid, we can think of the conditions when an input grid is invalid. Let no. of “X”s be countX and no. of “O”s be countO. Since we know that the game starts with X, a given grid of Tic-Tac-Toe game would be definitely invalid if following two conditions meet
a) countX != countO AND
b) countX != countO + 1
A Tic-Tac-Toe board is given as a string array
board. Return True if and only if it is possible to reach this board position during the course of a valid tic-tac-toe game.
The
board is a 3 x 3 array, and consists of characters " ", "X", and "O". The " " character represents an empty square.
Here are the rules of Tic-Tac-Toe:
- Players take turns placing characters into empty squares (" ").
- The first player always places "X" characters, while the second player always places "O" characters.
- "X" and "O" characters are always placed into empty squares, never filled ones.
- The game ends when there are 3 of the same (non-empty) character filling any row, column, or diagonal.
- The game also ends if all squares are non-empty.
- No more moves can be played if the game is over.
Example 1: Input: board = ["O ", " ", " "] Output: false Explanation: The first player always plays "X". Example 2: Input: board = ["XOX", " X ", " "] Output: false Explanation: Players take turns making moves. Example 3: Input: board = ["XXX", " ", "OOO"] Output: false Example 4: Input: board = ["XOX", "O O", "XOX"] Output: true
Note:
boardis a length-3 array of strings, where each stringboard[i]has length 3.- Each
board[i][j]is a character in the set{" ", "X", "O"}.
这道题又是关于井字棋游戏的，之前也有一道类似的题Design Tic-Tac-Toe，不过那道题是模拟游戏进行的，而这道题是让我们验证当前井字棋的游戏状态是否正确。这题的例子给的比较好，cover了很多种情况：
情况一：
0 _ _ _ _ _ _ _ _
这是不正确的状态，因为先走的使用X，所以只出现一个O，是不对的。
情况二：
X O X
_ X _
_ _ _
这个也是不正确的，因为两个player交替下棋，X最多只能比O多一个，这里多了两个，肯定是不对的。
情况三：
X X X
_ _ _
O O O
这个也是不正确的，因为一旦第一个玩家的X连成了三个，那么游戏马上结束了，不会有另外一个O出现。
情况四：
X O X
O _ O
X O X
这个状态没什么问题，是可以出现的状态。
好，那么根据给的这些例子，我们可以分析一下规律，根据例子1和例子2我们得出下棋顺序是有规律的，必须是先X后O，不能破坏这个顺序，那么我们可以使用一个turns变量，当是X时，turns自增1，反之若是O，则turns自减1，那么最终turns一定是0或者1，其他任何值都是错误的，比如例子1中，turns就是-1，例子2中，turns是2，都是不对的。根据例子3，我们得出结论，只能有一个玩家获胜，那么我们可以用两个变量xwin和owin，来记录两个玩家的获胜状态，由于井字棋的制胜规则是横竖斜任意一个方向有三个连续的就算赢，那么我们分别在各个方向查找3个连续的X，有的话xwin赋值为true，还要查找3个连续的O，有的话owin赋值为true，例子3中xwin和owin同时为true了，是错误的。还有一种情况，例子中没有cover到的是：
情况五：
X X X
O O _
O _ _
我们看到虽然只有xwin为true，但是这种状态还是错误的，因为一旦第三个X放下后，游戏立即结束，不会有第三个O放下，这么检验这种情况呢？这是我们的turns变量就非常的重要了，当第三个O放下后，turns自减1，此时turns为0了，而正确的应该是当xwin为true的时候，第三个O不能放下，那么turns不减1，则还是1，这样就可以区分情况五了。当然，我们可以交换X和O的位置，即当owin为true时，turns一定要为0。现在我们已经覆盖了搜索的情况了
https://leetcode.com/problems/valid-tic-tac-toe-state/discuss/117580/Straightforward-Java-solution-with-explaination
When
turns is 1, X moved. When turns is 0, O moved. rows stores the number of X or O in each row. cols stores the number of X or O in each column. diag stores the number of X or O in diagonal. antidiag stores the number of X or O in antidiagonal. When any of the value gets to 3, it means X wins. When any of the value gets to -3, it means O wins.
When X wins, O cannot move anymore, so
turns must be 1. When O wins, X cannot move anymore, so turns must be 0. Finally, when we return, turns must be either 0 or 1, and X and O cannot win at same time. public boolean validTicTacToe(String[] board) {
int turns = 0;
boolean xwin = false;
boolean owin = false;
int[] rows = new int[3];
int[] cols = new int[3];
int diag = 0;
int antidiag = 0;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (board[i].charAt(j) == 'X') {
turns++; rows[i]++; cols[j]++;
if (i == j) diag++;
if (i + j == 2) antidiag++;
} else if (board[i].charAt(j) == 'O') {
turns--; rows[i]--; cols[j]--;
if (i == j) diag--;
if (i + j == 2) antidiag--;
}
}
}
xwin = rows[0] == 3 || rows[1] == 3 || rows[2] == 3 ||
cols[0] == 3 || cols[1] == 3 || cols[2] == 3 ||
diag == 3 || antidiag == 3;
owin = rows[0] == -3 || rows[1] == -3 || rows[2] == -3 ||
cols[0] == -3 || cols[1] == -3 || cols[2] == -3 ||
diag == -3 || antidiag == -3;
if (xwin && turns == 0 || owin && turns == 1) {
return false;
}
return (turns == 0 || turns == 1) && (!xwin || !owin);
}首先我们要先熟悉下Tic-Tac-Toe三连棋游戏规则，就是两人轮流在九格方盘上画'X'或者'O'，谁先把三个相同记号排成横线、直线、斜线，即游戏结束。
那么我们从游戏规则中来找处所有不合理的状态。
根据规则1和2，假设X的数目为countX, O的数目为countO，那么我们可以得到countX==countO，或者countX - countO == 1。
根据游戏结束后则不能再画O和X，那么当countX==count时，如果存在三个X排成横线、直线、斜线，那么即是不合理的，因为X先画，当三个X排成横线、直线、斜线时， 此时游戏结束，不能再画O，所以O的数目应该比X的数目少1。
当countX - countO == 1时，如果存在三个O排成横线、直线、斜线，那么是不合理的，因为当三个O排成横线、直线、斜线时，游戏结束，不能再画X，所以此时X的数目应该和O的数目相等。
public boolean validTicTacToe(String[] board) {
char[][] boardChar = new char[3][3];
for (int i = 0; i < board.length; i++) {
boardChar[i] = board[i].toCharArray();
}
int countX = 0;
int countO = 0;
for (int i = 0; i < boardChar.length; i++) {
for (int j = 0; j < boardChar[i].length; j++) {
if (boardChar[i][j] == 'X') {
countX++;
} else if (boardChar[i][j] == 'O') {
countO++;
}
}
}
if (countO > countX || countX - countO > 1) {
return false;
}
if (countX - countO == 1) {
if(!helper(boardChar, 'O')) {
return false;
}
} else if (countX == countO) {
if(!helper(boardChar, 'X')) {
return false;
}
}
return true;
}
private boolean helper(char[][] boardChar, char ch) {
for (int i = 0; i < 3; i++) {
if (boardChar[i][0] == ch && boardChar[i][0] == boardChar[i][1] && boardChar[i][1] == boardChar[i][2]) {
return false;
}
if (boardChar[0][i] == ch && boardChar[0][i] == boardChar[1][i] && boardChar[1][i] == boardChar[2][i]) {
return false;
}
}
if (boardChar[0][0] == ch && boardChar[0][0] == boardChar[1][1] && boardChar[1][1] == boardChar[2][2]) {
return false;
}
if (boardChar[0][2] == ch && boardChar[0][2] == boardChar[1][1] && boardChar[1][1] == boardChar[2][0]) {
return false;
}
return true;
}http://bookshadow.com/weblog/2018/03/04/leetcode-valid-tic-tac-toe-state/
def validTicTacToe(self, board): """ :type board: List[str] :rtype: bool """ nx = ''.join(board).count('X') no = ''.join(board).count('O') wx, wo = self.isWin(board, 'X'), self.isWin(board, 'O') if wx: return nx == no + 1 and not wo if wo: return nx == no return nx - 1 <= no <= nx def isWin(self, board, pc): if any(r == pc * 3 for r in board): return True if any(c == pc * 3 for c in zip(*board)): return True if board[0][0] == board[1][1] == board[2][2] == pc: return True if board[0][2] == board[1][1] == board[2][0] == pc: return True return False
https://www.geeksforgeeks.org/validity-of-a-given-tic-tac-toe-board-configuration/
Basically, to find the validity of an input grid, we can think of the conditions when an input grid is invalid. Let no. of “X”s be countX and no. of “O”s be countO. Since we know that the game starts with X, a given grid of Tic-Tac-Toe game would be definitely invalid if following two conditions meet
a) countX != countO AND
b) countX != countO + 1
Since “X” is always the first move, second condition is also required.
Now does it mean that all the remaining board positions are valid one? The answer is NO. Think of the cases when input grid is such that both X and O are making straight lines. This is also not valid position because the game ends when one player wins. So we need to check the following condition as well
c) If input grid shows that both the players are in winning situation, it’s an invalid position.
d) If input grid shows that the player with O has put a straight-line (i.e. is in win condition) and countX != countO, it’s an invalid position. The reason is that O plays his move only after X plays his move. Since X has started the game, O would win when both X and O has played equal no. of moves.
e) If input grid shows that X is in winning condition than xCount must be one greater that oCount.
c) If input grid shows that both the players are in winning situation, it’s an invalid position.
d) If input grid shows that the player with O has put a straight-line (i.e. is in win condition) and countX != countO, it’s an invalid position. The reason is that O plays his move only after X plays his move. Since X has started the game, O would win when both X and O has played equal no. of moves.
e) If input grid shows that X is in winning condition than xCount must be one greater that oCount.
Armed with above conditions i.e. a), b), c) and d), we can now easily formulate an algorithm/program to check the validity of a given Tic-Tac-Toe board position.
1) countX == countO or countX == countO + 1
2) If O is in win condition then check
a) If X also wins, not valid
b) If xbox != obox , not valid
3) If X is in win condition then check if xCount is
one more than oCount or not
Another way to find the validity of a given board is using ‘inverse method’ i.e. rule out all the possibilities when a given board is invalid.
