Untitled
unknown
python
2 months ago
2.9 kB
6
Indexable
def is_winner(board, player): """Check if the given player has won.""" # Check rows for i in range(0, 9, 3): if board[i:i+3] == [player] * 3: return True # Check columns for i in range(3): if board[i::3] == [player] * 3: return True # Check diagonals if board[0::4] == [player] * 3: return True if board[2:7:2] == [player] * 3: return True return False def is_valid_game_state(board): """ Check if the game state is valid: - X's count should be equal to or one more than O's count - There shouldn't be two winners """ x_count = board.count('X') o_count = board.count('O') # Check if moves are in valid sequence if not (x_count == o_count or x_count == o_count + 1): return False # Check if both players won (impossible) x_won = is_winner(board, 'X') o_won = is_winner(board, 'O') if x_won and o_won: return False # If O won, X shouldn't have played last if o_won and x_count > o_count: return False # If X won, they must have played last if x_won and x_count <= o_count: return False return True def get_valid_moves(board): """Get list of empty positions.""" return [i for i, val in enumerate(board) if val == ''] def is_game_over(board): """Check if the game is over (winner or full board).""" return is_winner(board, 'X') or is_winner(board, 'O') or '' not in board def count_all_games(): def dfs(board, is_x_turn): # If this is an invalid game state, backtrack if not is_valid_game_state(board): return 0 # If game is over, we found a valid completed game if is_game_over(board): return 1 # Try all possible next moves count = 0 player = 'X' if is_x_turn else 'O' for move in get_valid_moves(board): new_board = board.copy() new_board[move] = player count += dfs(new_board, not is_x_turn) return count # Start with empty board, X plays first initial_board = [''] * 9 return dfs(initial_board, True) def print_example_game(): """Print an example valid game for verification.""" board = [''] * 9 moves = [0, 4, 1, 3, 2] # X wins with top row for i, move in enumerate(moves): board[move] = 'X' if i % 2 == 0 else 'O' print(f"\nMove {i+1}:") for row in range(3): print(' '.join(cell if cell != '' else '_' for cell in board[row*3:(row+1)*3])) return board if __name__ == "__main__": total_games = count_all_games() print(f"\nTotal number of valid completed games: {total_games}") print("\nExample of a valid game (X wins):") print_example_game()
Editor is loading...
Leave a Comment