Programming Puzzle: Tic-Tac-Toe Keychain

9 min readFeb 26, 2024

I was recently nerd-sniped by the Tic-Tac-Toe keychain pictured below. It’s a simple toy that has a 3-by-3 grid of spinners where each can be in one of three states: empty, “X,” and “O.”

Figure 1. The latest inanimate object to nerd-snipe me.

I know Tic-Tac-Toe is a solved game, but my simple question was, if you randomly spin all the pieces on this keychain, what are the odds that the board you get is a legal position? As seen in Figure 2, you could spin all empties, all “X”s, or all “O”s, but only one of these positions is legal:

Figure 2. Some legal and illegal positions in Tic-Tac-Toe Keychain.

The answer will be a good exercise in basic search strategies.

High-Level Approach

The Tic-Tac-Toe game has nine spaces, each of which has an equal chance of being one of either three outcomes, which means there are 3⁹ or 19,683 possible boards. This is a very small number from a computational perspective, meaning we should be able to use any approach — including exhaustive search — to find the solution.

The first approach we’ll program is depth-first search. Starting from a blank board, we’ll try out all possible moves for “X,” then try out all possible moves for “O,” and stop whenever the game reaches a terminal state. This way we’ll never be able to get to an invalid state, and the total number of states we reach will give us our answer.

Approach #1: Exhaustive Search

We’ll represent the board state with a simple 2D array with single string characters and use a convenience method board2str to convert it to a string:

def board2str(board):
  return '\n'.join(''.join(_) for _ in board)

board = [['.'] * 3, ['.'] * 3, ['.'] * 3]
print(board2str(board))
# ...
# ...
# ...

board[1][1] = 'x'
board[2][2] = 'o'
print(board2str(board))
# ...
# .x.
# ..o

We’ll use DFS to do our exhaustive search, which calls for a code skeleton like this:

def dfs(board, valids):
  valids.append([row.copy() for row in board])
  if not is_final_state(board):
    for next_board in next_states(board):
      dfs(next_board, valids)

It doesn’t matter whether we use DFS or BFS since we’re not looking for the shortest path (for which BFS is designed), nor do we care about limiting memory consumption (for which DFS does better). We will also save all states we see on the way to get a full count of the legal positions.

Checking Final State

To implement the is_final_state function, we need to check whether the game has been won or whether every space has been filled:

def is_final_state(board):
  if sum(board[r][c] != '.' for r in range(3) for c in range(3)) == 9:
    # All spaces filled.
    return True

  for win in ('x', 'o'):
    # Check wins along a row.
    for r in range(3):
      if all(piece == win for piece in board[r]):
        return True

    # Check wins along a column.
    for c in range(3):
      if all(board[r][c] == win for r in range(3)):
        return True

    # Check diagonals.
    if board[0][0] == win and board[1][1] == win and board[2][2] == win:
      return True
    if board[0][2] == win and board[1][1] == win and board[2][0] == win:
      return True

  return False

print(is_final_state([
  list('...'),
  list('.x.'),
  list('..o'),
]))
# False
print(is_final_state([
  list('..x'),
  list('..x'),
  list('..x'),
]))
# True
print(is_final_state([
  list('o.x'),
  list('.ox'),
  list('..o'),
]))
# True
print(is_final_state([
  list('xoo'),
  list('oxx'),
  list('xxo'),
]))
# True

Getting Next States

And then the next_states function:

def next_states(board):
  next_piece = 'x' if sum(board[r][c] != '.' for r in range(3) for c in range(3)) % 2 == 0 else 'o'
  for r in range(3):
    for c in range(3):
      if board[r][c] == '.':
        next_board = [row.copy() for row in board]
        next_board[r][c] = next_piece
        yield next_board

for next_board in next_states([
  list('o.x'),
  list('.ox'),
  list('...'),
]):
  print('\n' + board2str(next_board))

# oxx
# .ox
# ...

# o.x
# xox
# ...

# o.x
# .ox
# x..

# o.x
# .ox
# .x.

# o.x
# .ox
# ..x

You might have noticed that programming the game mechanics has taken around 30 lines of code while programming the DFS has taken only 5. This is typical of algorithms problems where the ultimate approach is simple (like DFS) but the problem requires much more special handling of its state and mechanics. This skew is even worse in, say, machine learning, where the core algorithm may only be 5 lines of PyTorch but readying the data to feed into the algorithm takes 300 lines.

Initial Run

Finally we are ready to run our function. I will also use import time to time its execution since I expect it to be very fast:

def dfs(board, valids):
  valids.append([row.copy() for row in board])
  if not is_final_state(board):
    for next_board in next_states(board):
      dfs(next_board, valids)

import time

valids = []
start_time = time.time()
dfs([['.'] * 3 for _ in range(3)], valids)
stop_time = time.time()
print('Num valids:', len(valids), 'took:', stop_time - start_time, 's')
# Num valids: 549946 took: 5.579200983047485 s

One, this took way too long — 5.6 seconds on a MacBook — and two, it’s wrong, since 549,946 >> 3⁹.

The problem turns out to be that we’re counting duplicated versions of states. Consider the scenario outlined below in Figure 3:

Figure 3. Two ways to arrive at a duplicate state: (a) [(0,0->’x’), (0,1->’o’), (0,2->’x’)]; and (b) [(0,2->’x’), (0,1->’o’), (0,0->’x’)].

A simple fix for this would be to turn valids into a set to only save (and continue to examine) board states that we haven’t seen before:

def dfs2(board, valids):
  board_str = board2str(board)
  if board_str not in valids:
    valids.add(board_str)
    if not is_final_state(board):
      for next_board in next_states(board):
        dfs2(next_board, valids)

import time

valids = set()
start_time = time.time()
dfs2([['.'] * 3 for _ in range(3)], valids)
stop_time = time.time()
print('Num valids:', len(valids), 'took:', stop_time - start_time, 's')
# Num valids: 5478 took: 0.10553789138793945 s

This took only 0.1 seconds — that’s more like it — and now we get 5,478 valid states. This seems correct as it’s only 27.83% of the total 19,683 possible boards, meaning if you spin a random position you have about a 1 in 4 chance of it being a valid board. But the bug we encountered in implementing Tic-Tac-Toe — the simplest of all games — convinces me to try another solution to cross-check.

Approach #2: Filtering

Our first approach used the rules of the game to simulate all legal moves, but a dual approach would be to generate every possible board state and then check whether it’s legal or not. Instead of using the rules of Tic-Tac-Toe to guide the search, we’ll use brute force to generate all solutions and only apply the rules as a check:

Generate All Boards

The approach we’ll use to generate all boards is to recursively build up an array nine elements long. Each invocation of the recursive function will be responsible for filling in all possible values of another position. At the end when we’ve filled up all nine positions, we’ll check if the position is valid before saving it to our list of solutions.

Figure 4. DFS strategy for generating all possible boards.

def dfs3(cells, valids):
  if len(cells) == 9:
    board = [cells[:3], cells[3:6], cells[6:]]
    if is_valid(board):
      valids.append([row.copy() for row in board])
  else:
    dfs3(cells + ['.'], valids)
    dfs3(cells + ['x'], valids)
    dfs3(cells + ['o'], valids)

valids_exhaustive = []
dfs3([], valids_exhaustive)
print('Valids:', len(valids_exhaustive))

Now we have to implement the is_valid check. If we start out with is_valid = lambda b: True, it should just count the number of all possible boards:

def is_valid(board):
  return True

valids_exhaustive = []
dfs3([], valids_exhaustive)
print('Valids:', len(valids_exhaustive))
# Valids: 19683

So far so good. Now let’s screen out boards which have an invalid number of X’s and O’s, since there can only ever be one more X than the number of Os:

def is_valid(board):
  num_xs = sum(sum(_ == 'x' for _ in row) for row in board)
  num_os = sum(sum(_ == 'o' for _ in row) for row in board)

  if (num_xs - num_os) not in (0, 1):
    return False

  return True

valids_xo = []
dfs3([], valids_xo)
print('X-O count valids:', len(valids_xo))
# X-O count valids: 6046

Now we need a function to check if someone has won, and it will return all the positions in the board that constitute their winning position:

def check_wins(board, win):
  win_positions = set()

  # Check wins along a row.
  for r in range(3):
    if all(piece == win for piece in board[r]):
      win_positions.update([(r, c) for c in range(3)])

  # Check wins along a column.
  for c in range(3):
    if all(board[r][c] == win for r in range(3)):
      win_positions.update([(r, c) for r in range(3)])

  # Check diagonals.
  if board[0][0] == win and board[1][1] == win and board[2][2] == win:
    win_positions.update([(0, 0), (1, 1), (2, 2)])
  if board[0][2] == win and board[1][1] == win and board[2][0] == win:
    win_positions.update([(0, 2), (1, 1), (2, 0)])

  return win_positions

def is_valid(board):
  num_xs = sum(sum(_ == 'x' for _ in row) for row in board)
  num_os = sum(sum(_ == 'o' for _ in row) for row in board)

  if (num_xs - num_os) not in (0, 1):
    return False

  x_wins = check_wins(board, 'x')
  o_wins = check_wins(board, 'o')
  if x_wins and o_wins:
    return False

  return True

valids_xo_double_win = []
dfs3([], valids_xo_double_win)
print('X-O count, no double wins valids:', len(valids_xo_double_win))
# X-O count, no double wins valids: 5890

By checking that both X and O can’t win at the same time, we’re down to 5,890 valid states —still higher than 5,478. To figure out what’s wrong, we can subtract our previous set of valids boards from valids_xo_double_win to see what we’re still counting as legal boards:

print(set(map(board2str, valids_xo_double_win)) - valids)
# {'xxo\nxoo\nxo.', 'oxx\noxx\no..', 'oxo\n.x.\n.xo', '.x.\nox.\noxo', 
# 'x.x\nooo\nxx.', '..o\nxxx\noo.', 'oo.\no..\nxxx', 'ooo\nxx.\n.xx',
# 'oox\noxo\nxx.', 'xxx\noo.\no..', '.ox\noxo\nx..', 'oox\noox\nx.x',
# '.xo\nxxo\nx.o', 'xoo\nx.o\nx..', 'oox\n.xx\nxoo', 'o.x\n.xo\nx.o', ...

Illustrating a few of these cases in Figure 5, we can see the problem in (5.a) is that X has won but with the same number of moves as O—impossible. The same is true in (5.c), and in (5.b) O has won with fewer moves than X.

Figure 5. Some illegal positions we haven’t filtered out yet.

We can adjust our filtering function to apply this extra constraint when the board state is won:

def is_valid(board):
  num_xs = sum(sum(_ == 'x' for _ in row) for row in board)
  num_os = sum(sum(_ == 'o' for _ in row) for row in board)

  if (num_xs - num_os) not in (0, 1):
    return False

  x_wins = check_wins(board, 'x')
  o_wins = check_wins(board, 'o')
  if x_wins and o_wins:
    return False
  if x_wins and num_xs != num_os + 1:
    return False
  if o_wins and num_xs != num_os:
    return False

  return True

valids_xo_fixed_win = []
dfs3([], valids_xo_fixed_win)
print('X-O count, fixed win valids:', len(valids_xo_fixed_win))
# X-O count, fixed win valids: 5478

And we’ve finally achieved the number we sought: 5,478.

Approach #3: Counting and Filtering

A final approach will be to use counting to enumerate all boards and then apply the same filtering approach. Since each board is composed of nine ternary values, we can count from 0 to 3⁹, convert each number to ternary, and then interpret the digit values 0 as empty, 1 as “X”, and 2 as “O” to convert it to a board. For example, the ternary number 021010012 could be converted to the string ".ox.x..xo", which represents a board:

def pos2board(pos):
  c = lambda c: 'x' if c == 1 else ('o' if c == 2 else '.')
  return [
    [c(pos[0]), c(pos[1]), c(pos[2])],
    [c(pos[3]), c(pos[4]), c(pos[5])],
    [c(pos[6]), c(pos[7]), c(pos[8])],
  ]

print(board2str(pos2board([0, 2, 1, 0, 1, 0, 0, 1, 2])))
# .ox
# .x.
# .xo

To generate all possible 9-digit ternary numbers, we just need to count from 0 to 3⁹ and convert the number from decimal to ternary:

valid_counting = set()
for i in range(3 ** 9):
  pos = []
  v = i
  for j in range(9):
    pos.append(i % 3)
    i = i // 3

  board = pos2board(pos)
  if is_valid(board):
    valid_counting.add(board2str(board))

print('Counting valids:', len(valid_counting))
# Counting valids: 5478

And with that we have double-verified our number of 5,478 valid states. We can rest reasonably assured that the odds of any random Tic-Tac-Toe Keychain position being legal are about 27.83%.

Unless otherwise noted, all images by the author.