Este desafio é sobre o jogo Tic Tac Toe, mas é jogado em um toro.

Como jogar

Para criar o tabuleiro necessário, comece com um tabuleiro regular de jogo da velha. Primeiro dobre-o em um cilindro juntando as bordas esquerda e direita. Em seguida, dobre-o em toro juntando a borda superior e inferior. Aqui está uma visualização simples desse tabuleiro de jogo com alguns movimentos jogados (habilidades do Sick Paint!).

As regras do Tic Tac Toe em um toro são as mesmas do Tic Tac Toe comum. Cada jogador coloca Xs e Os alternados. O primeiro com 3 mesmos símbolos seguidos, uma coluna ou um na diagonal vence.

Como um toro é bastante difícil de visualizar, simplesmente projetamos o cartão de volta em um papel. Agora podemos jogar o jogo como Tic Tac Toe regular. A única diferença é que você também pode ganhar com 3 mesmos símbolos em uma diagonal quebrada. Por exemplo, o Jogador 1 (X) vence o seguinte quadro. Você pode ver isso facilmente, alterando um pouco a visão no toro.

Se você estiver interessado, você pode jogar Tic Tac Toe em um Torus nos Torus Games . Existe uma versão para Windows, Mac e Android.

Optimal Games

Neste desafio estavam interessados ​​em jogos ótimos. Um jogo ideal é um jogo em que ambos os jogadores jogam uma estratégia ideal. Em um tabuleiro regular de Tic Tac Toe, os jogos ideais sempre terminam em empate. Fascinantemente em um toro sempre o primeiro jogador vence. De fato, um jogo em um tabuleiro de toro nunca pode terminar em empate (também se os jogadores não jogarem o ideal).

A estratégia ideal é realmente fácil:

• Se você pode ganhar colocando seu símbolo, faça-o.
• Caso contrário, se o seu oponente tiver dois símbolos em uma linha / coluna / diagonal, tente bloqueá-lo. Caso contrário, faça o que quiser.
• Caso contrário, faça o que quiser.

Todo jogo ideal consiste em exatamente 7 jogadas e essas jogadas podem ser descritas da seguinte maneira:

1. O jogador 1 coloca um X em qualquer lugar do tabuleiro (9 opções)
2. O jogador 2 coloca um O em qualquer lugar do tabuleiro (8 opções)
3. O jogador 1 coloca um X em qualquer lugar do tabuleiro (7 opções)
4. O movimento do jogador 2 pode ser forçado (1 opção); caso contrário, ele coloca o O em qualquer lugar (6 opções)
5. A jogada do jogador 1 é forçada (1 escolha)
6. O jogador 2 está preso em um garfo (o jogador 1 pode vencer de duas maneiras diferentes); portanto, o jogador 2 precisa bloquear o jogador 1 de uma maneira (2 opções)
7. O jogador 1 coloca seu último lance e ganha (1 escolha)

Existem 9 * 8 * 1 * 6 * 1 * 2 * 1 + 9 * 8 * 6 * 1 * 1 * 2 * 1 = 1728 jogos ótimos diferentes em nosso quadro projetado. Aqui você pode ver um jogo ideal típico:

Se rotularmos cada célula do tabuleiro com os dígitos 0-8, podemos descrever esse jogo pelos dígitos 3518207. Primeiro, um X é um local na célula 3 (linha do meio, coluna da esquerda), que um O na célula 5 (linha do meio, coluna da direita), que um X na célula 1 (linha superior, coluna do meio), ...

Usando essa notação de dígito, geramos automaticamente um pedido. Agora podemos classificar todos os 1728 jogos ideais e temos a lista:

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

Desafio

Esta lista faz parte do seu trabalho. Você receberá um número kentre 0 e 1727 e precisará retornar o kjogo em notação de dígitos dessa lista classificada.

Escreva uma função ou um programa que receba o número k( número inteiro) calcule o jogo correspondente. Você pode ler a entrada via STDIN, argumento de linha de comando, argumento de prompt ou função e imprimir o resultado (7 dígitos) em um formato legível (por exemplo, 0123845ou [0, 1, 2, 3, 8, 4, 5]) ou retorná-lo usando uma sequência (formato legível por humanos) ou um número inteiro (contendo todos os dígitos na base 10) ou em qualquer formato de matriz / lista.

O tipo de desafio é o código-golfe. Portanto, o código mais curto vence.

JavaScript (ES6), 266308317333434

Uma função retornando uma string. Edit Encontrou uma solução aritmética para a função M (finalmente!)

F=(n,x=[],M=(a,b,t=-a-b)=>(a-b)%3?a<3&b<3?3+t:a>5&b>5?21+t:12+t:9+t+a%3*3)=>
[for(a of z='012345678')for(b of z)for(c of z)for(d of z) 
a-b&&c-a&&c-b&&(b-(y=M(a,c))?d==y:d-a&&d-b&&d-c)&&(
f=M(c,e=M(b,d)),g=M(a,e),g<f?[f,g]=[g,f]:0,r=a+b+c+d+e,x.push(r+f+g,r+g+f))]
&&x[n]

Muito ingênuo , pode ser reduzido de várias maneiras . Simplesmente enumera todos os possíveis valores legais e retorna o que é encontrado no local n. A função M retorna a posição entre duas células, que é o movimento obrigatório para bloquear um jogador oposto.

Mais legível

F=(n,x=[],
  M=(a,b,t=-a-b)=>(a-b)%3? 
     a<3&b<3?
       3+t // first row
       :a>5&b>5?
          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

Oitava, 467369363309297 caracteres

297:

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,:);

A única mudança relevante é que nunca verificamos se o jogador atual pode vencer, apenas verificamos a possibilidade do adversário de vencer no próximo turno . Como o único turno que o jogador pode vencer é o turno 7 , este é o único local em que o algoritmo produziria um jogo que não é ideal, mas é muito fácil filtrar essa situação. Simplesmente verificamos cada jogo gerado se ele foi vencido pelo jogador 1 - se não foi, a jogada por sua vez 7 foi incorreta, por isso não adicionamos esse jogo à tabela de jogos ideal.

(Exatamente metade dos jogos gerados por esta regra é falsa, ou seja, no 7º turno, o jogador 1 sempre tem duas possibilidades de bloquear o jogador dois, mas apenas um o fará vencer instantaneamente).

Usar:

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

O código ungolfed se parece com:

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

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

 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
  allgames=[allgames;s];
  return;
 end;
 poss=(find(~t));                  # for now all free slots are possible
 player=1+mod(numel(s),2);
 moves = canbewon(3-player);
 if numel(moves) poss=moves; end;  # ... no, we must block the other player
 for i=poss
  t(i)=player;
  games_starting_with([s char(i+47)]);
  t(i)=0;
 end
end

games_starting_with('');
f=@(n)(allgames(n+1,:));