給定井字棋盤配置的有效性 · GeeksForGeeks 中文系列教程

# 給定井字棋盤配置的有效性 > 原文： [https://www.geeksforgeeks.org/validity-of-a-given-tic-tac-toe-board-configuration/](https://www.geeksforgeeks.org/validity-of-a-given-tic-tac-toe-board-configuration/) 播放一些動作后，將顯示井字游戲棋盤。找出給定的板是否有效，即是否可以在某些移動之后到達該板位置。請注意，每個由 9 個空格組成的任意填充網格都是無效的，例如充滿 3 個 X 和 6 個 O 的網格是無效的情況，因為每個玩家都需要輪流交替進行。 [![tictactoe](https://img.kancloud.cn/e4/57/e45729c7e99f413ddc3630620000a09a_639x407.png)](https://media.geeksforgeeks.org/wp-content/cdn-uploads/tictactoe.png) 輸入為大小為 9 的一維數組。 **示例**： ``` Input: board[] = {'X', 'X', 'O', 'O', 'O', 'X', 'X', 'O', 'X'}; Output: Valid Input: board[] = {'O', 'X', 'X', 'O', 'X', 'X', 'O', 'O', 'X'}; Output: Invalid (Both X and O cannot win) Input: board[] = {'O', 'X', ' ', ' ', ' ', ' ', ' ', ' ', ' '}; Output: Valid (Valid board with only two moves played) ``` 基本上，要找到輸入網格的有效性，我們可以考慮輸入網格無效時的條件。不行 X 的數字為 countX，否。的“ O”為 countO。由于我們知道游戲以 X 開頭，因此，如果以下兩個條件滿足，a）countX！= countO 和 b）countX！= countO + 1，則給定的井字游戲網格絕對無效。由于“ X”始終是第一個動作，因此也需要第二個條件。現在是否意味著所有剩余的董事會職位都是有效的？答案是不。考慮一下輸入網格使得 X 和 O 都成直線的情況。這也是無效位置，因為當一名玩家獲勝時游戲結束。因此，我們還需要檢查以下情況 c）如果輸入網格顯示兩個玩家都處于獲勝狀態，則該位置無效。 d）如果輸入網格顯示 O 的玩家放置了一條直線（即處于獲勝狀態）并且 countX！= countO，則該位置無效。原因是 O 僅在 X 出手后才出手。自從 X 開始游戲以來，當 X 和 O 都玩過等于 No 的 O 時，O 將獲勝。的動作。 e）如果輸入網格顯示 X 處于獲勝條件，則 xCount 必須比 oCount 大 1。有了上述條件，即 a），b），c）和 d），我們現在可以輕松地制定算法/程序來檢查給定 Tic-Tac-Toe 板位置的有效性。 ``` 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 ``` 確定給定板的有效性的另一種方法是使用“反向方法”，即排除給定板無效時的所有可能性。 ## C++ ```cpp // C++ program to check whether a given tic tac toe // board is valid or not #include <iostream> using namespace std; // This matrix is used to find indexes to check all // possible wining triplets in board[0..8] int win[8][3] = {{0, 1, 2}, // Check first row. ????????????????{3, 4, 5}, // Check second Row ????????????????{6, 7, 8}, // Check third Row ????????????????{0, 3, 6}, // Check first column ????????????????{1, 4, 7}, // Check second Column ????????????????{2, 5, 8}, // Check third Column ????????????????{0, 4, 8}, // Check first Diagonal ????????????????{2, 4, 6}}; // Check second Diagonal // Returns true if character 'c' wins. c can be either // 'X' or 'O' bool isCWin(char *board, char c) { ????// Check all possible winning combinations ????for (int i=0; i<8; i++) ????????if (board[win[i][0]] == c && ????????????board[win[i][1]] == c && ????????????board[win[i][2]] == c ) ????????????return true; ????return false; } // Returns true if given board is valid, else returns false bool isValid(char board[9]) { ????// Count number of 'X' and 'O' in the given board ????int xCount=0, oCount=0; ????for (int i=0; i<9; i++) ????{ ????if (board[i]=='X') xCount++; ????if (board[i]=='O') oCount++; ????} ????// Board can be valid only if either xCount and oCount ????// is same or xount is one more than oCount ????if (xCount==oCount || xCount==oCount+1) ????{ ????????// Check if 'O' is winner ????????if (isCWin(board, 'O')) ????????{ ????????????// Check if 'X' is also winner, then ????????????// return false ????????????if (isCWin(board, 'X')) ????????????????return false; ????????????// Else return true xCount and yCount are same ????????????return (xCount == oCount); ????????} ????????// If 'X' wins, then count of X must be greater ????????if (isCWin(board, 'X') && xCount != oCount + 1) ????????return false;? ????????// If 'O' is not winner, then return true ????????return true; ????} ????return false; } // Driver program int main() { char board[] = {'X', 'X', 'O', ????????????????'O', 'O', 'X', ????????????????'X', 'O', 'X'}; (isValid(board))? cout << "Given board is valid": ????????????????????cout << "Given board is not valid"; return 0; } ``` ## Java ```java // Java program to check whether a given tic tac toe? // board is valid or not?? class GFG { // This matrix is used to find indexes to check all? // possible wining triplets in board[0..8]? ????static int win[][] = {{0, 1, 2}, // Check first row.? ????{3, 4, 5}, // Check second Row? ????{6, 7, 8}, // Check third Row? ????{0, 3, 6}, // Check first column? ????{1, 4, 7}, // Check second Column? ????{2, 5, 8}, // Check third Column? ????{0, 4, 8}, // Check first Diagonal? ????{2, 4, 6}}; // Check second Diagonal? // Returns true if character 'c' wins. c can be either? // 'X' or 'O'? ????static boolean isCWin(char[] board, char c) { ????????// Check all possible winning combinations? ????????for (int i = 0; i < 8; i++) { ????????????if (board[win[i][0]] == c ????????????????????&& board[win[i][1]] == c ????????????????????&& board[win[i][2]] == c) { ????????????????return true; ????????????} ????????} ????????return false; ????} // Returns true if given board is valid, else returns false? ????static boolean isValid(char board[]) { ????????// Count number of 'X' and 'O' in the given board? ????????int xCount = 0, oCount = 0; ????????for (int i = 0; i < 9; i++) { ????????????if (board[i] == 'X') { ????????????????xCount++; ????????????} ????????????if (board[i] == 'O') { ????????????????oCount++; ????????????} ????????} ????????// Board can be valid only if either xCount and oCount? ????????// is same or xount is one more than oCount? ????????if (xCount == oCount || xCount == oCount + 1) { ????????????// Check if 'O' is winner? ????????????if (isCWin(board, 'O')) { ????????????????// Check if 'X' is also winner, then? ????????????????// return false? ????????????????if (isCWin(board, 'X')) { ????????????????????return false; ????????????????} ????????????????// Else return true xCount and yCount are same? ????????????????return (xCount == oCount); ????????????} ????????????// If 'X' wins, then count of X must be greater? ????????????if (isCWin(board, 'X') && xCount != oCount + 1) { ????????????????return false; ????????????} ????????????// If 'O' is not winner, then return true? ????????????return true; ????????} ????????return false; ????} // Driver program? ????public static void main(String[] args) { ????????char board[] = {'X', 'X', 'O', 'O', 'O', 'X', 'X', 'O', 'X'}; ????????if ((isValid(board))) { ????????????System.out.println("Given board is valid"); ????????} else { ????????????System.out.println("Given board is not valid"); ????????} ????} } //this code contributed by PrinciRaj1992 ``` ## Python3 ```py # Python3 program to check whether a given tic tac toe # board is valid or not # Returns true if char wins. Char can be either # 'X' or 'O' def win_check(arr, char): ????# Check all possible winning combinations ????matches = [[0, 1, 2], [3, 4, 5], ???????????????[6, 7, 8], [0, 3, 6], ???????????????[1, 4, 7], [2, 5, 8], ???????????????[0, 4, 8], [2, 4, 6]] ????for i in range(8): ????????if(arr[matches[i][0]] == char and ????????????arr[matches[i][1]] == char and ????????????arr[matches[i][2]] == char): ????????????return True ????return False def is_valid(arr): ????# Count number of 'X' and 'O' in the given board ????xcount = arr.count('X') ????ocount = arr.count('O') ????# Board can be valid only if either xcount and ocount ????# is same or xount is one more than oCount ????if(xcount == ocount+1 or xcount == ocount): ????????# Check if O wins ????????if win_check(arr, 'O'): ????????????# Check if X wins, At a given point only one can win,? ????????????# if X also wins then return Invalid ????????????if win_check(arr, 'X'): ????????????????return "Invalid" ????????????# O can only win if xcount == ocount in case where whole ????????????# board has values in each position. ????????????if xcount == ocount: ????????????????return "Valid" ????????# If X wins then it should be xc == oc + 1,? ????????# If not return Invalid????? ????????if win_check(arr, 'X') and xcount != ocount+1: ????????????return "Invalid" ????????# if O is not the winner return Valid? ????????if not win_check(arr, 'O'): ????????????return "Valid" ????# If nothing above matches return invalid ????return "Invalid" # Driver Code arr = ['X', 'X', 'O', ???????'O', 'O', 'X',? ???????'X', 'O', 'X'] print("Given board is " + is_valid(arr)) ``` ## C# ```cs // C# program to check whether a given? // tic tac toe board is valid or not? using System; class GFG { // This matrix is used to find indexes // to check all possible wining triplets // in board[0..8]? public static int[][] win = new int[][] { ????new int[] {0, 1, 2}, ????new int[] {3, 4, 5}, ????new int[] {6, 7, 8}, ????new int[] {0, 3, 6}, ????new int[] {1, 4, 7}, ????new int[] {2, 5, 8}, ????new int[] {0, 4, 8}, ????new int[] {2, 4, 6} }; // Returns true if character 'c'? // wins. c can be either 'X' or 'O'? public static bool isCWin(char[] board,? ??????????????????????????char c) { ????// Check all possible winning ????// combinations? ????for (int i = 0; i < 8; i++) ????{ ????????if (board[win[i][0]] == c &&? ????????????board[win[i][1]] == c &&? ????????????board[win[i][2]] == c) ????????{ ????????????return true; ????????} ????} ????return false; } // Returns true if given board? // is valid, else returns false? public static bool isValid(char[] board) { ????// Count number of 'X' and? ????// 'O' in the given board? ????int xCount = 0, oCount = 0; ????for (int i = 0; i < 9; i++) ????{ ????????if (board[i] == 'X') ????????{ ????????????xCount++; ????????} ????????if (board[i] == 'O') ????????{ ????????????oCount++; ????????} ????} ????// Board can be valid only if either? ????// xCount and oCount is same or xount ????// is one more than oCount? ????if (xCount == oCount || ????????xCount == oCount + 1) ????{ ????????// Check if 'O' is winner? ????????if (isCWin(board, 'O')) ????????{ ????????????// Check if 'X' is also winner,? ????????????// then return false? ????????????if (isCWin(board, 'X')) ????????????{ ????????????????return false; ????????????} ????????????// Else return true xCount? ????????????// and yCount are same? ????????????return (xCount == oCount); ????????} ????????// If 'X' wins, then count of? ????????// X must be greater? ????????if (isCWin(board, 'X') &&? ????????????xCount != oCount + 1) ????????{ ????????????return false; ????????} ????????// If 'O' is not winner,? ????????// then return true? ????????return true; ????} ????return false; } // Driver Code? public static void Main(string[] args) { ????char[] board = new char[] {'X', 'X', 'O', 'O', 'O', ????????????????????????????????????'X', 'X', 'O', 'X'}; ????if ((isValid(board))) ????{ ????????Console.WriteLine("Given board is valid"); ????} ????else ????{ ????????Console.WriteLine("Given board is not valid"); ????} } } // This code is contributed by Shrikant13 ``` ## PHP ```php <?php // PHP program to check whether a given? // tic tac toe board is valid or not // This matrix is used to find indexes? // to check all possible wining triplets // in board[0..8] // Returns true if character 'c' wins.? // c can be either 'X' or 'O' function isCWin($board, $c) { ????$win = array(array(0, 1, 2), // Check first row. ?????????????????array(3, 4, 5), // Check second Row ?????????????????array(6, 7, 8), // Check third Row ?????????????????array(0, 3, 6), // Check first column ?????????????????array(1, 4, 7), // Check second Column ?????????????????array(2, 5, 8), // Check third Column ?????????????????array(0, 4, 8), // Check first Diagonal ?????????????????array(2, 4, 6)); // Check second Diagonal ????// Check all possible winning combinations ????for ($i = 0; $i < 8; $i++) ????????if ($board[$win[$i][0]] == $c && ????????????$board[$win[$i][1]] == $c && ????????????$board[$win[$i][2]] == $c ) ????????????return true; ????return false; } // Returns true if given board is // valid, else returns false function isValid(&$board) { ????// Count number of 'X' and 'O' ????// in the given board ????$xCount = 0; ????$oCount = 0; ????for ($i = 0; $i < 9; $i++) ????{ ????????if ($board[$i] == 'X') $xCount++; ????????if ($board[$i] == 'O') $oCount++; ????} ????// Board can be valid only if either? ????// xCount and oCount is same or xount? ????// is one more than oCount ????if ($xCount == $oCount || $xCount == $oCount + 1) ????{ ????????// Check if 'O' is winner ????????if (isCWin($board, 'O')) ????????{ ????????????// Check if 'X' is also winner,? ????????????// then return false ????????????if (isCWin($board, 'X')) ????????????????return false; ????????????// Else return true xCount and ????????????// yCount are same ????????????return ($xCount == $oCount); ????????} ????????// If 'X' wins, then count of X? ????????// must be greater ????????if (isCWin($board, 'X') && ???????????????????$xCount != $oCount + 1) ????????return false;? ????????// If 'O' is not winner, then? ????????// return true ????????return true; ????} ????return false; } // Driver Code $board = array('X', 'X', 'O','O',? ???????????????'O', 'X','X', 'O', 'X'); if(isValid($board)) ????echo("Given board is valid"); else ????echo ("Given board is not valid"); // This code is contributed? // by Shivi_Aggarwal ?> ``` **輸出**： ``` Given board is valid ``` 感謝 Utkarsh 提出此解決方案。