Generate a list of all unique Tic Tac Toe boards

Question

I would like to generate a text file containing all 19,683 Tic-Tac-Toe board layouts in the structure of 0 = Blank, 1 = X, and 2 = O. Unfortunately math is not my strong suit and I cannot seem to find any examples of this anywhere.

This isn't for homework I assure you. I intend to run this data through a Minimax calculator in order to generate an image that contains RGB values representing the optimal move based on the board setup. I am developing Tic-Tac-Toe for a platform that does not support functions (it's event-driven) so I will convert the board to a number in my game and then lookup the RGB of a pixel in an image which indicates what the best move is. It's a cheeky workaround, but one that requires no more RAM than an 145x145 pixel image (145x145 = 21,025 so each pixel represents the recommended move based on the board effectively). This also means I won't have to chew CPU time which is another plus.

Answer 1

Since you want board layouts, there's only a small number of them (19683).

You can just brute-force generate all of these. Each box only has 3 possibilities. And there are 9 boxes, just run through all of them.

EDIT:

int c = 0;
while (c < 262144){
    bool valid = (c & 3) < 3;
    valid &= ((c >>  2) & 3) < 3;
    valid &= ((c >>  4) & 3) < 3;
    valid &= ((c >>  6) & 3) < 3;
    valid &= ((c >>  8) & 3) < 3;
    valid &= ((c >> 10) & 3) < 3;
    valid &= ((c >> 12) & 3) < 3;
    valid &= ((c >> 14) & 3) < 3;
    valid &= ((c >> 16) & 3) < 3;

    if (valid){
        int i = c;
        int j = 0;
        while (j < 9){
            cout << (i & 3) << " ";
            i >>= 2;
            j++;
        }
        cout << endl;
    }

    c++;
}

This will print out all 19,683 board layouts. I'm not sure what format you want, but it should be fairly easy to extract that from the output.

Answer 2

The total possible moves is not 3^9 as it includes many non allowed move in Tic Tac Toe. (X's - O's) or (O's - X's) must be equal to 1 always. As https://stackoverflow.com/a/25358690/13557570 mentions the total possible moves are 5477

Python code using numpy with states reduced to 5814:

import numpy as np
StatesMatrix = np.zeros((3**9,9))
for i in range(3**9):
     c = i
     for j in range(9):
       StatesMatrix[i][j] = c % 3
       c //= 3
StatesMatrix1 = np.zeros((5814,9))
k = 0
for i in range(0,StatesMatrix.shape[0]):
  if (np. count_nonzero(StatesMatrix[i] == 1) - np. count_nonzero(StatesMatrix[i] == 2)) == 1 or (np. count_nonzero(StatesMatrix[i] == 2) - np. count_nonzero(StatesMatrix[i] == 1))== 1:
    StatesMatrix1[k] = StatesMatrix[i]
    k = k + 1
    
print(StatesMatrix1)
print(k)