Tic-tac-toe: 362,880 ways to fill a grid, and only 23 boards that matter.

The game of tic-tac-toe is well known and has been played for ages. It's a very simple game — the first person to get three in a row wins. But have you ever thought about the math underlying it? That's what we explore in our story #18.

Combinatorial game theory is used to analyse the possible outcomes of tic-tac-toe.

A tic-tac-toe board is a 3 × 3 grid. If we were to fill each of the nine spaces with a unique value (1 to 9), we would have nine choices for the first slot, eight for the second, and so on. Counting this way, there are 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 9! = 362,880 ways to fill the board.

But in tic-tac-toe we fill the board with X, O, or leave it blank. So the total number of ways to fill the grid is 3⁹ = 19,683 — every square is either an X, an O, or empty.

The number of different ways of filling the grid with five Xs and four Os is 9 choose 5 = 126. So we get 126 full boards for the game.

Wait, that's not it. Among those 126 boards, there are many that are the same when rotated or reflected. Take those symmetries into account and there are just 23 unique boards which, when rotated and reflected, give us all 126.

Uff — so much math to get us 23 unique boards, isn't it?