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.
Optimal Games
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
Challenge
This list is part of your job. You will receive one number k
between 0 and 1727 and you have to return the k
th 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. 0123845
or [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.