# How many games are possible in Tictactoe?

This topic is 2532 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

this was a question in an exam I just did

my answer was 9! but I was told it was wrong

really?

##### Share on other sites

this was a question in an exam I just did

my answer was 9! but I was told it was wrong

really?

Perhaps it's 18. Or 1*2*3*4*5*6*7*8*9*2?

Remember, there are 2 players.

##### Share on other sites
This is kind of vague to me.

Is:

 XXX OO. ... 

supposed to be a different outcome than:

 XXX O.O ... 

##### Share on other sites
If I remember correctly there are 8 different outcomes for each player in a winning game.

one for each row so that is 3 different possibilities. One for each column which is another 3 possibilities. Finally one for each diagonal which is 2 more possibilities.

So that gives us (3 + 3 + 2) * 2 = 16 different winning outcomes in tic tac toe. Not sure if the question asked for losing outcomes as well.

##### Share on other sites
What an open-ended question. Is a "game" defined by where a player places his pieces, in what order? You may win by getting 3 diagonal, but is it a different "game" if you play the middle place as your 1st, 2nd, or 3rd move? I would say yes. Which would get the number of games into a very high count.

##### Share on other sites

this was a question in an exam I just did

my answer was 9! but I was told it was wrong

really?

yes, 9! is the number of ways you can fill the board in completely(assuming that order matters), games can end before the board is completely filled

##### Share on other sites
Also the board is symmetric along 4 axii: horizontal, vertical, and 2 diagonals. So you can pick one, flip/mirror the board across it, and thus show half the possible sequences of moves to be duplicates of the other half.

##### Share on other sites
sounds like a challenging problem..

I think "game" is probably defined as "a sequence of moves that terminates in one player winning or a draw"

You'd have to start with 9! and then subtract all the games that are impossible. Specifically, any game where there are moves after a player has reached 3 in a row is impossible.

So.. in the whole game there are 9 moves. We don't have to worry about a winner until move number 5 (when X might win). How many different ways can we have a winner in 5 moves? There are 8 different ways to win, and order is important, there are 6 different ways to order 3 moves. Also, O is also playing- there are 6 remaining spots on the board (after you subtract the 3 that X uses to win), so there's 6*5 ways that O could play before losing. So that's 8*6*6*5, or 1440 games that end at move #5.

With that number you can figure out how much the 9! total has overcounted. After a victory in 5 moves, there's 4! ways to keep playing. So the 9! number has overcounted by 1440*4! = 34560. So the final answer would be 9! minus 34560. But let's not forget the 1440 valid games that ended after 5 moves, so add 1440 back in.

I think you would have to continue and find numbers of games that are impossible because of victories after move #6, #7 and #8. It gets complicated quickly. What class is this for?

##### Share on other sites
I count 255,168 games, without considering any symmetries.

#include <iostream> unsigned const magic[9] = { 010010010, 010001000, 010000101, 001010000, 001001011, 001000100, 000110001, 000101000, 000100110 }; int count(unsigned p[2], int to_play, unsigned unused) { if (p[!to_play] & 044444444) return 1; // Last move was a win if (p[0]+p[1] == 055555555) return 1; // Full board int result = 0; for (int i=0; i<9; ++i) { if (unused & (1u<<i)) { p[to_play] += magic; result += count(p, !to_play, unused^(1u<<i)); p[to_play] -= magic; } } return result; } int main() { unsigned p[2] = {011111111, 011111111}; std::cout << count(p, 0, 0777) << '\n'; } 

##### Share on other sites
Hidden
How does this dark magic work?

• 11
• 19
• 12
• 34
• 9
• ### Forum Statistics

• Total Topics
631398
• Total Posts
2999838
×