Answer for TicTacToe Homework #1

# My answers to TicTacToe Homework #1
# Using a depth-first search of the game tree.

# Here, my use of "board" is the same as my later use of "layout" -- it's the 9-char string

Wins = [[0,1,2],[3,4,5],[6,7,8],[0,3,6],[1,4,7],[2,5,8],[0,4,8],[2,4,6]]

NumGames = 0
NumBoards = 0
Boards = set()

def GamesAndBoards(starting_board):
    global NumBoards, Boards, NumGames

    NumGames = 0
    Boards = set()
    TryAllMoves(starting_board)
    NumBoards = len(Boards)

def TryAllMoves(board):
    global NumGames
    
    Boards.add(board)

    # Is this the final board in a game?
    if IsWin(board) or board.count('_') == 0:
        NumGames += 1
        return
    
    # Find all children of this board
    move = 'x' if board.count('o') == board.count('x') else 'o'
    for pos in range(9):
        if board[pos] == '_':
            new_board = board[:pos] + move + board[pos+1:]
            TryAllMoves(new_board)

def IsWin(board):
    for awin in Wins:
        if board[awin[0]] == board[awin[1]] and board[awin[1]] == board[awin[2]] and board[awin[0]] != '_':
            return True
    return False

GamesAndBoards('_________')
print (NumBoards, NumGames)

Number of Games = 255,168
Number of Boards = 5,478

By the way, here are the number of games that end in "x-wins", "o-wins" and draws:
x-wins: 131,184
o-wins: 77,904
draws: 46,080