grid47 Exploring patterns and algorithms
Aug 19, 2024
9 min read
Solution to LeetCode 794: Valid Tic-Tac-Toe State Problem
Given a Tic-Tac-Toe board represented as a 3x3 string array, return true if and only if this board could have been reached during a valid Tic-Tac-Toe game. In a valid game, players alternate placing ‘X’ and ‘O’ characters into empty spaces. ‘X’ always goes first, and no player can move after the game has ended.
Problem
Approach
Steps
Complexity
Input: The input is a 3x3 Tic-Tac-Toe board represented as a string array where each element in the array is a string of length 3.
Example: board = ['XOX', ' O ', ' ']
Constraints:
• board.length == 3
• board[i].length == 3
• board[i][j] is either 'X', 'O', or ' ' (empty space).
Output: Return a boolean value indicating whether the given board configuration could be reached during a valid game.
Example: Output: true
Constraints:
• The output should be either true or false.
Goal: The goal is to determine if the given Tic-Tac-Toe board is a valid position during a game, respecting the rules of turn order and winning conditions.
Steps:
• Count the number of 'X' and 'O' characters on the board.
• Check if a player has won. A player wins if they have three of their symbols in a row, column, or diagonal.
• Ensure that the number of 'X's is either equal to or one more than the number of 'O's.
• If a player has won, check that the game is consistent with turn order (i.e., 'X' should not have won before 'O' had a chance to play).
Goal: Ensure that the board adheres to the rules of Tic-Tac-Toe, considering the turn order and winning conditions.
Steps:
• The board must be a 3x3 grid.
• The characters on the board are restricted to 'X', 'O', or ' '.
• The number of 'X' can only be equal to or one more than the number of 'O'.
Assumptions:
• The board is a 3x3 grid.
• Players alternate placing 'X' and 'O' with 'X' going first.
• No more moves can be made after the game has ended.
• Input: Input: board = ['XOX', ' O ', ' ']
• Explanation: This board configuration is invalid because 'O' should not have played after 'X' placed their 'X'. 'X' should always play first.
• Input: Input: board = ['XOX', ' X ', ' ']
• Explanation: This board configuration is valid because the count of 'X' is one more than the count of 'O', and no one has won yet.
• Input: Input: board = ['XOX', 'O O', 'XOX']
• Explanation: This board configuration is valid because the game ended with no inconsistencies between turn order and the game status.
Approach: To solve this problem, we need to simulate the sequence of moves and verify the rules governing the game, including turn order and the winning condition.
Observations:
• We need to check both the count of 'X' and 'O' characters and ensure that a player can only win if it's their turn.
• It's important to ensure that the board configuration is consistent with the rules of the game before determining if it's valid.
Steps:
• Count the number of 'X' and 'O' on the board.
• Check for any winner (three 'X' or 'O' in a row, column, or diagonal).
• Ensure that the number of 'X' is equal to or one more than the number of 'O'.
• If a winner exists, ensure that the winner's turn count is consistent with the game rules (i.e., 'X' wins only if it has one more move than 'O').
Empty Inputs:
• An empty board should not be considered a valid configuration.
Large Inputs:
• Since the board is always a 3x3 grid, no consideration for large inputs is needed.
Special Values:
• Check if the board configuration includes a winning state and that no further moves are possible after that.
Constraints:
• Ensure the input follows the constraint that the board is a 3x3 grid.
This line defines the function 'validTicTacToe', which takes a 3x3 board as input and returns a boolean indicating whether the board configuration is valid.
2 : Variable Initialization
bool xwin =false, owin =false;
This line initializes two boolean variables, 'xwin' and 'owin', which will track whether player X or player O has won the game.
3 : Variable Initialization
vector<int> rows(3, 0), cols(3, 0);
This initializes two vectors of size 3, 'rows' and 'cols', both set to 0. These vectors will track the sum of marks (X or O) in each row and column.
4 : Variable Initialization
int diag =0, antidiag =0, turns =0;
This initializes three variables: 'diag' for tracking the diagonal sum, 'antidiag' for the anti-diagonal sum, and 'turns' for counting the number of turns taken.
5 : Looping through Board
for(int i =0; i <3; i++)
This outer loop iterates over the rows of the board.
6 : Looping through Board
for(int j =0; j <3; j++) {
This inner loop iterates over the columns of the board.
7 : Condition Check (X)
if(board[i][j] =='X') {
This checks if the current cell contains the 'X' symbol.
8 : Update Counters (X)
turns++, cols[j]++, rows[i]++;
This increments the turn count and updates the row and column counters for player X.
9 : Update Counters (Diagonal)
if(i == j) diag++;
This checks if the current cell is on the main diagonal (i == j) and increments the 'diag' counter if true.
10 : Update Counters (Anti-Diagonal)
if(i + j ==2) antidiag++;
This checks if the current cell is on the anti-diagonal (i + j == 2) and increments the 'antidiag' counter if true.
11 : Condition Check (O)
} elseif(board[i][j] =='O') {
This checks if the current cell contains the 'O' symbol.
12 : Update Counters (O)
turns--, cols[j]--, rows[i]--;
This decrements the turn count and updates the row and column counters for player O.
13 : Update Counters (Diagonal)
if(i == j) diag--;
This checks if the current cell is on the main diagonal (i == j) and decrements the 'diag' counter if true.
14 : Update Counters (Anti-Diagonal)
if(i + j ==2) antidiag--;
This checks if the current cell is on the anti-diagonal (i + j == 2) and decrements the 'antidiag' counter if true.
15 : Check for X Win
xwin = rows[0] ==3|| cols[0] ==3||
This checks if player X has won by checking if any row, column, or diagonal has a sum of 3.
16 : Check for X Win
rows[1] ==3|| cols[1] ==3||
Continues checking for player X's win.
17 : Check for X Win
rows[2] ==3|| cols[2] ==3||
Continues checking for player X's win.
18 : Check for X Win
diag ==3|| antidiag ==3;
Final check for player X's win.
19 : Check for O Win
owin = rows[0] ==-3|| cols[0] ==-3||
This checks if player O has won by checking if any row, column, or diagonal has a sum of -3.
20 : Check for O Win
rows[1] ==-3|| cols[1] ==-3||
Continues checking for player O's win.
21 : Check for O Win
rows[2] ==-3|| cols[2] ==-3||
Continues checking for player O's win.
22 : Check for O Win
diag ==-3|| antidiag ==-3;
Final check for player O's win.
23 : Return Invalid Game Configuration
if(xwin && turns ==0|| owin && turns ==1)
This checks if there is an invalid game configuration, where both players win or the number of turns is incorrect.
24 : Return Validity
returnfalse;
If the game configuration is invalid, return false.
