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!).

Tic Tac Torus

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.

Player 1 (X) wins because of 3 Xs in one broken diagonal

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:

  1. Player 1 places a X anywhere on the board (9 choices)
  2. Player 2 places an O anywhere on the board (8 choices)
  3. Player 1 places a X anywhere on the board (7 choices)
  4. Player 2's move may be forced (1 choice), if not, he places the O anywhere (6 choices)
  5. Player 1's move is forced (1 choice)
  6. 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)
  7. 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:

Example of an 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. 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.

  • \$\begingroup\$ Why does player 2's first move have to be in the same row or column as player 1's first move? I've played out a few games in my head where player 2's first move is in one of the same diagonals instead and they follow the same optimal game pattern. It seems to me that one of the aspects of the toroidal board is that rows, columns, and diagonals have symmetric effects on the game. \$\endgroup\$ – Runer112 Apr 14 '15 at 12:49
  • \$\begingroup\$ @Runer112 Simplified the optimal strategy a lot. The only rule now is block your opponent if you can, otherwise do what you want. \$\endgroup\$ – Jakube Apr 14 '15 at 13:24
  • 8
    \$\begingroup\$ Just a side comment: actually there are much fewer unique games possible here. Translational symmetry makes the position of the first move irrelevant (because you can always center your view), so divide by 9... and rotation of the board makes for only 2 different second moves (diagonal or adjacent square)... so at most 48 distinct games. If you take into account reflection symmetry, it goes down even further. This torus version is much more boring than the regular one. Golf away. \$\endgroup\$ – orion Apr 15 '15 at 10:31
  • \$\begingroup\$ @orion Actually the fact that torus wraps, does not forbid us to think of '0' as the 'first' rect on the torus board and distinguish all nine fields in general... Yet we agree upon "meridian 0" being at Greenwich, while on the opposite of the Earth we can be one leg in place where it's Thursday, one leg in place it's Wednesday (24h difference in local time!) - and all in spite of the fact that the Earth is round and does not have a "starting point"... \$\endgroup\$ – pawel.boczarski Apr 15 '15 at 20:22
  • \$\begingroup\$ @Rodney Nope, it's a one, not a seven. Try calculating it. \$\endgroup\$ – Jakube Apr 21 '15 at 20:54

JavaScript (ES6), 266 308 317 334 341

A function returning a string. Edit Found an arithmetic solution for function M (at last!)

[for(a of z='012345678')for(b of z)for(c of z)for(d of z) 

Very naive , it can be shortened in many ways. It simply enumerates all the possible legal values and returns what find at place n. The M function returns the position in between two cells, that is the mandatory move to block an opposite player.

More readable

       3+t // first row
          21+t // last row
          :12+t // middle row and diags
     :9+t+a%3*3 // columns
  [for(a of z='012345678') // enumerate the first 4 moves
     for(b of z)
       for(c of z)
         for(d of z) 
           a-b&&c-a&&c-b // avoid duplicates
           &&(b-(y=M(a,c))?d==y:d-a&&d-b&&d-c) // and check if d must block a-c or it's free
             e=M(b,d), // forced to block b-d
             f=M(c,e),g=M(a,e),g<f?[f,g]=[g,f]:0, // f and g could be in the wrong order
             r=a+b+c+d+e, // start building a return string
             x.push(r+f+g,r+g+f) // store all values in x
  )]&&x[n] // return value at requested position
| improve this answer | |

APL (Dyalog Unicode), 73 bytes

⎕⊃z/⍨(∧/{⍵[4⍪3 2⍴5 6 1 3]∊⍨∘{3⊥3|-+/3 3⊤⍵}¨⍥↓⍵[1 3⍪3 2⍴0 4 2]},≠)¨z←,⍳7⍴9

Try it online!

A full program, and takes way too much time and memory to complete for any input. Also, the code includes some 18.0 features that aren't yet available on TIO. The TIO link includes a faster version using only features up to 17.1, so that the output can be checked.

Winning or blocking position

Given two positions, extract their row and column numbers. For each dimension (row/column), if the numbers are the same, so is the result; otherwise, the result is the third number. In both cases, the result coordinates can be found with the following property:

n1  n2  res  -(n1+n2)%3
0   0   0    0
0   1   2    2
0   2   1    1
1   0   2    2
1   1   1    1
1   2   0    0
2   0   1    1
2   1   0    0
2   2   2    2

The resulting code is as simple as the following.

{3⊥3|-+/3 3⊤⍵}  ⍝ ⍵←two positions
        3 3⊤⍵   ⍝ Convert the numbers to base 3, each number → column
      +/        ⍝ Sum of each row
   3|-          ⍝ Negate and modulo 3
 3⊥             ⍝ Convert from base 3 to integer

How the code works

z←,⍳7⍴9      ⍝ Create an array of 7-tuples of 0..8
z/⍨(...)¨z   ⍝ Filter the tuples by the following condition:
  ∧/{...},≠  ⍝ Check that Unique Mask (≠) is all ones AND it is an optimal TTT game:
    ⍵[...] ... ⍵[...]  ⍝ Extract certain indexes of the given tuple as matrices
    ⍥↓                 ⍝ Downrank both sides into four 2-tuples
    ∘{...}¨            ⍝ For each tuple of the right side,
      3⊥3|-+/3 3⊤⍵     ⍝ Compute the cell that completes a line in TTT
    ∊⍨                 ⍝ And check that the right side appears in
                       ⍝ the matching tuple on the left side
⎕⊃  ⍝ Take input n from stdin and pick the nth 7-tuple

Left side idxs  ≡ ↓4⍪3 2⍴5 6 1 3 ≡ (4 4)(5 6)(1 3)(5 6)
Right side idxs ≡ ↓1 3⍪3 2⍴0 4 2 ≡ (1 3)(0 4)(2 0)(4 2)

Left  Right  Meaning
1 3   2 0    Turns 1 and 3 (by P1) are blocked by either Turn 2 or 4
4 4   1 3    Turns 2 and 4 (by P2) are blocked by Turn 5
5 6   0 4    Turn 6 blocks one of Turns 1,5 or Turns 3,5, and
             Turn 7 completes the other
5 6   4 2    ↑
| improve this answer | |

Octave, 467 369 363 309 297 characters


global t=0*(1:9)m=dec2bin([15;113;897;1170;1316;1608;2370;2216;2580])-48 a;
function g(s,p)global a t m;
if nnz(s)<8&&any((t==1)*m>2)a=[a;s];return;end;q=t==3-p;
(r=sort(~q.*(1:9)*m(:,find([3 1]*([q;t==p]*m)==6)')))||(r=find(~t));
for i=r t(i)=p;g([s i+47],3-p);t(i)=0;end;end;g('',1);f=@(n)a(n+1,:);

The only relevant change is that we never check if the current player can win, only check the opponent's possibility to win the next turn. As the only turn the player 1 can win is turn 7, this is the only place when the algorithm would produce game that is not optimal, but it's very easy to filter such a situation out. We simply verify each game generated if it's won by player 1 - if it was not, the move in turn 7 was incorrect, so we don't add this game to optimal games table.

(Exactly half the games generated by this rule are false ie. in the 7th turn the player 1 always has two possibilities to block player two, but only one will make him win instantly).


$ octave
octave:1>> source script.m
octave:2>> f(634)
ans = 3270148

The ungolfed code looks like:

 global t=0*(1:9);
 global m=dec2bin([15;113;897;1170;1316;1608;2370;2216;2580])-48;
 global allgames;

 function r=canbewon(by)
  global t m
  g=(find([3 1]*q==6))';
  r=sort((~(t==by).*(1:9)) * m(:,g));

 function games_starting_with(s)
 global allgames t;
 if 7==numel(s) && any((t==1)*m==3) # it's 7th move and first player won
 poss=(find(~t));                  # for now all free slots are possible
 moves = canbewon(3-player);
 if numel(moves) poss=moves; end;  # ... no, we must block the other player
 for i=poss
  games_starting_with([s char(i+47)]);

| improve this answer | |
  • 1
    \$\begingroup\$ small hint: you can cut out old versions if they use the same logic since these are stored in the edit history so they are still available \$\endgroup\$ – masterX244 Apr 24 '15 at 14:52

APL (Dyalog Extended), 72 bytes

7↑⎕⊃∧⍋¨5 6g,¨(⊂⍳3)(∪⊢,⌽¨,⊖¨,⊢∘⌽¨)⍣≡1 3g⊂3 3⍴⊃4 6 8g⊂⍳9

Try it online!

Decided to post as a separate answer, because the approach is drastically different.

Inspired from orion's comment, this one generates all optimal games by transforming a single game board in various ways.

The 3x3 toroidal board is very very permissive on its transformations; the three-in-a-rows are preserved through reflection, rotation (e.g. cycling the top row to the bottom), and shear (e.g. cycling elements of each row 0, 1, 2 units to the right respectively). With this information, I could identify four seed boards that have distinct topology (using 0 to 6 to denote the seven moves made in sequence):

P2#4 not forced
0 1 2    0 1 2
3 6 5    3 5 6
x x 4    x x 4

P2#4 forced
0 3 2    0 3 2
1 6 5    1 5 6
x x 4    x x 4

Then I tried various combinations of the transformations to find a short one that generates all 1728 boards. And I noticed that even the seed boards can be generated from one board, by swapping the positions of 1-3 (decides whether the 4th move is forced) and 5-6 (swap a block and a win).

How it works

⍝ Helper function
1⌽@(∊∘⍺)¨⍵  ⍝ Cycle the positions of ⍺s in each of ⍵
⍵,⍨  ⍝ Prepend the above to ⍵

⍝ Main program
7↑⎕⊃∧⍋¨5 6g,¨(⊂⍳3)(∪⊢,⌽¨,⊖¨,⊢∘⌽¨)⍣≡1 3g⊂3 3⍴⊃4 6 8g⊂⍳9
3 3⍴⊃4 6 8g⊂⍳9  ⍝ Generate the seed board:
0 1 2
3 6 5
8 7 4
5 6g 1 3g  ⍝ Generate four seed boards from the above,
           ⍝ by swapping the numbers 1-3 and 5-6
(⊂⍳3)(...)⍣≡  ⍝ Repeat certain transformations until all are found:
  ⊢∘⌽¨  ⍝ Reverse the order of columns:
a b c   c b a
d e f → f e d
g h i   i h g
  ⊖¨,   ⍝ Join with vertical shear:
a b c   a e i
d e f → d h c
g h i   g b f
  ⌽¨,   ⍝ Join with horizontal shear:
a b c   a b c
d e f → e f d
g h i   i g h
  ∪⊢,   ⍝ Join with original and take unique results

⍋¨,¨  ⍝ Flatten each 3x3 matrix and extract where each number is
∧     ⍝ Ascending sort
⎕⊃    ⍝ Take input n and pick nth result
7↑    ⍝ Take first 7, since the last two are garbage
| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.