3 ms·
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 sta
by Liru 6y ago
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.
- 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.