5 ms·
Since I didn't see it mentioned here among the mentions of satire, and I found the problem interesting... The number of valid tic-tac-toe games is 255168.
by Liru 6y ago
Since I didn't see it mentioned here among the mentions of satire, and I found the problem interesting...
The number of valid tic-tac-toe games is 255168.
- jagged-chisel 6y ago26,830 when you consider rotations and reflections. This is the important metric for your software design.
- gogs_bread 6y agoum..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?
- Liru 6y agoBoard 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.
- shhsshs 6y agoI 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!
- deleted 6y ago[deleted]
- jl2718 6y agoLooking at it that way, you can subtract all game states that occur after a win.
- anthuswilliams 6y agoCan 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?