This challenge is about the game Tic Tac Toe, but it's played on a torus.
How to play
To create the necessary game board, you start out with a regular Tic Tac Toe game board. First fold it into a cylinder by joining the left and the right edge. Then fold it into torus by joining the top and the bottom edge. Here's a simple visualization of such a game board with a few moves played (Sick Paint skills!).
The rules of Tic Tac Toe on a torus are the same as regular Tic Tac Toe. Each Player place alternating Xs and Os. The first one with 3 same symbols in a row, a column or a in a diagonal wins.
Since a torus is quite hard to visualize, we simply project the board back onto a paper. Now we can play the game as regular Tic Tac Toe. The only difference is, that you can also win with 3 same symbols in a broken diagonal. For instance Player 1 (X) wins the following board. You can see this easily by changing the view on the torus a little bit.
If your interested, you can play Tic Tac Toe on a Torus at Torus Games. There's a Windows, Mac and Android version.
In this challenge were interested in optimal games. An optimal game is a game, where both players play an optimal strategy. On a regular Tic Tac Toe board optimal games always end in a draw. Fascinatingly on a torus board always the first player wins. In fact a game on a torus board can never end in a draw (also if the players play not optimal).
The optimal strategy is really easy:
- If you can win by placing your symbol, do it.
- Otherwise if your opponent has two symbols in one row/column/điagonal, try to block him. Otherwise, do what you want.
- Otherwise do what you want.
Every optimal game consists of exactly 7 moves and these moves can be described in the following way:
- Player 1 places a X anywhere on the board (9 choices)
- Player 2 places an O anywhere on the board (8 choices)
- Player 1 places a X anywhere on the board (7 choices)
- Player 2's move may be forced (1 choice), if not, he places the O anywhere (6 choices)
- Player 1's move is forced (1 choice)
- Player 2 is caught in a fork (Player 1 can win in two different ways), so Player 2 has to block Player 1 in one way (2 choices)
- Player 1 places the his last move and wins (1 choice)
There are 9*8*1*6*1*2*1 + 9*8*6*1*1*2*1 = 1728 different optimal games on our projected board. Here you can see one typical optimal game:
If we label each cell of the board with the digits
0-8, we can describe this game by the digits
3518207. First a X is places in the cell 3 (middle row, left column), than an O in cell 5 (middle row, right column), than a X in cell 1 (upper row, middle column), ...
Using this digit notation we automatically generated an order. Now we can sort all of the 1728 optimal games and we get the list:
Game 0000: 0123845 Game 0001: 0123854 Game 0002: 0124735 Game 0003: 0124753 Game 0004: 0125634 ... Game 0674: 3518207 ... Game 1000: 5167423 Game 1001: 5167432 Game 1002: 5168304 ... Game 1726: 8765034 Game 1727: 8765043
This list is part of your job. You will receive one number
k between 0 and 1727 and you have to return the
kth game in digit notation of that sorted list.
Write a function or a program, that receives the number
k (integer) computes the correspondent game. You can read the input via STDIN, command-line argument, prompt or function argument and print the result (7 digits) in a readable format (e.g.
[0, 1, 2, 3, 8, 4, 5]) or return it using an string (human readable format) or an integer (containing all digits in base 10), or in any array/list format.
The challenge type is code-golf. Therefore the shortest code wins.