Hacker News Reader

26,830 when you consider rotations and reflections. This is the important metric for your software design.

Can you explain to me what "valid" means, in the context of tic-tac-toe games? What would it mean for a tic-tac-toe game to be invalid?

um..A cell can only be in 3 states(X, O or Empty) and there are only 9 cells; so the total possible board states be 3^9 = 19683 states?

Board states, yes, but in a game of tic-tac-toe, placement order matters as well. There are a total of 9! (362880) possible (but not necessarily valid) game states. With such a low number, it's not hard to brute force the correct answer. Someone more well-versed in combinatorics could probably do it in a more efficient way.

I don’t think it is valid to consider two identical boards, arrived at via different sequences of moves, to be different “states”. They did take separate paths to get there, but their state trees have now converged and they are de-facto the same state.

And these are the kind of questions that would (hopefully) come up in the interview!

Looking at it that way, you can subtract all game states that occur after a win.