# Determining the number of valid TicTacToe board states in terms of board dimension

I am attempting to find a closed form equation in terms of $n$, for the number of valid Tic-Tac-Toe board states (ignoring symmetry), where the board has dimension $n \times n ,\; 0 \lt n,\;n \in \Bbb Z$.

Tic-Tac-Toe Rules:

• The $X$ token moves first
• No player can abstain from moving
• The game ends when:

• All spaces are filled
• $n$ identical horizontal, vertical, or diagonal tokens exits

From these rules, how can we derive a closed form equation of the number of valid Tic-Tac-Toe board states when the board's dimension changes in terms of $n\,$?

Observations of small values of $n$:

$\;n = 1: 2\;$ valid board states (by enumeration)

[ ], [X]


$\;n = 2: 29\;$ valid board states (by enumeration)

[ ][ ]  [X][ ]  [ ][X]  [ ][ ]  [ ][ ]  [X][O]  [X][ ]  [X][ ]  [O][X]
[ ][ ], [ ][ ], [ ][ ], [X][ ], [ ][X], [ ][ ], [O][ ], [ ][O], [ ][ ],

[ ][X]  [ ][X]  [O][ ]  [ ][O]  [ ][ ]  [O][ ]  [ ][O]  [ ][ ]  [X][O]
[O][ ], [ ][O], [X][ ], [X][ ], [X][O], [ ][X], [ ][X], [O][X], [X][ ],

[X][O]  [X][X]  [X][ ]  [X][X]  [X][ ]  [O][X]  [O][X]  [ ][X]  [ ][X]
[ ][X], [O][ ], [O][X], [ ][O], [X][O], [X][ ], [ ][X], [O][X], [X][O],

[O][ ]  [ ][O]
[X][X], [X][X]


$\;n = 3: 255,168\;$ valid board states (by reference)

• Why hasn't this question got more attention? This is a really cool question :) Commented Aug 17, 2013 at 0:21
• @Ataraxia A cool question, but a hard one. Already the number of the 3x3 board states is counted by quite a complicated case analysis: see Henry Bottomley's or Steve Schaeffer's analyses. Commented Sep 11, 2013 at 16:28
• For a 2x2 board, I make it seven states (ignoring symmetry). Commented Oct 3, 2013 at 23:19
• oeis.org/A008907 also useful Commented Oct 4, 2013 at 12:04
• Most things in mathematics don't have closed forms; shape-oriented enumeration problems are particularly notorious for not having closed forms. A shape-oriented enumeration problem with a complex constraint (the 'gameplay' constraint) is virtually a lost cause for anything but manual enumeration. Commented May 30, 2014 at 18:50

Fun question.

I don't have enough karma to add this as a comment, so I'll offer it up as an answer, although it is (currently) an incomplete one.

The reference you link to for the $N=3$ case does not say that there are $255,168$ valid 3-by-3 tic-tac-toe boards, but that there are $255,168$ distinct 3-by-3 tic-tac-toe games.

That is, if you make a "game tree" where each (valid) board is a node and each move is an edge, you're asking how many nodes are in the tree. The Wikipedia article states that there are $255,168$ distinct paths through the tree (from the root to a leaf), but there are substantially fewer nodes. In fact we can set an upper bound on the number of distinct 3-by-3 tic-tac-toe boards by ignoring the rules of the game and noting that there are only $3^9$ ways to fill a 9x9 board with 3 tokens (blank, X and O), which is only $19,683$. And many of those have too many Xs or Os to be valid.

(The Wikipedia article is also taking symmetry into account, which if I understand you correctly, you want to ignore.)

I happen to be working on a program that generates this game tree for entirely different reasons.

The program may be buggy, so take the numbers above with a grain of salt, but it looks right to me on inspection. I believe I've seen other pages online that corroborate the $N=3$ case, but at the time I was only trying to validate that my program was working properly, so I didn't bother the record the link.

Currently my program runs out of memory (on my little netbook) when I try to generate the game tree for $N=4$, but I imagine that's fixable with a little bit beefier hardware and/or a little optimization of the program for memory footprint (currently I'm storing a lot of metadata about each board state).

Circumstances permitting, I'll try come back and update this answer with more information if and when I have some to share, but I wanted to put some hard numbers (and specific constraints) on the table because I think it clears up some of the confusion in the comment thread.

## Assumptions

To clarify the constraints on the problem, here's what I'm assuming:

1. We're interested in counting the number of valid "game states" on an $N$-by-$N$ tic-tac-toe board.
2. We're ignoring symmetry, so that a board with one X in the upper-left corner is considered a distinct board from the one with an X in the lower-right corner.
3. X always moves first.
4. The game stops with either player makes a horizontal, vertical or diagonal line of length $N$. Any boards that can only be reached by continuing to play after one of the players has made a line are considered invalid and ignored.
5. (The game also stops when we run out of free spaces to move, of course.)

## Some data based on enumeration

Under these constraints, as you wrote, we can confirm that:

• for $N=1$ there are $2$ valid and distinct boards
• for $N=2$ there are $29$ valid and distinct boards

Based on (programmatic) inspection, I think we can say that:

• for $N=3$ there are $5,478$ valid and distinct boards
• for $N=4$ there are $9,722,011$ valid and distinct boards

If you break these down by ply (turn):

      N:   1   2     3        4
-------   -  --  ----  -------
ply  0:   1   1     1        1
ply  1:   1   4     9       16
ply  2:   -  12    72      240
ply  3:   -  12   252     1680
ply  4:   -   0   756    10920
ply  5:   -   -  1260    43680
ply  6:   -   -  1520   160160
ply  7:   -   -  1140   400400
ply  8:   -   -   390   895950
ply  9:   -   -    78  1433520
ply 10:   -   -     -  1962576
ply 11:   -   -     -  1962576
ply 12:   -   -     -  1543080
ply 13:   -   -     -   881760
ply 14:   -   -     -   333792
ply 15:   -   -     -    83440
ply 16:   -   -     -     8220
=======   =  ==  ====  =======
TOTAL:   2  29  5478  9722011
-------


I don't see an obvious formula for the sequence $(2,29,5478,9722011,...)$, but a few interesting (IMO) observations about this:

• $N=3$ is the smallest board for which player O can win

• $N=3$ is the smallest board that can end in a tie game

• $N=2$ is likely the only board that cannot be filled (X is guaranteed to win on the third move, leaving one slot unfilled)

• Both of the even examples have two plies in a row with the exactly same number of boards (for $N=2$ plies 2 and 3 have $12$ boards and for $N=4$ plies 10 and 11 have $1,962,576$). These are also the "widest" plies in their respective trees. (The same is true for $N=1$, but I imagine that's a degenerate case.)

• (This didn't hold for $N=4$.) It may just be the law of small numbers, but I notice that the "widest" tier of the game tree is the one where there are $N$ empty spaces left on the board. For $N=1$, this is ply 0 with $1$ board, for $N=2$ this is ply 2 with $12$ boards and for $N=3$ this is ply 6, with $1,520$ boards.

• and of course, at $N=1$, player O doesn't even get to move.

## Looking at upper bounds

By the way, as a very rough sanity check, I compared the number of valid boards with $3^{(N^2)}$ (the number of distinct ways to fill an $N\times{}N$ board with 3 symbols):

       N:   1     2        3          4
-------- ----  ----  -------  ----------
# Valid:  2    29     5478     9722011
3^(N^2):  3    81    19683    43046721
% Valid: 66.7  35.8     27.8        22.6


We can get a tighter upper bound if we look at the number of ways to fill an $N\times{}N$ board with $count(X) = count(O)$ or $count(X) = count(O)+1$.

That's actually not the hard to figure out if you change your thinking a little bit. Instead of alternating between X and O, imagine you put down all the Xs first, then all the Os.

• On the zeroth ply, there are no Xs or Os, so we always have 1 board. (Note that this is $N^2$ choose $0$, written ${{N^2} \choose 0}$).

• On the first ply, there is exactly one X, so we have ${{N^2} \choose 1}$ distinct boards.

• On the second ply, there is exactly one X and exactly one O, so we have ${{N^2} \choose 1} \times {((N^2)-1) \choose 1}$ boards.

• On the third ply, there are two Xs and one O, so we have ${{N^2} \choose 2} \times {{((N^2)-2)} \choose 1}$ boards.

• On the fourth ply, there are two Xs and two Os, so we have ${{N^2} \choose 2} \times {{((N^2)-2)} \choose 2}$ boards.

And so on.

### In the general case

Note that on ply $p$ there will be $floor({{(p+1)}\over{2}})$ Xs and $floor({{p}\over{2}})$ Os on the board, so let's say:

• $x = floor({{(p+1)}\over{2}})$

and

• $o = floor({{p}\over{2}})$

Note that:

• There are ${{N^2} \choose x}$ ways to place $x$ X marks on an $N\times{}N$ board.

• There are ${{N^2 - x} \choose o}$ ways to place $o$ O marks on an $N\times{}N$ board that is already filled with $x$ Xs.

Hence ignoring winners there are:

${{N^2} \choose x} \times {{N^2 - x} \choose o}$

distinct boards at ply $p$. Or (plugging the definitions of $x$ and $o$ from above):

${{N^2} \choose {floor({{p+1}\over{2}})}} \times {{N^2 - {floor({{p+1}\over{2}})}} \choose {floor({p \over 2})}}$

So an upper bound on the number of distinct boards would the be summation of that ugly formula over $p = 0$ to $p = N^2$.

I imagine that the clever application of algebra could dramatically simplify that expression (especially when you plug the definition of $n \choose k$ in for the choose notation).

To get an even better count we could take into account the winning boards.

• I calculate 5427 unique boards. Could you possibly send me a list of your 5477 unique boards so I can compare? I get 1,9,72,252,756,1254,1516,1112,382,74. Even the list of 78 full boards would be helpful.
– DCR
Commented May 5, 2022 at 0:05
• Just for the sake of future readers that come across this comment, RSS and I corresponded over email and came to the conclusion that 5478 does appear to be the correct count (of valid 3x3 tic tac toe boards ignoring symmetry).
– Rod
Commented May 6, 2022 at 0:49
• ...one observation that corroborates that BTW is that after the 5th move (the first difference between our counts) there are (9 choose 3) X (6 choose 2) = 84 X 15 = 1260 unique boards (matching the answer above) by the same logic as described toward the end of the answer. In a nutshell: after move 5 there will be 3 Xs and 2 Os on the board, imagine putting them down all at once instead of taking turns. That gives (9 choose 3) ways to place the Xs and (6 choose 2) ways to place the Os in the spaces that are left.
– Rod
Commented May 6, 2022 at 0:54
• Those 5478 is the number when it is always 'X' doing the first move or does it include also the 'O' first case? Commented Jun 3, 2023 at 0:11
• @BitTickler my model assumes that X always makes the first move (assumption #3). If you want to include cases where O makes the first move I think (1) every odd ply would yield another set of unique boards (since the # of Xs and Os would be different) and (2) the even plies would not yield any additional unique boards (since the number of Xs and Os would be the same. E.g., for n=2 I think you'd have 16 additional boards (+4 from ply 1 and +12 from ply 3).
– Rod
Commented Jun 11, 2023 at 1:54

just in case someone wants to calculate the 5478 boards here's a java program. I will eventually rewrite it using recursion. the valid boards are contained in the ArrayList bds and can be printed out after the last loop

import java.util.ArrayList;

public class Boards{
private ArrayList<int[]> bds = new ArrayList<int[]>();
int loops = 9;
private int[][] moves = new int[loops][loops];
private int cnt = 0;
private boolean player1Moves = true;
boolean gameOver = false;
int[] sum = new int[10];

public static void main(String[] args){
System.out.println("\f");
Boards game = new Boards();
game.count();

}

public void count(){
sum[0] = 1;

for (int i = 0; i < loops; i++){
int[] element = new int[loops+1];
for(int j = 0; j < loops; j++){
moves[0][j] = 0;
}
moves[0][i] = 1;
player1Moves = true;
element[loops] = 10;
cnt++;

int[] idx1 = new int[loops];
for(int i1 = 0; i1 < loops - 1 ; i1++){
element = new int[loops+1];
for(int j = 0; j < loops; j++){
moves[1][j] = moves[0][j];
}

for(int k = 0; k < loops; k++){
if(moves[1][k] == 0 && idx1[k] != 100){
moves[1][k] = -1;
player1Moves = false;
idx1[k] = 100;
break;
}
}
element[9] = -10;
cnt++;

int[] idx2 = new int[loops];
for(int i2 = 0; i2 < loops - 2; i2++){
element = new int[loops+1];
for(int j = 0; j < loops; j++){
moves[2][j] = moves[1][j];
}

for(int k1 = 0; k1 < loops; k1++){
if(moves[2][k1] == 0 && idx2[k1] != 100){
moves[2][k1] = 1;
player1Moves = true;
idx2[k1] = 100;
break;
}
}
element[9] = 10;
cnt++;

int[] idx3 = new int[loops];
for(int i3 = 0; i3 < loops - 3; i3++){
element = new int[loops+1];
for(int j = 0; j < loops; j++){
moves[3][j] = moves[2][j];
}
for(int k2 = 0; k2 < loops; k2++){
if(moves[3][k2] == 0 && idx3[k2] != 100){
moves[3][k2] = -1;
player1Moves = false;
idx3[k2] = 100;
break;
}
}
element[9] = -10;
cnt++;

int[] idx4 = new int[loops];
for(int i4 = 0; i4 < loops - 4; i4++){
player1Moves = false;
gameOver(moves[3]);
if(gameOver){
gameOver = false;
break;
}
element = new int[loops+1];
for(int j = 0; j < loops; j++){
moves[4][j] = moves[3][j];
}
for(int k3 = 0; k3 <= loops; k3++){
if(moves[4][k3] == 0 && idx4[k3] != 100){
moves[4][k3] = 1;
player1Moves = true;
idx4[k3] = 100;
break;
}
}
element[9] = 10;
cnt++;

int[] idx5 = new int[loops];
for(int i5 = 0; i5 < loops - 5; i5++){
player1Moves = true;
gameOver(moves[4]);
if(gameOver){
gameOver = false;
break;
}
element = new int[loops+1];
for(int j = 0; j < loops; j++){
moves[5][j] = moves[4][j];
}
for(int k4 = 0; k4 < loops; k4++){
if(moves[5][k4] == 0 && idx5[k4] != 100){
moves[5][k4] = -1;
player1Moves = false;
idx5[k4] = 100;
break;
}
}
element[9] = -10;
cnt++;

int[] idx6 = new int[loops];
for(int i6 = 0; i6 < loops - 6; i6++){
player1Moves = false;
gameOver(moves[5]);
if(gameOver){
gameOver = false;
break;
}
element = new int[loops+1];
for(int j = 0; j < loops; j++){
moves[6][j] = moves[5][j];
}
for(int k5 = 0; k5 < loops; k5++){
if(moves[6][k5] == 0 && idx6[k5] != 100){
moves[6][k5] = 1;
player1Moves = true;
idx6[k5] = 100;
break;
}
}
element[9] = 10;
cnt++;

int[] idx7 = new int[loops];
for(int i7 = 0; i7 < loops - 7; i7++){
player1Moves = true;
gameOver(moves[6]);
if(gameOver){
gameOver = false;
break;
}
element = new int[loops+1];
for(int j = 0; j < loops; j++){
moves[7][j] = moves[6][j];
}
for(int k6 = 0; k6 < loops; k6++){
if(moves[7][k6] == 0 && idx7[k6] != 100){
moves[7][k6] = -1;
player1Moves = false;
idx7[k6] = 100;
break;
}
}
element[9] = -10;
cnt++;

int[] idx8 = new int[loops];
for(int i8 = 0; i8 < loops - 8; i8++){
player1Moves = false;
gameOver(moves[7]);
if(gameOver){
gameOver = false;
break;
}
element = new int[loops+1];
for(int j = 0; j < loops; j++){
moves[8][j] = moves[7][j];
}
for(int k7 = 0; k7 < loops; k7++){
if(moves[8][k7] == 0 && idx8[k7] != 100){
moves[8][k7] = 1;
player1Moves = true;
idx8[k7] = 100;
break;
}
}
element[9] = 10;
cnt++;
}
}
}
}
}
}
}
}
}

System.out.println("cnt = " + cnt);
System.out.println("bds = " + (bds.size() + 1));
for (int i = 0; i < 10; i++)System.out.println(sum[i]);
}

public void copyAdd(int[] element, int level){
for (int i = 0; i < loops; i++){
element[i] = moves[level][i];
}

}

public void myPrint(int[] item){
System.out.print(cnt + "      ");

for (int i = 0; i < item.length; i++){
System.out.print(item[i] + "  ");
}

System.out.println();

}

boolean[] in = new boolean[bds.size()];
boolean duplicate = false;;

for (int i = 0; i < bds.size(); i++){
in[i] = true;
for (int j = 0; j < loops ; j++){

if(element[j] != bds.get(i)[j]){
in[i] = false;
break;
}
}
}
for (int i = 0; i < bds.size(); i++){
if (in[i]){
duplicate = true;
//System.out.println("Duplicate " + cnt);
break;
}
}
if(!duplicate){
sum[level]++;
}
}

public int  score(int[] board){
/*
* compute the score of the board using an array (moves[])
*/

int idx = 0;
int [] scores = new int[] {0,0,0,0,0,0,0,0};
int currentScore = 0;

//score rows (horizontal) and columns (vertical)
for (int i = 0; i < 3; i++){
for (int j = 0; j < 3; j++){
idx = j + (i * 3);
scores[i] = scores[i] + board[idx];
idx = i + (j * 3);
scores[i+3] = scores[i+3] + board[idx];
}
}

//score diagonals
for (int m = 0; m < 2; m++){
for (int i = 0 ; i < 3; i++){
scores[6+m] = scores[6 + m] + board[4 * i - 6 * m * (i - 1)];
}
}

if(player1Moves){//maximizing get highest score
currentScore = -100;
for (int i = 0; i < 8; i++){
if(scores[i]  > currentScore) currentScore = scores[i] ;
}
}else{ // minimizing get lowest score
currentScore = 100;
for (int i = 0; i < 8; i++){
if(scores[i]  < currentScore) currentScore = scores[i] ;
}
}

return currentScore;
}

public boolean gameWon(int[] board){
/*
* check if game is won
*/
boolean gameWon;
int score = score(board);

gameWon = (Math.abs(score) == 3) ? true : false;

return gameWon;
}

public void gameOver(int[] board){
/*
* check if game is over         */

int score = score(board);
int zeroCnt = 0;
//check for empty (0) squares
for(int i = 0; i < 9; i++){
if (board[i] == 0){
zeroCnt++;
break;
}
}
//game is over if game won or no empty squares
gameOver = (gameWon(board)) ? true : (zeroCnt == 0) ? true : false;

// or

if (gameWon(board) || zeroCnt == 0) gameOver = true;
else gameOver = false;

}

}


My mathematics isn't very good but I am very good at programming. I am also interested in the issue and I have investigated it but found a different number. The number is 8533.

I didn't account for reflections and rotations.

There are $$3^9=19683$$ possible permutations of 3 symbols, ignoring the game's rules, a lot of them cannot be reached in real playing.

A board is legal if there are no two winners, and the difference between moves of the two players is less than or equal to one. Because if there is already a winner, the game ends, and the players take turns place pieces, after one player moves the other must make a move, the same player cannot move in two consecutive turns.

Here is the Python code I used:

from itertools import product
from pathlib import Path

LINES = (
(0, 3, 1),
(3, 6, 1),
(6, 9, 1),
(0, 7, 3),
(1, 8, 3),
(2, 9, 3),
(0, 9, 4),
(2, 7, 2),
)

def is_valid(board):
winners = set()
winner = None
for start, stop, step in LINES:
line = board[start:stop:step]
if len(set(line)) == 1 and (winner := line[0]) in {"O", "X"}:

return (
len(winners) <= 1
and abs(board.count("O") - board.count("X")) <= 1
and (not winner or board.count(winner) >= board.count("OX".replace(winner, "")))
)

VALID_BOARDS = [board for board in product(" OX", repeat=9) if is_valid(board)]

def repr_board(board, indent):
return (
"\t" * indent
+ "[\n"
+ ",\n".join("\t" * (indent + 1) + repr(board[i : i + 3]) for i in (0, 3, 6))
+ "\n"
+ "\t" * indent
+ "]"
)

Path("D:/tic-tac-toe-boards.txt").write_text(
"[\n" + ",\n".join(repr_board(board, 1) for board in VALID_BOARDS) + "\n]"
)


Previously the number was calculated to be 8725, that was wrong, because it included 192 states impossible to be reached, more specifically the states are post-game states, if the rules are followed, there would already be a winner and the game would end. But the count of the moves of the loser is one greater than the winner's, indicating the game didn't end after the winner is determined.

I have fixed that error and I have verified its correctness. I have programmatically generated all possible legal board states one by one, and counted the number of wins and ties followed from the state for each move. I have calculated the case where the player moves first and second, for both cases the number of reachable states is 5478, the total number of unique states (with reflections and rotations) is 8533.

I disagree with some of the results in the N=3 column in the table above.
I agree with the values cited for up through ply 5.
But from that point on:
ply:      table value:       my value:
6           1520               1680
7           1140               1260
8            390                630
9             78                126
total for 9 plys:
5478               6046
Basis: formula for N things taken R at a time  N! /(R! x (N-R)!
EX: Ply 7:   N = 9, R = 4 for X  9! / (4!)(9-4)! = 126
N = 5, R = 3 for O  5! / (3!)(5-3)! = 10
126 x 10 = 1260

• This should really be a comment to Rod's answer, but it is too long. A disclaimer to that fact at the outset would be good.
– robjohn
Commented Jul 29, 2014 at 16:59
• Thanks Norman. It's been a while since I looked at this, but if I'm reading your comment correctly I think the difference in our numbers may be explained by assumption #4 in my list ("The game stops with either player makes a horizontal, vertical or diagonal line of length N. Any boards that can only be reached by continuing to play after one of the players has made a line are considered invalid and ignored."). The N! /(R! x (N-R)!) formula allows boards that are invalid according to that assumption.
– Rod
Commented May 7, 2015 at 12:00