Validez de una determinada configuración de tablero Tic-Tac-Toe

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.

tictactoe

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *