Perfect Tic-Tac-Toe

A computer that never makes a mistake is playing tic-tac-toe, on the usual 3 by 3 board or on a bigger 4 by 4 one. board is a list of n strings of length n (n is 3 or 4), with 'X', 'O' and '.' for an empty square. X always moves first, so X is to move when both players have the same number of marks, and O is to move otherwise. A player wins by filling a whole row, a whole column or one of the two long diagonals with their mark; the game is a draw when the board fills up with no winner.

Both players play perfectly:

• a player who can force a win plays to win in as few moves as possible;
• a player who cannot win but can force a draw plays for the draw;
• a player who is sure to lose plays to make the game last as many moves as possible.

Moves are counted for both players together, up to the end of the game. Write best_move(board) that returns a tuple ((row, col), result) for the player to move: the square to play, and how the game ends with perfect play, 'win', 'draw' or 'loss' from that player's point of view. If several squares are equally good (the same result and, for a win or a loss, the same number of moves until the end), return the first of them in reading order: the smallest row, then the smallest column.

Examples

best_move(['XX.', 'OO.', '...'])   # returns ((0, 2), 'win')
best_move(['XO.', '.X.', '...'])   # returns ((2, 2), 'loss')
best_move(['...', '...', '...'])   # returns ((0, 0), 'draw')

On the first board X wins at once by completing the top row. On the second, O is lost, but blocking the diagonal at (2, 2) makes the game last longest. On the empty board every first move leads to a draw, so the top left corner is returned.

Constraints

• The board comes from a real game: nobody has won yet, and at least one square is empty.
• A 4 by 4 board has at most 10 empty squares.