import copy

def evaluate(perspective, whose_turn, other_player, board):
  # perspective 'X' or 'O': who is running this simulated game and wants to win
  # whose_turn 'X' or 'O': in this simulated game, whose turn is it?
  # other_player 'X' or 'O': different from whose_turn
  # board is an N ? N array of ' ', 'X', or 'O'
  w = winner(board)
  if w == whose_turn:
    if perspective == w:
      return +1
    else:
      return -1
  elif w != ' ':
    if perspective == w:
      return -1
    else:
      return +1
  else:
    loss = False
    tie = False
    win = False
    for pnb in possible_next_boards(board, other_player):
      e = evaluate(perspective, other_player, whose_turn, pnb)
      if e == -1:
        loss = True
      elif e == +1:
        win = True
      else:
        tie = True
    if win and not loss and not tie:
      return +1
    elif (win or tie) and not loss:
      return 0
    else:
      return -1

def winner(board):
  # I'm sure this could be done a lot more efficiently
  N = len(board)

  win = True
  first = board[0][0]
  for i in range(1, N):
    if board[i][i] != first:
      win = False
  if win and first != ' ':
    return first

  win = True
  first = board[0][N - 1]
  for i in range(1, N):
    if board[i][N - 1 - i] != first:
      win = False
  if win and first != ' ':
    return first

  for r in range(0, N):
    win = True
    first = board[r][0]
    for i in range(1, N):
      if board[r][i] != first:
        win = False
    if win and first != ' ':
      return first

  for c in range(0, N):
    win = True
    first = board[0][c]
    for i in range(1, N):
      if board[i][c] != first:
        win = False
    if win and first != ' ':
      return first

  return ' '

def possible_next_boards(board, whose_turn):
  N = len(board)
  result = []
  for r in range(0, N):
    for c in range(0, N):
      if board[r][c] == ' ':
        new_board = copy.deepcopy(board)
        new_board[r][c] = whose_turn
        result.append(new_board)
  return result

def move(whose_turn, other_player, board):
  tie = None
  loss = None
  for pnb in possible_next_boards(board, whose_turn):
    e = evaluate(whose_turn, whose_turn, other_player, pnb)
    if e == +1:
      return pnb
    elif e == 0:
      tie = pnb
    else:
      loss = pnb
  if tie:
    return tie
  if loss:
    return loss
  return None

def play(N):
  board = [ [' '] * N for i in range(0, N) ]
  whose_turn = 'X'
  other_player = 'O'
  moves = 0
  while True:
    next = move(whose_turn, other_player, board)
    moves += 1
    if next == None:
      print("tie")
      break
    print("result of move", moves)
    print_board(next)
    result = winner(next)
    if result != ' ':
      print(result, "won")
      break
    (whose_turn, other_player) = (other_player, whose_turn)
    board = next

def print_board(board):
  N = len(board)
  bar = "-" * (N * 2 - 1)
  print("|".join(board[0]))
  for i in range(1, N):
    print(bar)
    print("|".join(board[i]))
  print()