The well-known game of Ultimate Tic-Tac-Toe is played on a 9×99\times 9 board (with the rows and columns numbered by 0,1,…,80,1,\ldots,8), conceptually divided into nine 3×33\times 3 small boards. The players are denoted by "X" and "O" and take turns, starting with X.
At each turn, a player picks an empty cell from the board and adds their symbol to it. The main constraint is that whenever possible, the small board in which the player is placing their symbol must correspond to the cell the previous player played in. Formally: If a player plays in the (x,y)(x,y) cell, the next player should pick a cell in the (x mod 3,y mod 3)(x \text{ mod } 3, y \text{ mod } 3) small board.
For example, say X plays in the cell (4,6)(4,6), i.e., the fifth row and the seventh column. This cell is part of the middle-right small board. Inside that 3×33\times 3 board, that is the leftmost cell in the middle row. Hence, the next move (of the O player) must be played in the middle-left small board (in any free cell of that board), i.e., board (1,0)(1, 0).
At any stage of the game, if a player makes a winning move (in the usual Tic-Tac-Toe sense) on a 3×33\times 3 small board, that board is considered "locked" and its global value is the same as that of the winning player. If the small board is fully filled without a winner, it's also considered "locked" but has no global value.
If the small board a player is supposed to play inside (according to the rule previously described) is locked, the player is free to choose any cell from any non-locked small board instead.
The game is won if the global values of the small boards are determined in such a way that if the small boards are viewed as cells in a 3×33\times 3 grid, they were filled in a winning way (in the usual Tic-Tac-Toe sense).
We can number the cells of a board by the numbers 0,1,2,…,800,1,2,\ldots,80, beginning with the top-left cell and proceeding by rows (so the first row is 0,1,…,80,1,\ldots, 8, the second is 9,10,…,179,10,\ldots,17, etc). With this numbering, a game can be described as a sequence of numbers. As an example, consider the following game
Ending in the board
where O wins by a diagonal of small boards.
An Ultimate Ultimate Tic-Tac-Toe Game is a game such that
- The game lasts 81 moves (meaning the whole board is filled);
- The last 9 moves each win one of the small boards (no ties and no small board is won earlier than that);
- The last move wins the game.
Note that it's OK if the game has moves we'll usually consider irrational (opportunities to win a small board that are ignored by the player) since the goal here is to achieve these three conditions, and we can consider both X and O as trying to cooperate in order to succeed.
Your goal: Find an Ultimate Ultimate Tic-Tac-Toe Game. Provide your solution in the format described.
A Bonus "*" will be given for finding an Ultimate Ultimate Tic-Tac-Toe Game for the 5x5 case, meaning 25 small boards of 5×55\times 5 cells each, with moves numbered by 0,1,…,6240,1,\ldots,624.
/)
