Design Tic-Tac-Toe
Assume the following rules are for the tic-tac-toe game on an n x n board between two players:
A move is guaranteed to be valid and is placed on an empty block.
Once a winning condition is reached, no more moves are allowed.
A player who succeeds in placing n of their marks in a horizontal, vertical, or diagonal row wins the game.
Implement the TicTacToe class:
TicTacToe(int n) : Initializes the object the size of the board n.
int move(int row, int col, int player)
Indicates that the player with id player plays at the cell (row, col) of the board.
The move is guaranteed to be a valid move, and the two players alternate in making moves.
Return 0 if there is no winner after the move, 1 if player 1 is the winner after the move,
or 2 if player 2 is the winner after the move.
Example 1:
Input: ["TicTacToe", "move", "move", "move", "move", "move", "move","move"]
[[3], [0, 0, 1], [0, 2, 2], [2, 2, 1], [1, 1, 2], [2, 0, 1], [1, 0, 2], [2, 1, 1]]
Output: [null, 0, 0, 0, 0, 0, 0, 1]
Example 2:
TicTacToe ticTacToe = new TicTacToe(3);
Assume that player 1 is "X" and player 2 is "O" in the board.
ticTacToe.move(0, 0, 1); // return 0 (no one wins)
|X| | |
| | | | // Player 1 makes a move at (0, 0).
| | | |
ticTacToe.move(0, 2, 2); // return 0 (no one wins)
|X| |O|
| | | | // Player 2 makes a move at (0, 2).
| | | |
ticTacToe.move(2, 2, 1); // return 0 (no one wins)
|X| |O|
| | | | // Player 1 makes a move at (2, 2).
| | |X|
ticTacToe.move(1, 1, 2); // return 0 (no one wins)
|X| |O|
| |O| | // Player 2 makes a move at (1, 1).
| | |X|
ticTacToe.move(2, 0, 1); // return 0 (no one wins)
|X| |O|
| |O| | // Player 1 makes a move at (2, 0).
|X| |X|
ticTacToe.move(1, 0, 2); // return 0 (no one wins)
|X| |O|
|O|O| | // Player 2 makes a move at (1, 0).
|X| |X|
ticTacToe.move(2, 1, 1); // return 1 (player 1 wins)
|X| |O|
|O|O| | // Player 1 makes a move at (2, 1).
|X|X|X|
Constraints:
2 ≤ n ≤ 100
player is 1 or 2.
0 ≤ row, col < n
(row, col) are unique for each different call to move.
At most n2 calls will be made to move.
Follow-up: Could you do better than O(n2) per move() operation?
Summary
Tic Tac Toe is one of the classic games most of us have played in our childhood.
The game rules are pretty simple.
There are 2 players that take turns marking a position on an n * n board.
The first player that makes n marks horizontally, vertically, or diagonally, wins the game.
The brute force approach to solve this problem is to iterate over the entire board of size n * n and
check if the current player has marked any row, column, diagonal or anti-diagonal.
This approach is exhaustive and requires 2 * O(n^2) time for every move.
Let's look at other more efficient approaches to solve the problem.
Approach 1: Optimized Brute Force
Intuition
The simplest and most intuitive approach is to check on every move if the current player has won.
Each player makes a move by marking a cell on the board.
The given cell is located at row row and column col.
The 4 ways in which a player can win are as follows:
Player has marked the entire row given by row.
Player has marked the entire column given by col.
Player has marked the diagonal beginning at the top left corner of the board and ending at the bottom right corner.
Player has marked the anti-diagonal beginning at the top right corner of the board and ending at the bottom left corner.
The following figure illustrates the 4 winning conditions.
How do we identify which cells lie on the diagonal or anti-diagonal?
Every cell on the main diagonal has a unique property; the row index equals the column index.
Similarly, for every cell on the anti-diagonal, the value of the column index is equal to n - row - 1.
Every move, we will check if any of the above conditions are true.
If yes, we declare the current player as the winner and finish the game.
Algorithm:-
For a given n, /p>
initialize a 2-dimensional array board of size n * n with the values of all elements set to 0.
Every move, mark the row and col on the board with the current player's id player.
Now, we will check the following conditions to see if the current player has won.
Check if all of the cells for the given row are marked by the current player.
To do so, we must iterate over all the columns ranging from index 0 to n - 1,
keeping the row index constant.
Check if all of the positions for the given col are marked by the current player.
To do so, we must iterate over all the rows ranging from index 0 to n - 1, keeping the col index constant.
Check if the main diagonal is completely marked by the current player.
From the above intuition, we know that for each cell on the main diagonal,
the row and col indices are equal.
Thus, every cell on the diagonal can be given by board[row][row].
Check if the anti-diagonal is completely marked by the current player.
From the above intuition for each cell in the anti-diagonal,
the value of the col index is equal to n - row - 1.
Thus, every cell in the anti-diagonal could be given by board[row][n - row - 1].
If the current player wins the game, then return player.
Otherwise, return 0 indicating that no one has won the game.
Implementation:-
class TicTacToe {
private int[][] board;
private int n;
public TicTacToe(int n) {
board = new int[n][n];
this.n = n;
}
public int move(int row, int col, int player) {
board[row][col] = player;
// check if the player wins
if ((checkRow(row, player)) ||
(checkColumn(col, player)) ||
(row == col && checkDiagonal(player)) ||
(col == n - row - 1 && checkAntiDiagonal(player))) {
return player;
}
// No one wins
return 0;
}
private boolean checkDiagonal(int player) {
for (int row = 0; row < n; row++) {
if (board[row][row] != player) {
return false;
}
}
return true;
}
private boolean checkAntiDiagonal(int player) {
for (int row = 0; row < n; row++) {
if (board[row][n - row - 1] != player) {
return false;
}
}
return true;
}
private boolean checkColumn(int col, int player) {
for (int row = 0; row < n; row++) {
if (board[row][col] != player) {
return false;
}
}
return true;
}
private boolean checkRow(int row, int player) {
for (int col = 0; col < n; col++) {
if (board[row][col] != player) {
return false;
}
}
return true;
}
}
Time and Space Complexity
Time Complexity: O(n),
as for every move we are iterating over n cells 44 times to check for each of the column, row, diagonal row, and anti-diagonal.
This gives us time complexity of (4)O(4⋅n) which is equivalent to O(n).
Space Complexity: 2*O(n^2), as we are using 2-dimensional array board of size n * n.
<Time Complexity: O(n) and Space Complexity: O(n)
