Recently I came across the following problem in a contest. We tried the problem for a long time, but could not come up with a correct solution.
Alice and bob are playing a game across $$$ n \leq 10000 $$$, 3×3 Tic-tac-toe boards with both players marking the board with X. Each board already has some X's on it. One player can choose an arbitrary board and put an X on any of the empty cells. Alice always makes the first move. You can not make any further moves on a board after it has three consecutive X's (column, row or diagonal). A game ends when all the boards contain three consecutive X's. The player that made the last move loses the game.
Given a configuration of the game, you have to find out the winner. It is given that none of initial boards contain three consecutive X's.
5 1 XX. ..X ..X 1 ..X X.. X.X 1 ..X .X. .X. 1 ..X X.. XX. 1 ..X X.. ..X
Game #1: Alice Game #2: Alice Game #3: Bob Game #4: Bob Game #5: Bob