this was a question in an exam I just did

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

really?

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.

This is kind of vague to me.

Is:


XXX
OO.
...


supposed to be a different outcome than:


XXX
O.O
...


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.

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.

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?

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';
}