All Possible Tic Tac Toe Winning Combinations

Question

I had an interview were I was asked a seemingly simple algorithm question: "Write an algorithm to return me all possible winning combinations for tic tac toe." I still can't figure out an efficient way to handle this. Is there a standard algorithm or common that should be applied to similar questions like this that I'm not aware of?

Accepted Answer

This is one of those problems that's actually simple enough for brute force and, while you could use combinatorics, graph theory, or many other complex tools to solve it, I'd actually be impressed by applicants that recognise the fact there's an easier way (at least for this problem).

There are only 39, or 19,683 possible combinations of placing `x`, `o` or `<blank>` in the grid, and not all of those are valid.

First, a valid game position is one where the difference between `x` and `o` counts is no more than one, since they have to alternate moves.

In addition, it's impossible to have a state where both sides have three in a row, so they can be discounted as well. If both have three in a row, then one of them would have won in the previous move.

There's actually another limitation in that it's impossible for one side to have won in two different ways without a common cell (again, they would have won in a previous move), meaning that:

```
XXX
OOO
XXX
```

cannot be achieved, while:

```
XXX
OOX
OOX
```

can be. But we can actually ignore that since there's no way to win two ways without a common cell without having already violated the "maximum difference of one" rule, since you need six cells for that, with the opponent only having three.

So I would simply use brute force and, for each position where the difference is zero or one between the counts, check the eight winning possibilities for both sides. Assuming only one of them has a win, that's a legal, winning game.

Below is a proof of concept in Python, but first the output of `time` when run on the process sending output to `/dev/null` to show how fast it is:

```
real    0m0.169s
user    0m0.109s
sys     0m0.030s
```

The code:

```
def won(c, n):
  if c[0] == n and c[1] == n and c[2] == n: return 1
  if c[3] == n and c[4] == n and c[5] == n: return 1
  if c[6] == n and c[7] == n and c[8] == n: return 1

if c[0] == n and c[3] == n and c[6] == n: return 1
  if c[1] == n and c[4] == n and c[7] == n: return 1
  if c[2] == n and c[5] == n and c[8] == n: return 1

if c[0] == n and c[4] == n and c[8] == n: return 1
  if c[2] == n and c[4] == n and c[6] == n: return 1

return 0

pc = [' ', 'x', 'o']
c = [0] * 9
for c[0] in range (3):
  for c[1] in range (3):
    for c[2] in range (3):
      for c[3] in range (3):
        for c[4] in range (3):
          for c[5] in range (3):
            for c[6] in range (3):
              for c[7] in range (3):
                for c[8] in range (3):
                  countx = sum([1 for x in c if x == 1])
                  county = sum([1 for x in c if x == 2])
                  if abs(countx-county) < 2:
                    if won(c,1) + won(c,2) == 1:
                      print " %s | %s | %s" % (pc[c[0]],pc[c[1]],pc[c[2]])
                      print "---+---+---"
                      print " %s | %s | %s" % (pc[c[3]],pc[c[4]],pc[c[5]])
                      print "---+---+---"
                      print " %s | %s | %s" % (pc[c[6]],pc[c[7]],pc[c[8]])
                      print
```

As one commenter has pointed out, there is one more restriction. The winner for a given board cannot have less cells than the loser since that means the loser just moved, despite the fact the winner had already won on the last move.

I won't change the code to take that into account but it would be a simple matter of checking who has the most cells (the last person that moved) and ensuring the winning line belonged to them.

All Possible Tic Tac Toe Winning Combinations

Solution

Problem