There are a couple of approaches you can take.
One is to reduce things by a dimension: There are 233 possible tuples for a row of 5, instead of 243, if I read your constraints correctly. You can now loop through 3 iterations to determine an approximate number of 5x5 boards: for every 3 tuple of possible rows, compute the number of possibile completions (ignoring the difference between X's and O's) by assuming the three rows are three middle rows, and then finding how many of the remaining (233^2) pairs fit for each board. The nice thing about choosing the middle three rows is that the outcome for each remaining row can be done independently (if I read the constraints right), and so you don't have (233^2) remaining iterations. In fact, by preprocessing each triple of rows, you can determine what squares are restricted or fixed,
and then compute the number of legal rows that fit those restrictions.
This idea extends to a rough estimate for the cube. Instead of choosing the middle three rows, choose the middle 9 columns in the cube, randomly select legal columns, and either use the 5x5 stats to extrapolate allowed sections of the cube, or do an analysis stage which restricts the number of allowed squares, and use that to (over-) estimate the number of completions. If you are worried about the difference between O's and X's, you can keep a running tally of the difference until you run into the last few of the 16 undetermined columns. This is like the random sampling suggested in an earlier comment, but uses a little more precision because you are picking legal rows of 5 at random instead of indivisual cells.
The other way, which might be prudent, is to do a game tree search. Start by generating all first moves, then all second moves, then all third moves, and so on. After each level of moves, apply whatever symmetry operations you wish to reduce cases, but keep track of the size of each equivalence class. Then when the tree is large enough, pick a random sample of branches to do a continuation of the game tree for a small fraction of the space,
and repeat until each branch has its own full blown extension, then select a fraction of those branches, etc, until you get an idea how much pruning gets done. For example, after 5 moves you might run out of memory to store the game tree, but you realize that, say , something like .001% of the possible configurations were pruned because they did not meet the constraints. Then choose , say, a few hundred thousand of these positions, and continue them for another four or five moves. Note that perhaps .1% of those branches had to be pruned. Repeat and observe how the constraints affect the percentage of allowed positions to decrease. This may allow you to get a rough estimate of the size of the game space.
In the first method above, I would not bother with rotations/reflections because you are using a small portion of the space to eliminate possibilities for the larger portion. In the second method, it helps to have as complete a game tree as possible, so eliminating symmetric cases early on results in more coverage of the full game tree. However, the difference between any partial tree and one shrunk by taking rotations and reflections into consideration will reduce the size by a factor of less than 100 (less than 48, more precisely), and for rough estimates like these that is not a consideration.
As a sanity check, suppose I estimate the number of positions after 10 moves. Including possibilities that are not allowed by the constraints, and taking the symmetry group into consideration, I would expect something not far from (125 choose 10) * (10 choose 5)/48, which is in the neighborhood of 10^14--10^16. If you take the second method, and compute,
say, 10^7 game positions for the first 5 moves up to symmetry, then you are on track toward this estimate. If , for each of 1000 randomly chosen positions, each one generates a five move subtree of size about 10^7, then the simulation (in my mind) bears out the hand-waving calculation I just made. If instead, the average size of each of the 1000 subtrees is more like 10^6, then the constraints are having more of an effect, and you may be able to extapolate how much I am overestimating the count.
Gerhard "Ask Me About System Design" Paseman, 2011.04.01
