Valid Tic-Tac-Toe State Solution In C++/Python/java/JS
Problem Description
In this problem, you are given a 3x3 Tic-Tac-Toe board represented as a string array. The goal is to determine if the given board configuration could have been reached through a sequence of valid moves according to the rules of Tic-Tac-Toe. The game follows a turn-based approach where the first player always places 'X', followed by the second player placing 'O'. Moves are made on empty squares, and once a player wins or the board is full, no further moves can be made.
Example
Input 1: board = ["O ", " ", " "]
Output: false
Explanation:
The input board is ["O ", " ", " "]\. Here, the board shows that 'O' has been placed before 'X', which violates the rule that 'X' always goes first. Hence, the output is false.
Input 2: board = ["XOX", "O O", "XOX"]
Output: true
Explanation:
The input board is ["XOX", "O O", "XOX"]. This configuration follows all the rules—players took turns correctly, and the board represents a valid end-state of a Tic-Tac-Toe game. The output is true.
Constraints
- board.length == 9
- board[i].length == 9
- board[i][j] is a digit 1-9 or '.'.
First, count the occurrences of 'X' and 'O'. Since 'X' always plays first, its count should be equal to or exactly one more than 'O'. If 'O' has more moves than 'X', the board state is invalid. Next, check if any player has won by identifying three consecutive 'X' or 'O' in a row, column, or diagonal. If 'X' has won, then 'O' should not have the same count as 'X' because 'X' should have played last. Similarly, if 'O' has won, 'X' should not have more moves, as 'O' must have played last. Additionally, if both 'X' and 'O' have winning conditions at the same time, the board is invalid. Finally, ensure that no moves have been made after a winning condition has already been reached, as no further moves should be possible once the game ends.
Brute Force Approach
Intuition
Tic-Tac-Toe is a turn-based game where players alternately place 'X' and 'O' on a 3x3 board. The challenge is to determine if a given board state could have been reached through a valid sequence of moves. A valid board must follow the rules: 'X' always plays first, players take turns, and the game ends when a player wins or the board is full. If 'X' has played more than one extra move over 'O', or if 'O' has played the same number or more moves than 'X', the board is invalid. Another crucial aspect is checking the winning conditions—if a player has already won, no further moves should have been made. Additionally, both 'X' and 'O' cannot win at the same time since the game stops as soon as a winner is determined. The problem requires verifying all these conditions, making a brute force approach suitable by iterating over the board and checking every possible violation.
Approach
To determine whether the given Tic-Tac-Toe board is valid, we first count the occurrences of 'X' and 'O'. Since 'X' always plays first, the count of 'X' should either be equal to or exactly one more than the count of 'O'. If 'O' has played the same number of times as 'X' or more, the board is immediately invalid because it means 'O' played first or took extra turns.
Next, we check for a winning condition by examining all possible ways a player can win—three in a row, three in a column, or three diagonally. If 'X' has a winning combination, then 'O' should not have the same count as 'X' since 'X' must have played last. Similarly, if 'O' has a winning combination, 'X' must not have more moves than 'O', as 'O' must have played last. If both 'X' and 'O' have winning positions simultaneously, the board is invalid because a game stops immediately when a player wins.
Finally, we ensure that no extra moves were made after a winning condition was met. If a player has already won, no further moves should have been placed, as the game ends as soon as a winner is determined. If all these conditions are satisfied, the board state is valid; otherwise, it is invalid.
Dry Run
Input:
board = ["XOX", "O O", "XOX"]
Output: true
The board represents a completed Tic-Tac-Toe game. We need to check if this board state follows all game rules, including turn order, valid moves, and winning conditions. If any rule is violated, the board is invalid; otherwise, it is valid.
Step 1: Count 'X' and 'O' Moves
First, we count the occurrences of 'X' and 'O' on the board. The total count of 'X' is 5, and the total count of 'O' is 4. Since 'X' always plays first, the count of 'X' should be equal to or exactly one more than 'O'. Here, 'X' has played one extra move, which is valid. If 'O' had the same or more moves than 'X', the board would be invalid.
Step 2: Check for a Winning Condition
Next, we check if either 'X' or 'O' has won by forming three of the same symbol in a row, column, or diagonal. Looking at the board, we see that 'O' has won in the second column (O O O). Now, we verify whether the game state remains valid. Since 'O' has won, it must have played the last move. The count of 'X' (5) is only one more than 'O' (4), which means 'O' could have completed its turn before the game ended. Also, no additional moves were made after 'O' won, which is a necessary condition for validity.
Final Output: true
All conditions for a valid Tic-Tac-Toe game have been satisfied. The turn order is correct, 'O' won in a valid way, and no extra moves were made after the game ended. Since no rules were broken, the given board state is a possible outcome of a real game, making it valid.
Code for All Languages
C++
// Valid Tic-Tac-Toe State - Brute Force Approach CPP
// Function to check if a player has won
bool checkWin(vector<string>& board, char player) {
// Check rows and columns
for (int i = 0; i < 3; i++) {
if (board[i][0] == player && board[i][1] == player && board[i][2] == player) return true; // Row win
if (board[0][i] == player && board[1][i] == player && board[2][i] == player) return true; // Column win
}
// Check diagonals
if (board[0][0] == player && board[1][1] == player && board[2][2] == player) return true; // Main diagonal win
if (board[0][2] == player && board[1][1] == player && board[2][0] == player) return true; // Anti-diagonal win
return false;
}
// Function to check if the board state is valid
bool isValidTicTacToe(vector<string>& board) {
int xCount = 0, oCount = 0;
// Count 'X' and 'O' occurrences
for (const string& row : board) {
for (char cell : row) {
if (cell == 'X') xCount++;
else if (cell == 'O') oCount++;
}
}
// 'X' should be equal to or one more than 'O'
if (oCount > xCount || xCount > oCount + 1) return false;
// Check if a player has won
bool xWin = checkWin(board, 'X');
bool oWin = checkWin(board, 'O');
// Both 'X' and 'O' cannot win at the same time
if (xWin && oWin) return false;
// If 'X' wins, then 'X' should have one more move than 'O'
if (xWin && xCount != oCount + 1) return false;
// If 'O' wins, then 'X' and 'O' should have the same count
if (oWin && xCount != oCount) return false;
return true;
}Java
// Valid Tic-Tac-Toe State - Brute Force Approach Java
// Generate all possible valid Tic-Tac-Toe game states
public static void generateBoards(char[][] board, int turn, int xCount, int oCount) {
// Convert board to string representation
String boardStr = boardToString(board);
// Stop recursion if board already visited
if (validBoards.contains(boardStr)) return;
// Store this board state as valid
validBoards.add(boardStr);
// Check if the game has ended (win or full board)
if (checkWin(board, 'X') || checkWin(board, 'O') || (xCount + oCount == 9)) return;
// Try placing the next valid move
char nextMove = (turn % 2 == 0) ? 'X' : 'O'; // 'X' moves on even turns, 'O' on odd
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (board[i][j] == ' ') { // Empty spot
board[i][j] = nextMove;
generateBoards(board, turn + 1, xCount + (nextMove == 'X' ? 1 : 0), oCount + (nextMove == 'O' ? 1 : 0));
board[i][j] = ' '; // Backtrack
}
}
}
}
// Convert 2D board to string format for comparison
private static String boardToString(char[][] board) {
StringBuilder sb = new StringBuilder();
for (char[] row : board) {
sb.append(new String(row));
}
return sb.toString();
}
// Function to check if a player has won
private static boolean checkWin(char[][] board, char player) {
for (int i = 0; i < 3; i++) {
if (board[i][0] == player && board[i][1] == player && board[i][2] == player) return true; // Row
if (board[0][i] == player && board[1][i] == player && board[2][i] == player) return true; // Column
}
if (board[0][0] == player && board[1][1] == player && board[2][2] == player) return true; // Main diagonal
if (board[0][2] == player && board[1][1] == player && board[2][0] == player) return true; // Anti-diagonal
return false;
}
// Function to check if the given board is valid
public static boolean isValidTicTacToe(String[] board) {
// Generate all possible valid Tic-Tac-Toe game states
char[][] emptyBoard = {
{' ', ' ', ' '},
{' ', ' ', ' '},
{' ', ' ', ' '}
};
generateBoards(emptyBoard, 0, 0, 0);
// Convert input board to string and check if it's in valid states
return validBoards.contains(String.join("", board));
}
Python
# Valid Tic-Tac-Toe State - Brute Force Approach Python
def generate_boards(board, turn, x_count, o_count, valid_boards):
# Convert board to string format
board_str = ''.join([''.join(row) for row in board])
# Stop if this board is already in the set
if board_str in valid_boards:
return
# Store the board as a valid state
valid_boards.add(board_str)
# Stop if the game has ended (win or full board)
if check_win(board, 'X') or check_win(board, 'O') or (x_count + o_count == 9):
return
# Determine the next move
next_move = 'X' if turn % 2 == 0 else 'O'
# Try placing the next valid move in all empty positions
for i in range(3):
for j in range(3):
if board[i][j] == ' ':
board[i][j] = next_move
generate_boards(board, turn + 1, x_count + (next_move == 'X'), o_count + (next_move == 'O'), valid_boards)
board[i][j] = ' ' # Backtrack
# Function to check if a player has won
def check_win(board, player):
for i in range(3):
if all(board[i][j] == player for j in range(3)): # Row check
return True
if all(board[j][i] == player for j in range(3)): # Column check
return True
if all(board[i][i] == player for i in range(3)): # Main diagonal
return True
if all(board[i][2 - i] == player for i in range(3)): # Anti-diagonal
return True
return False
# Function to check if the input board is valid
def is_valid_tic_tac_toe(board):
JavaScript
// Valid Tic-Tac-Toe State - Brute Force Approach JavaScript
// Function to check if a player has won
function checkWin(board, player) {
for (let i = 0; i < 3; i++) {
if (board[i][0] === player && board[i][1] === player && board[i][2] === player) return true; // Row check
if (board[0][i] === player && board[1][i] === player && board[2][i] === player) return true; // Column check
}
if (board[0][0] === player && board[1][1] === player && board[2][2] === player) return true; // Main diagonal
if (board[0][2] === player && board[1][1] === player && board[2][0] === player) return true; // Anti-diagonal
return false;
}
// Function to generate all valid Tic-Tac-Toe board states
function generateBoards(board, turn, xCount, oCount, validBoards) {
let boardStr = board.map(row => row.join("")).join("");
// If this board has already been generated, return
if (validBoards.has(boardStr)) return;
// Store the board in the set
validBoards.add(boardStr);
// Stop if the game has ended
if (checkWin(board, 'X') || checkWin(board, 'O') || (xCount + oCount === 9)) return;
// Determine the next move
let nextMove = (turn % 2 === 0) ? 'X' : 'O';
// Try placing the next valid move in all empty positions
for (let i = 0; i < 3; i++) {
for (let j = 0; j < 3; j++) {
if (board[i][j] === ' ') {
board[i][j] = nextMove;
generateBoards(board, turn + 1, xCount + (nextMove === 'X' ? 1 : 0), oCount + (nextMove === 'O' ? 1 : 0), validBoards);
board[i][j] = ' '; // Backtrack
}
}
}
}
// Function to check if the given Tic-Tac-Toe board is valid
function isValidTicTacToe(board) {
let validBoards = new Set();
// Create an empty board
let emptyBoard = Array.from({ length: 3 }, () => Array(3).fill(' '));
// Generate all valid Tic-Tac-Toe board states
generateBoards(emptyBoard, 0, 0, 0, validBoards);
// Convert input board into a string format and check in validBoards
return validBoards.has(board.map(row => row.join("")).join(""));
}Time Complexity - Valid Tic-Tac-Toe State - O(N!)
The time complexity of the brute force approach is O(9!), as it involves generating all possible valid Tic-Tac-Toe board states by simulating every possible move from an empty board. Since there are 9 cells and moves alternate between 'X' and 'O', the number of possible board configurations follows a factorial growth pattern, leading to 9! = 362,880 possible game sequences in the worst case. Each move creates a new state, and the game can end when a player wins or when all cells are filled. Although checking if a given board is valid is O(1) using a precomputed set of valid states, the process of generating and storing all valid states makes the approach computationally expensive.
Space Complexity - Valid Tic-Tac-Toe State - O(N!)
The space complexity is also O(9!), as it requires storing every valid Tic-Tac-Toe board state in memory. Since every possible game configuration needs to be saved, the memory usage grows factorially with the number of moves. Additionally, the recursive depth of the function is at most 9, contributing an extra O(1) space usage for the recursive call stack. While this approach ensures correctness, it is inefficient in both time and space compared to more optimized solutions that validate board configurations in constant time without precomputing all possible states.
Bridge between Brute Force and Optimized
A bridge between the brute force and optimized approach involves reducing unnecessary computations while still following a structured validation process. Instead of generating all possible Tic-Tac-Toe states, we can directly check a given board’s validity using logical constraints derived from the game’s rules.
First, we count the occurrences of 'X' and 'O' to ensure 'X' is either equal to or exactly one more than 'O'. Then, we check if any player has already won. If 'X' has won, 'O' should not have the same count as 'X', and if 'O' has won, 'X' should not have played more moves after that. This eliminates the need to precompute all valid board states, significantly reducing the factorial time complexity to O(1) by using a few simple checks. The space complexity is also reduced to O(1) as we no longer need to store all valid states.
This approach serves as a transition between brute force and fully optimized solutions, maintaining correctness while improving efficiency.
Optimized Approach
Intuition
The optimized approach leverages the fundamental rules of Tic-Tac-Toe to validate a board state efficiently, eliminating the need to generate all possible game sequences. Instead of precomputing valid states, we analyze the given board directly by checking key conditions: the count of 'X' and 'O', the winning conditions, and the order in which moves must have occurred. This allows us to determine whether the board state is possible in constant time, making the approach highly efficient.
In a valid Tic-Tac-Toe game, players alternate turns, meaning the number of 'X' marks must be equal to or exactly one more than the number of 'O' marks. Additionally, the game cannot continue after a player has already won. If either 'X' or 'O' has a winning combination (three in a row, column, or diagonal), the board must reflect a state where no further moves were made. For example, if 'O' wins, 'X' should not have an extra move. By enforcing these constraints, we can determine whether a given board could have been reached through legal gameplay without simulating all possible moves.
Approach
First, we start by counting the number of 'X' and 'O' occurrences on the board. Since players take turns, 'X' should always be either equal to or exactly one more than 'O'. If 'O' appears more times than 'X' or if 'X' is ahead by more than one move, the board is immediately considered invalid. This ensures that the turn order was followed correctly throughout the game.
Next, we check whether any player has won by looking for three identical symbols in any row, column, or diagonal. If a player has formed a winning combination, the board must reflect a state where no more moves were made after that win. This means that if both 'X' and 'O' have winning sequences simultaneously, the board is invalid because a player must have won before the other could complete a line.
If 'X' has won, then 'O' should have one less move, as 'X' must have made the final winning move. If 'O' has won, then 'X' should not have an extra move, as the game should have ended on 'O’s' winning turn. Any deviation from these conditions indicates an impossible game state, rendering the board invalid.
Finally, if none of these violations are found, the board is considered valid. This approach works in O(1) time and requires O(1) space since we are only performing a few predefined checks on a fixed 3x3 board without storing additional data. By enforcing these simple yet effective constraints, we eliminate unnecessary computations while ensuring correctness.
Dry Run
Input:
board = ["XOX",
"O O",
"XOX"]
Output: true
True (The board represents a valid Tic-Tac-Toe state that could have been reached through legal gameplay.)
Steps:
Step 1 begins with counting the occurrences of 'X' and 'O' on the board. By iterating through the board, we determine that 'X' appears five times, while 'O' appears four times. Since the rules dictate that 'X' should either be equal to or exactly one more than 'O', this condition is satisfied, and we can proceed to the next step.
Step 2 focuses on checking if any player has won by forming three identical symbols in a row, column, or diagonal. We start by scanning the rows. The first row consists of 'XOX', which does not form a winning sequence. The second row contains 'O O', which is incomplete and does not satisfy the win condition. The third row also has 'XOX', which does not result in a win. Moving on to the columns, we analyze each one. The first column contains 'XOX', the second column has 'O O', and the third column holds 'XOX', none of which create a winning sequence. Next, we examine the diagonals. The main diagonal consists of 'X O', which is incomplete, and the anti-diagonal contains 'X O', which is also not a winning pattern. Since no winning conditions are met, we move to the final validation step.
Step 3 ensures that the board's state remains consistent with the game's rules. Since no winner has been found, the only requirement left is to verify the turn-based structure of the game. Given that we previously checked and confirmed that 'X' appears exactly one more time than 'O', no further validation is required. With all conditions satisfied, the board is determined to be a valid Tic-Tac-Toe state.
Final Output: true
The board meets all the conditions of a valid Tic-Tac-Toe state. Since the number of moves is correct and no invalid winning condition exists, we return True as the final result.
Cpp
// Valid Tic-Tac-Toe State - Optimised Approach CPP
// Function to check the validity of a tic-tac-toe game board state
bool validTicTacToe(vector<string>& board) {
// Lambda to count occurrences of a provided character ('X' or 'O') on the board
auto countCharacter = [&](char character) {
int count = 0;
for (const auto& row : board) { // Iterate through each row of the board
for (char cell : row) { // Iterate through each cell in the row
count += cell == character; // Increment count if the cell matches the character
}
}
return count;
};
// Lambda to check if a given player has won the game
auto checkWin = [&](char player) {
// Check rows and columns for a win condition
for (int i = 0; i < 3; ++i) {
if (board[i][0] == player && board[i][1] == player && board[i][2] == player) return true;
if (board[0][i] == player && board[1][i] == player && board[2][i] == player) return true;
}
// Check both diagonals for a win condition
if (board[0][0] == player && board[1][1] == player && board[2][2] == player) return true;
return board[0][2] == player && board[1][1] == player && board[2][0] == player;
};
// Count the number of 'X' and 'O' on the board
int countX = countCharacter('X');
int countO = countCharacter('O');
// Check the game's rules:
// Rule 1: The number of 'X's must either be equal to or one more than the number of 'O's
if (countX != countO && countX - 1 != countO) return false;
// Rule 2: If 'X' has won, there must be one more 'X' than 'O'
if (checkWin('X') && countX - 1 != countO) return false;
// Rule 3: If 'O' has won, the number of 'X's and 'O's must be equal
if (checkWin('O') && countX != countO) return false;
// If all rules are satisfied, the board state is valid
return true;
}Java
// Valid Tic-Tac-Toe State - Optimised Approach Java
private String[] board;
// Checks if the given Tic-Tac-Toe board state is valid
public boolean validTicTacToe(String[] board) {
this.board = board;
int countX = count('X'), countO = count('O');
// 'X' goes first, so countX must be equal to or one more than countO
if (countX != countO && countX - 1 != countO) {
return false;
}
// If 'X' has won, it must have exactly one more move than 'O'
if (hasWon('X') && countX - 1 != countO) {
return false;
}
// If 'O' has won, there must be an equal number of 'X' and 'O'
return !(hasWon('O') && countX != countO);
}
// Checks if the given player has won
private boolean hasWon(char player) {
// Check all rows and columns
for (int i = 0; i < 3; ++i) {
if (board[i].charAt(0) == player && board[i].charAt(1) == player && board[i].charAt(2) == player) {
return true; // Row win
}
if (board[0].charAt(i) == player && board[1].charAt(i) == player && board[2].charAt(i) == player) {
return true; // Column win
}
}
// Check both diagonals
if (board[0].charAt(0) == player && board[1].charAt(1) == player && board[2].charAt(2) == player) {
return true; // Main diagonal win
}
return board[0].charAt(2) == player && board[1].charAt(1) == player && board[2].charAt(0) == player; // Anti-diagonal win
}
// Counts the number of times the given character appears on the board
private int count(char character) {
int count = 0;
for (String row : board) {
for (char cell : row.toCharArray()) {
if (cell == character) {
++count;
}
}
}
return count;
}Python
# Valid Tic-Tac-Toe State - Optimised Approach Python
def validTicTacToe(self, board: List[str]) -> bool:
# Function to check if player with mark 'X' or 'O' has won
def has_winner(mark):
# Check for horizontal and vertical wins
for i in range(3):
if all(board[i][j] == mark for j in range(3)): # Row win
return True
if all(board[j][i] == mark for j in range(3)): # Column win
return True
# Check for diagonal wins
if all(board[i][i] == mark for i in range(3)): # Main diagonal
return True
return all(board[i][2 - i] == mark for i in range(3)) # Anti-diagonal
# Count occurrences of 'X' and 'O'
count_x = sum(row.count('X') for row in board)
count_o = sum(row.count('O') for row in board)
# Check for the correct number of 'X's and 'O's
if count_x != count_o and count_x - 1 != count_o:
return False
# If 'X' has won, it must have exactly one more move than 'O'
if has_winner('X') and count_x - 1 != count_o:
return False
# If 'O' has won, there must be an equal number of 'X' and 'O'
if has_winner('O') and count_x != count_o:
return False
return True
JavaScript
// Valid Tic-Tac-Toe State - Optimised Approach JavaScript
const validTicTacToe = (board) => {
// Helper function to count occurrences of 'X' or 'O' on the board.
const countOccurrences = (char) => {
return board.reduce((accumulator, currentRow) => {
return accumulator + [...currentRow].filter(c => c === char).length;
}, 0);
};
// Helper function to check if a player has won the game.
const hasWon = (char) => {
// Check rows and columns for win
for (let i = 0; i < 3; ++i) {
if (board[i][0] === char && board[i][1] === char && board[i][2] === char) {
return true;
}
if (board[0][i] === char && board[1][i] === char && board[2][i] === char) {
return true;
}
}
// Check diagonals for win
if (board[0][0] === char && board[1][1] === char && board[2][2] === char) {
return true;
}
return board[0][2] === char && board[1][1] === char && board[2][0] === char;
};
// Count occurrences of 'X' and 'O'.
const xCount = countOccurrences('X');
const oCount = countOccurrences('O');
// Ensure 'X' goes first and there's at most one more 'X' than 'O'
if (xCount !== oCount && xCount - 1 !== oCount) {
return false;
}
// Check for a win by 'X'. If 'X' has won, there must be one more 'X' than 'O'.
if (hasWon('X') && xCount - 1 !== oCount) {
return false;
}
// Check for a win by 'O'. If 'O' has won, there must be an equal number of 'X' and 'O'.
if (hasWon('O') && xCount !== oCount) {
return false;
}
// If none of the invalid conditions were met, the board is valid.
return true;
};
Time Complexity - Valid Tic-Tac-Toe State - O (1)
The function validTicTacToe primarily performs three key operations: counting occurrences of characters, checking for winning conditions, and validating the board state. The counting function iterates through all the cells in a 3×3 tic-tac-toe board, meaning it processes at most 9 elements, making it a constant time operation O(1). The function that checks for a winner goes through 3 rows, 3 columns, and 2 diagonals, making a total of 8 checks in every execution. Since each check involves comparing a fixed number of elements, this operation also runs in O(1) time. Finally, the validity checks in validTicTacToe involve a few conditional statements and function calls that all operate in constant time. Since every operation in the solution executes in a constant number of steps irrespective of the input, the overall time complexity is O(1), meaning the function runs in a fixed amount of time for any given tic-tac-toe board.
Space Complexity - Valid Tic-Tac-Toe State - O (1)
The function operates on a fixed-size 3×3 tic-tac-toe board, meaning the input size is always constant. The board is stored as an array of strings, but since the size remains fixed, it does not impact the space complexity beyond O(1). Additionally, the function does not use any extra data structures like arrays, lists, or hash maps, but only a few integer variables for counting occurrences and looping through elements. The helper functions, such as the counting function and the winner-checking function, also use only a few additional variables that do not depend on input size. Since all the extra space used remains constant regardless of the board state, the overall space complexity is O(1). This means the function consumes a fixed amount of memory regardless of the input.
Similar Questions
This problem involves checking whether a given 9x9 Sudoku board is valid by ensuring that numbers don’t repeat in rows, columns, or 3x3 sub-boxes. It is similar because both problems require validating board states based on specific game rules.
This problem asks you to determine the winner of a Tic-Tac-Toe game given a sequence of moves. It involves tracking the game state and checking for win conditions, making it closely related to the validation logic in your current problem.