Menu
This is an interview question. "How would you determine if someone has won a game of tic-tac-toe on a board of any size?" I heard the algorithm complexity was O(1). Does it make sense ? Can anybody explain the algorithm ?
462
Unfortunately, there is no way to guarantee that a player will win every single game of tic tac toe they play. Victory, defeat, or a draw is determined by the interaction of both players. If both players operate perfectly, a draw will always occur.
In tic tac toe, a player wins if they have 3 of their symbols in one row, column, or diagonal.
(read “9 factorial”) = 362,880 ways to fill the board. In actuality, tic-tac-toe players fill in each of the nine entries with one of only three values: an X, an O, or leave it blank. That's a total of 3*3*3*3*3*3*3*3*3 = 3^9 = 19,683 different ways the 3x3 grid can be filled in.
The answer is right on that page, but I'll explain it anyway.
The algorithm's complexity is O(1) for determining if a given move will win the game. It cannot be O(1) in general since you need to know the state of the board to determine a winner. However, you can build that state incrementally such that you can determine whether a move wins in O(1).
To start, have an array of numbers for each row, column, and diagonal for each player. On each move, increment the elements corresponding to the player for the row, column, and diagonal (the move may not necessarily be on a diagonal) influenced by that move. If the count for that player is equal to the dimension of the board, that player wins.
75
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
