The Tic Tac Toe Dictionary

Question

A TicTacToe game can be represented by a string denoting the sequence of positions as the players make their move.

0 1 2
3 4 5
6 7 8

Assume X always plays first.

So a string of "012345678" denotes the game

X O X
O X O
X O X

Notice, the game is already won when Player X marks 6, at that point the game ends, granting a win to X. (ie, ignore the remaining moves once a player wins)

Your challenge (code) is to print all the games (sorted order) and its results.

The Format

<movesequence>:<result>\n

eg:

012345678:X
012345687:X
012345768:X
...

Denote X for the 1st player winning, O for the second player, and D for Draws.

There will be 9! (362880) games.

Here is some data to verify your results.

'X' Wins: 212256 
'O' Wins: 104544 
Draws : 46080 

This is a codegolf, and runtime should be within a minute. Have Fun!

EDIT: Removed excess details, and just print it on stdout. No need to create a file.

Answer 1

Ruby 1.9, 201 characters

r=*[*l=0..8,0,3,6,1,4,7,2,5,8,0,4,8,2,4,6].each_slice(3)
w=->a{r.any?{|b|b&a==b}}
[*l].permutation(9){|a|u=[[],[]];i=-1
u[i%2]<<a[i+=1]while !((x=w[u[1]])||o=w[u[0]])&&i<8
puts a*""+":#{x ??X:o ??O:?D}"}

Slightly golfed so far. Takes about 45 seconds to complete here.

• Edit: (268 -> 249) Write to stdout instead of a file
• Edit: (249 -> 222) Don't pre-fill the array with each player's moves.
• Edit: (222 -> 208) Shorter way to find out if a player won
• Edit: (208 -> 213) Back to 213, the previous solution was too slow.
• Edit: (213 -> 201) Some rearrangements, removed whitespace

Answer 2

J, 124 chars

((],~':',~1":[){&'DOX'@(</+2*>/)@:(<./"1)@:(((2{m/.@|.),(2{m/.),m"1,>./)"2)@(<:@(>:%2|]),:(%(2|>:)))@(3 3$]))"1((i.!9)A.i.9)

X win, O win and Draw counts check out.

Was a bit painful to debug though. :)

Answer 3

Haskell, 224 222 characters

import Data.List
p=sort.permutations
a(e:_:z)=e:a z;a z=z
[c,d]%(e:z)|any((`elem`words"012 345 678 036 147 258 048 246").take 3).p.a.reverse$e=c|1<3=[d,c]%z;_%[]='D'
main=putStr$p['0'..'8']>>=(\s->s++':':"OX"%inits s:"\n")

Alas, the permutations function from Data.List doesn't produce permutations in lexographic order. So I had to expend 6 characters on the sort.

Answer 4

APL (139)

This can probably be shortened more, but it was hard enough as it is. Believe it or not, it runs in about 45 seconds on my computer (excluding the time it takes to output everything, when output to the screen).

↑{⊃,/(,/⍕¨⍵-1),':',{1∊T←↑{∨/↑{⍵∘{⍵≡⍵∧⍺}¨↓⍉(9⍴2)⊤⎕UCS'㗀㐇㔤㑉㔑㑔'}¨↓(M∘.≥M)∧[2]M∊⍵}¨↓⍉5 2⍴0,⍨⍵:'XO'[1+</+/T]⋄'D'}⍵}¨↓{1≥⍴⍵:↑,↓⍵⋄↑⍪/⍵,∘∇¨⍵∘~¨⍵}M←⍳9

Explanation:

• M←⍳9: Store in M the numbers from 1 to 9. Internally, this program uses 1..9 instead of 0..8.
• {...}: a function to get all permutations:
  • 1≥⍴⍵:↑,↓⍵: if the length is smaller or equal to 1, return the argument as a matrix.
  • ⋄↑⍪/⍵,∘∇¨⍵∘~¨⍵: otherwise, remove each character in ⍵ from ⍵, get the permutations of that, and add the character back in.
• ¨↓: for each permutation...
• {...}: a function that gives the winner for that permutation:
  • ⊃,/(,/⍕¨⍵-1),':',{...}⍵: get the permutation as a string, with all the numbers decreased by 1 (to get the required 0..8 output instead of 1..9), followed by a colon, followed by the character denoting the winner:
    • ⍉5 2⍴0,⍨⍵: separate the moves by X from the moves by O. Because O has one move less than X, that space is filled by 0, which is unused and so does not influence the result.
    • {...}¨↓: for both the X board and the O board, run the following function which determines whether there is a win in one of the nine timesteps:
      • (M∘.≥M)∧[2]M∊⍵: Generate a bitboard from the move numbers, and and this bitboard with the bitstrings 100000000, 110000000 ... 111111111 to get the state of the board at each of the nine moments in time.
      • {...}¨↓: for each of these, run the following function:
        • ⍉(9⍴2)⊤⎕UCS'㗀㐇㔤㑉㔑㑔': get the bitboards for each possible winning situation
        • ⍵∘{⍵≡⍵∧⍺}¨↓: and each winning state with the current bitboard and check if said winning state is still there
      • ∨/↑: or these together, giving whether there is a win on this bitboard
    • 1∊T←↑: make a 9x2 matrix, with the 9 X-timesteps on the first row and the 9 O-timesteps on the second row. Store this in T. If there is a 1 in this matrix, someone has won.
    • :'XO'[1+</+/T]: If someone has won, give 'X' or 'O' depending on whose 1 was first.
    • ⋄'D': If nobody has won, give 'D'.
• ↑: make a matrix out of these so that they are each displayed on a separate row.

Answer 5

Python Ungolfed

from itertools import*
r=range
W=[[0,1,2],[3,4,5],[6,7,8],[0,3,6],[1,4,7],[2,5,8],[0,4,8],[2,4,6]]
def c(B):
    for i in r(8):
                if B[W[i][0]]==B[W[i][1]]==B[W[i][2]]:
                        return 1
        return 0

for i in permutations('012345678',9):
    B=[]
    for j in r(9):
        B.append(-(j+1))
    k=0
    F=1
    for j in r(9):
        k=[1,0][k]
        B[int(i[j])]=k
        if c(B):
            F=0
            break
    print "".join(i),':',[['0','X'][k],'D'][F]

Answer 6

C++ Ungolfed

#include<iostream>
using namespace std;
#include<algorithm>

int check(int B[])
{
        for (int i=0;i<3;i++)
                if ((B[3*i]==B[3*i+1]&&B[3*i]==B[3*i+2]) || (B[i]==B[i+3]&&B[i]==B[i+6]))
                        return 1;
        if ((B[2]==B[4]&&B[2]==B[6]) || (B[0]==B[4]&&B[0]==B[8]))
                return 1;
        return 0;               
}
int main()
{
        char c[11]="012345678";
        int B[9],i,j;
        do{
                for (i=0;i<9;i++)B[i]=-(i+1);
                for (i=0,j=1;i<9;i++,j=j?0:1)
                {
                        B[c[i]-'0']=j;
                        if (check(B))
                                break;
                }
                printf("%s:%c\n",c,i<9?j?'X':'O':'D');
        }while (next_permutation(c,c+9));
}

Answer 7

Python 2.7 (237)

from itertools import*
for z in permutations('012345678'):
 k,F=0,[9]*9
 for h in z:
    F[int(h)]=k=1-k
    if any(sum(a)in(0,3)for a in(F[:3],F[3:6],F[6:],F[::3],F[1::3],F[2::3],F[::4],F[2:8:2])):break
 else:k=2
 print"".join(z)+':','OXD'[k]