Se da un tablero de Tic-Tac-Toe después de que se juegan algunos movimientos. Averigüe si el tablero dado es válido, es decir, si es posible llegar a esta posición del tablero después de algunos movimientos o no.
Tenga en cuenta que cada cuadrícula llena arbitrariamente de 9 espacios no es válida, por ejemplo, una cuadrícula llena con 3 X y 6 O no es una situación válida porque cada jugador necesita tomar turnos alternos.
C++
// 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 winning 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 count 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 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 winning 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 count 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
# 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 count 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#
// 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 winning 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 count
// 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 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 winning 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 count
// 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
?>
Javascript
<script>
// Javascript 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 winning triplets
// in board[0..8]
// Returns true if character 'c' wins.
// c can be either 'X' or 'O'
function isCWin(board, c)
{
let win = new Array(new Array(0, 1, 2), // Check first row.
new Array(3, 4, 5), // Check second Row
new Array(6, 7, 8), // Check third Row
new Array(0, 3, 6), // Check first column
new Array(1, 4, 7), // Check second Column
new Array(2, 5, 8), // Check third Column
new Array(0, 4, 8), // Check first Diagonal
new Array(2, 4, 6)); // Check second Diagonal
// Check all possible winning combinations
for (let 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
let xCount = 0;
let oCount = 0;
for (let 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 count
// 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
let board = new Array('X', 'X', 'O','O',
'O', 'X','X', 'O', 'X');
if(isValid(board))
document.write("Given board is valid");
else
document.write("Given board is not valid");
// This code is contributed
// by Saurabh Jaiswal
</script>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA