Algorithm to Detect A tic tac toe Winner
Recently I was asked to work on the game of tic tac toe on iOS. Creating a game layout and rest of the business logic is straightforward, until it comes to detecting whether either side has won the game or not.
There are 2 ways of solving this problem - Brute force and using some smarter solution. In this blog post we won't discuss brute force approach as that solution is pretty straightforward - we simply need to create a matrix of size 3 X 3 and check each winning combination after each move by every player.
This blog post will mostly concern with smarter solution which has a linear time complexity for the board of given size. This efficiency is achieved by the use of extra storage in the form of 4 one-dimensional arrays. We will call these storage items as simply containers. They will be divided into following 4 categories based on the type of winning combinations,
- Rows container (When player wins along rows)
- Columns container (When player wins along columns)
- Diagonal container (When player wins along diagonal)
- Opposite diagonal container (When player wins along opposite diagonal)
Since winning combination can emerge in any of these directions, we maintain these containers in each direction to detect the win after each move.
How can either player win the game of tic-tac-toe?
- Along rows
There are 3 ways player can win along rows ,
0 1 2 0 1 2 0 1 2
------------- ------------- -------------
0 | X | X | X | | | | | | | | |
------------- ------------- -------------
1 | | | | Or | X | X | X | Or | | | |
------------- ------------- -------------
2 | | | | | | | | | X | X | X |
------------- ------------- -------------2. Along columns
There are 3 ways player can win along columns,
0 1 2 0 1 2 0 1 2
------------- ------------- -------------
0 | X | | | | | X | | | | | X |
------------- ------------- -------------
1 | X | | | Or | | X | | Or | | | X |
------------- ------------- -------------
2 | X | | | | | X | | | | | X |
------------- ------------- -------------3. Along the diagonal
There is only 1 way player can win along the diagonal,
0 1 2
-------------
0 | X | | |
-------------
1 | | X | |
-------------
2 | | | X |
------------- 4. Along the opposite diagonal
There is only 1 way player can win along the diagonal,
0 1 2
-------------
0 | | | X |
-------------
1 | | X | |
-------------
2 | X | | |
------------- As we discussed all four cases with their diagrammatic representations, let's see how we can use temporary containers to check for win.
- Along rows
To detect the win across either row, we will maintain an array called as rowsContainer storing integer values. Since our board size is 3 X 3, the rowsContainer size will be 3 and all the places initialized by 0 since player hasn't made a move yet.
Every time player adds a X, it will have its own position marked in terms of (row, column) pair and we will increment the value at the index corresponding to row by 1. For example, if user makes move at positions (0, 1), (2, 2), (2, 1), (0, 2), (1, 0) the value of row container will be as follows,
[2, 0, 2]
Since we touched row #0 twice, row #1 one and row #2 twice. So how can be leverage it to detect the user win along rows?
If user is going to win in first row, which moves do they have to do? Answer is, combination of (0, 0) (0, 1), (0, 2) in any sequence. And by the time they're done with these moves, the value contained in the rows container will be [3, 0, 0]. Every time user makes a move, we're going to check if the value stored in rowsContainer at index row is equal to size of board. If the value is equal to size of the board, then we can declare the player has won.
We can use the similar logic to detect win along other two rows,
--------------------------------------
| Board state | Rows container |
--------------------------------------
| 0 1 2 | |
-------------
| 0 | | | | | |
-------------
| 1 | X | X | X | | [0, 3, 0] |
-------------
| 2 | | | | | |
-------------
| | |
--------------------------------------
| 0 1 2 | |
-------------
| 0 | | | | | |
------------- [0, 0, 3]
| 1 | | | | | |
-------------
| 2 | X | X | X | | |
-------------
--------------------------------------
With this understanding in mind we can write our Swift code to detect win along rows as follows,
func makeMove(row: Int, column: Int) {
rowsContainer[row] += 1
if rowsContainer[row] == 3 {
// Player has won the game along one of the rows
}
}
2. Along columns
To detect the win along columns, we will use similar strategy. Here we will use another container columnsContainer with size equal to size of board (In this case 3) with all values initialized to zero. Every time user makes a move at that column position, we will increment value at corresponding index by 1.
For example, if user makes move at positions (1, 0), (2, 2), (1, 2), (2, 0), (0, 1) the value of columns container will be as follows,
[2, 0, 2]
Since we touched column #0 twice, column #1 one and column #2 twice. So how can be leverage it to detect the user win along any column?
If user is going to win in the first column, which moves do they have to do? Answer is, combination of (0, 0) (1, 0), (2, 0) in any sequence. And by the time they're done with these moves, the value contained in the columns container will be [3, 0, 0] since they used column #0 3 times.
We can use the similar logic to detect win along other two columns,
------------------------------------------
| Board state | Columns container |
------------------------------------------
| 0 1 2 | |
-------------
| 0 | | X | | | |
-------------
| 1 | | X | | | [0, 3, 0] |
-------------
| 2 | | X | | | |
-------------
| | |
-----------------------------------------
| 0 1 2 | |
-------------
| 0 | | | X | | |
------------- [0, 0, 3]
| 1 | | | X | | |
-------------
| 2 | | | X | | |
-------------
----------------------------------------
Now let's write a Swift code snippet to mark positions in container as we go along and detect the win if any of the winning combination is detected,
func makeMove(row: Int, column: Int) {
columnsContainer[column] += 1
if columnsContainer[column] == 3 {
// Player has won the game along one of the columns
}
}
3. Along the Diagonal
Checking the win along regular diagonal is bit tricky and not too complicated. Similar to first two cases here we are going to use another container diagonalContainer to mark positions and then run our logic to decide if user has indeed won along the diagonal.
However, we don't directly mark the diagonalContainer. First we will check if the incoming row is same as the input column and then increment the value at index corresponding to that column (Or row) by 1. The table below shows the winning combination and corresponding state for diagonalContainer.
------------------------------------------
| Board state | Diagonal container |
------------------------------------------
| 0 1 2 | |
-------------
| 0 | X | | | | |
------------- [1, 1, 1]
| 1 | | X | | | |
-------------
| 2 | | | X | | |
-------------
-----------------------------------------
Now we have diagonal container is perfect winning state. So all we have to do after each move is to sum up all its elements and verify if the sum is equal to size of the board. If that is true, user has won along the primary diagonal.
func makeMove(row: Int, column: Int) {
if row == column {
diagonalContainer[row] += 1
}
var totalSum = 0
for (_, element) in diagonalContainer.enumerated() {
totalSum += element
}
if totalSum == 3 {
// User has won the game along the primary diagonal
}
}
Please note that even though we're iterating over every element in diagonalContainer, this is still a linear-time operation4. Along the Opposite Diagonal
Finally we're going to take a look at how we can detect the win along the opposite diagonal. Initially I thought we could use the same logic and diagonal container we already had. But turns out this slightly different case.
Here we are going to use another container oppositeDiagonalContainer to mark places. Detecting whether user has marked along opposite diagonal also needs extra logic. So how do we check if the marked position pair (row, column) falls along this diagonal?
For typical 3 X 3 board, these positions are [(0, 2), (1, 1), (2, 0)]. For all position pairs the sum of row and column is one less than the size of 3 X 3 board. Thus we can say,
if row + column + 1 == 3 {
// Move is made along the opposite diagonal
}
If this condition is true, then choose either row or column value and use it as an index. Now increment the value in oppositeDiagonalContainer situated at that index by 1.
The table below shows the winning combination and corresponding state for oppositeDiagonalContainer.
------------------------------------------------
| Board state | Opp. Diagonal container |
------------------------------------------------
| 0 1 2 | |
-------------
| 0 | | | X | | |
------------- [1, 1, 1]
| 1 | | X | | | |
-------------
| 2 | X | | | | |
-------------
-----------------------------------------------
Please note that oppositeDiagonalContainer will have exact same state whether you choose row or the column as the index as long as that choice is consistentNow the next thing we will do is to sum up all the elements in oppositeDiagonalContainer and testing if that value is equal to the size of board. If it is, the player has won along the diagonal.
func makeMove(row: Int, column: Int) {
if row + column + 1 == 3 {
oppositeDiagonalContainer[row] += 1
}
var totalSum = 0
for (_, element) in oppositeDiagonalContainer.enumerated() {
totalSum += element
}
if totalSum == 3 {
// User has won the game along the opposite diagonal
}
}
Now, as we discussed all the winning combinations and logic behind detecting the win, let's go ahead and write the complete code,
// We will use two containers for keeping tracks of marked rows and columns in the matrix
// Size of each container is equal to the size of board
var rowsContainer: [Int] = [0, 0, 0]
var columnsContainer: [Int] = [0, 0, 0]
// We will also use two other containers to keep track of regular and opposite diagonal combinations
// Size of each diagonal container is also equal the size of board
var diagonalContainer: [Int] = [0, 0, 0]
var oppositeDiagonalContainer: [Int] = [0, 0, 0]
func makeMove(row: Int, column: Int, sizeOfBoard: Int) {
// Populate all the containers based on the marked position
rowsContainer[row] += 1
columnsContainer[column] += 1
if row == column {
diagonalContainer[row] += 1
}
if row + column + 1 == sizeOfBoard {
oppositeDiagonalContainer[row] += 1
}
// Now check for win across either direction
if rowsContainer[row] == sizeOfBoard {
// Win across row
}
if columnsContainer[column] == sizeOfBoard {
// Win across column
}
var sumForRegularDiagonalElements = 0
var sumForOppositeDiagonalElements = 0
for (index, _) in diagonalContainer.enumerated() {
sumForRegularDiagonalElements += diagonalContainer[index]
sumForOppositeDiagonalElements += oppositeDiagonalContainer[index]
}
if sumForRegularDiagonalElements == sizeOfBoard {
// Win across regular diagonal
}
if sumForOppositeDiagonalElements == sizeOfBoard {
// Win across opposite diagonal
}
}
Calculating Complexity
Space Complexity:
For the board of arbitrary size n * n, we need to maintain 4 container - One for each direction. So we will need total space for 4 * n elements. That makes the worst case space complexity O(n * 4) or simple O(n)
Time Complexity
Every time player makes a move, we need to set certain positions in some containers. This operation happens in constant time.
We also need to check the player win in all the directions. For win across rows and columns, this is a constant operation since we can directly grab the element at index and compare it with current board size.
When it comes to detecting win across either diagonal though, we need to iterate over both containers to sum up all elements. For board of size n, we need to perform traversal twice. Thus time complexity for detecting a win in tic-tac-toe is O(2 * n) or simple O(n). (Which is achieved at the expense of extra space complexity)
So that's all folks! Thanks for taking a time to read through it. Please let me know in the comment box if you have follow-up questions or suggestions for improving space or time complexity of algorithm