eqdist FINAL

def board_legal(board):
    for i in range(9):
        for j in range(1, 4):
            if i + 2 * j < 9:
                if board[i] != "_" and board[i] == board[i + j] and board[i] == board[i + 2 * j]:
                    return False
    return True


def move_legal(board, player, move):
    board[move] = player
    if board_legal(board):
        board[move] = "_"
        return True
    else:
        board[move] = "_"
        return False


def no_moves_left(board, player):
    for i in range(9):
        if board[i] == "_" and move_legal(board, player, i):
            return False
    return True


def switch_players(player):
    if player == "X":
        return "O"
    else:
        return "X"


def play_move(board, player, move, end_set, game):
    board[move] = player
    new_game = game
    new_game += ''.join(board)
    new_game += ", "
    do_turn(board, switch_players(player), end_set, new_game)
    board[move] = "_"


def moves_blocked(board, player, move, blockee):
    current_moves = 0
    for i in range(9):
        if board[i] == "_" and move_legal(board, blockee, i):
            current_moves += 1
    board[move] = player
    for i in range(9):
        if board[i] == "_" and move_legal(board, blockee, i):
            current_moves -= 1
    board[move] = "_"
    return current_moves


def do_turn(board, player, end_set, game):
    if no_moves_left(board, player) and switch_players(player) == "X":
        end_set.add(game)
    else:
        if player == "X":  # #go over all possible moves for player 1
            for i in range(9):
                if board[i] == "_" and move_legal(board, player, i):
                    play_move(board, player, i, end_set, game)
        else:  # go over possible moves for player 2, according to strategy
            if board[0] == "_" and move_legal(board, player, 0):  # #first priority is edges
                play_move(board, player, 0, end_set, game)
            if board[8] == "_" and move_legal(board, player, 8):
                play_move(board, player, 8, end_set, game)
            if board[8] != "_" and board[0] != "_":  # if edges are not free
                if board[8] == "O" and board[0] == "O":  # in all cases where both edges are "O",
                    for i in [1, 3, 4, 5, 7]:  # the only way to lose is to place a circle in 2,6
                        if board[i] == "_" and move_legal(board, player, i):
                            play_move(board, player, i, end_set, game)
                else:
                    if board == ["O", "X", "_", "_", "_", "_", "_", "_", "X"]:
                        play_move(board, player, 2, end_set, game)
                    else:
                        x = -1
                        max_delta = -10000
                        for i in range(9):
                            if board[i] == "_":
                                i_delta = moves_blocked(board, player, i, "X") - moves_blocked(board, player, i, "O")
                                if i_delta > max_delta:
                                    x = i
                                    max_delta = i_delta
                        play_move(board, player, x, end_set, game)


def main():
    board = ["_", "_", "_", "_", "_", "_", "_", "_", "_"]
    player = "X"
    end_set = set()
    do_turn(board, player, end_set, "")
    new_set = set()
    count_x = [0, 0, 0, 0, 0, 0, 0, 0, 0]
    count_o = [0, 0, 0, 0, 0, 0, 0, 0, 0]
    for a in end_set:
        if a[::-1] not in new_set:
            if a[0] != "X":
                new_set.add(a[::-1])
            if a[0] == "X":
                new_set.add(a)
    for a in end_set:
        print(a)
    #     for i in range(9):
    #         if a[i] != "_":
    #             if a[i] == "X":
    #                 count_x[i] = count_x[i] + 1
    #             else:
    #                 count_o[i] = count_o[i] + 1
    # x_percent = [i * 100 / len(new_set) for i in count_x]
    # o_percent = [i * 100 / len(new_set) for i in count_o]
    # print(x_percent)
    # print(o_percent)
    print(len(new_set))


main()