My ultimate goal is determine whether the game Pentago is a first player win. But I need to start by getting my computational ducks in line. So, lets examine an old standby.
Let's examine the possible 3by3 TicTacToe boards.
T = [1 2 3;
4 5 6;
7 8 9]
If we label the squares from left to right, top to bottom, then each possible game can be represented by a sequence of the numbers from 1 to $n^2$, where none of the numbers is repeated. This follows from the fact that each play consists of marking a square that has not yet been marked. An upper bound on the number of possible games is the size of the set of all permutations of the $n^2$ numbers, that is, $n^2$ factorial.
What are these upper bounds for the $n=2$, $3$, $4$, and $6$ TicTacToe games?
Which of these these bounds are strictly larger than the actual number of possible games and why?

For $n$ greater than 2, the numbers, $(n^2)!$, overestimate the number of games because if a game ends in $k$ moves, then that game is the initial sequence of $(n^2k)!$ permutations. None of those permutations will be examined further.
Note that for $n=2$, $4!$ is exactly the number of games. White always wins in 3 moves, and Black would only have one square to play if the game were not already over.
Now consider a program that, given $n$, will play all $(n^2)!$ "games". It will not check for wins, but it will simply count the number of "games" (complete sequences) that were generated and print the final count.

Here are the intermediate results, when we run the program for the $n=2$ case.

Here is the time and the count for running the program for the $n=3$ case.

A very rough estimate for how long the $n=4$ case might take would be to multiply the time for the $n=3$ case by the ratio of $(4^2)! / (3^2)!$.
However, this is may be a significant overestimate since tails that get ignored when a game ends are probably a lot larger than for the $n=3$ case.

How much does it help to check for wins? One way to calculate a win is to examine all the rows, columns, and diagonals after every move. However, a more succinct approach is to keep an array corresponding to each of the possible wins, which will be $2n+2$ for an $n$by$n$ board. This give rise to the following code.


We can modify the TTT01 function so that it checks for a win on each move and keeps track of how many wins at each level.

Here are the intermediate results for the $n=2$ case.

Here's the main results and the time for the $n=3$.

The total number of games for $n=3$ is 255,168 out of the $9! =$ 362,880 possible sequences. We can reduce the previous time estimates by that fraction, although the correct fraction is probably smaller.
Unfortunately the code to check for a win makes the program run longer.

Notice that the game that starts [1,2,5] is a different game from the game that starts [5,2,1]. However the boards at this point are identical. Since we can label each square as 0 if it is empty, 1 if it is marked White, and 2 if it is marked Black, we can generate a unique number for each board. For example, if White has marked squares 1 and 5 while Black has marked square 2, then we can count base 3 and give this board the id $(1\cdot 3^{(11)} + 2\cdot 3^{(21)} + 1\cdot 3^{(51)})= 88$.
With this approach it is easy to see that there is a onetoone correspondence between the numbers
from 0 to $(2 \cdot 3^0 + 2 \cdot 3^1 + \cdots + 2 \cdot 3^{(n^21)})$ and the distinct $n$by$n$ boards.
It follows that an upper bound for the total number of distinct boards is simply $3^{n^2}$.
What are these upper bounds for the $n=2$, $3$, $4$, and $5$ TicTacToe boards?

Although this approach includes every board that can occur in a legitimate game, it also includes boards which can not occur such as a board where all the squares are marked white. Another illegitimate board would be one where both white and black have a win.
Note that for $n=2$ the number of possible boards is larger than the number of possible games, but for larger values of $n$ the number of possible boards is orders of magnitude less that the number of possible games.

We can reduce the number of boards even more by taking into account the group of symmetries.
Sage makes this step very easy.
Recall our labeling of the 3by3 TicTacToe board.
T = [1 2 3;
4 5 6;
7 8 9]








The following function is needed for automatically generating variables.

Now we have the tools to automatically build the cycle index polynomial.







Now we can write a little routine that isolates the coefficients for the Legitimate Nonequivalent Boards.

The action of a permutation group on a function whose domain is N is defined by performing the group operations and then applying the function.
a*b*f ::= f(a*b)
In other words, the operations are evaluated from left to right, including the final operation which is the evaluation of the function.

Let's quickly verify the actions of the group of symmetries.

The dictionary data structure encourages us to find a key for each board and then record properties for that board.

Another quick verification.

Now we introduce the symmetries by using as the id for each board, the smallest number of all the equivalent boards.

Another quick check.

And yet another quick check.

We can now investigate all the possible nonequivalent TicTacToe games.

Now let's run the program and display the list of the boards that are generated and the number of times each one is encountered for the $n=2$ case.


Let's run the program for the $n=3$ case and time it.


Let's examine the possible 4by4 Tritego boards.
T = [ 1 2 3 4;
5 6 7 8;
9 10 11 12;
13 14 15 16]










At this point we can essentially duplicate the recursive search.
However, we now need to modify both the move command because it must also allow the 8 rotations.
In addition the win_check routine needs to be modified, since we now include 3 in a row on the 4b4 board as well as the possibility of a twowin draw.
