Problem
Design a Tic-tac-toe game that is played between two players on anxngrid. You may assume the following rules:
- A move is guaranteed to be valid and is placed on an empty block.
- Once a winning condition is reached, no more moves is allowed.
- A player who succeeds in placing n of their marks in a horizontal, vertical, or diagonal row wins the game.
Examples
**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]
Explanation
Given n = 3, assume that player 1 is "X" and player 2 is "O" in the board.
TicTacToe toe = new TicTacToe(3);
toe.move(0, 0, 1); -> Returns 0 (no one wins)
|X| | |
| | | | // Player 1 makes a move at (0, 0).
| | | |
toe.move(0, 2, 2); -> Returns 0 (no one wins)
|X| |O|
| | | | // Player 2 makes a move at (0, 2).
| | | |
toe.move(2, 2, 1); -> Returns 0 (no one wins)
|X| |O|
| | | | // Player 1 makes a move at (2, 2).
| | |X|
toe.move(1, 1, 2); -> Returns 0 (no one wins)
|X| |O|
| |O| | // Player 2 makes a move at (1, 1).
| | |X|
toe.move(2, 0, 1); -> Returns 0 (no one wins)
|X| |O|
| |O| | // Player 1 makes a move at (2, 0).
|X| |X|
toe.move(1, 0, 2); -> Returns 0 (no one wins)
|X| |O|
|O|O| | // Player 2 makes a move at (1, 0).
|X| |X|
toe.move(2, 1, 1); -> Returns 1 (player 1 wins)
|X| |O|
|O|O| | // Player 1 makes a move at (2, 1).
|X|X|X|
Follow up: Could you do better than O(n^2) permove()
operation?
Could you get O(1) per move()
operation?
Class structure
class TicTacToe {
/** Initialize your data structure here. */
public TicTacToe(int n) {
}
/** Player {player} makes a move at ({row}, {col}).
@param row The row of the board.
@param col The column of the board.
@param player The player, can be either 1 or 2.
@return The current winning condition, can be either:
0: No one wins.
1: Player 1 wins.
2: Player 2 wins. */
public int move(int row, int col, int player) {
}
}
Solution
Method 1 - Use 2D char array
Here are the steps:
- Initialization:
- Create a
board
with sizen x n
. - Use characters ‘X’ and ‘O’ to represent the moves of the two players.
- Create a
- Making a Move:
- Validate the move to ensure it is placed on an empty block.
- Update the
board
with the player’s move. - Check if the current move results in a win by evaluating the row, column, primary diagonal, and anti-diagonal containing the move.
- Check Win Condition:
- For each move, check the corresponding row, column, and diagonals if they contain all identical marks (
X
orO
).
- For each move, check the corresponding row, column, and diagonals if they contain all identical marks (
This ensures that the game accurately tracks moves and winning conditions with each move evaluated in linear time relative to the grid size.
Code
Java
class TicTacToe {
private char[][] board;
private static char X = 'X';
private static char O = 'O';
private int n;
/** Initialize your data structure here. */
public TicTacToe(int n) {
this.board = new char[n][n];
this.n = n;
}
/** Player {player} makes a move at ({row}, {col}).
@param row The row of the board.
@param col The column of the board.
@param player The player, can be either 1 or 2.
@return The current winning condition, can be either:
0: No one wins.
1: Player 1 wins.
2: Player 2 wins. */
public int move(int row, int col, int player) {
char c;
if (player == 1) {
c = X;
} else {
c = O;
}
if (board[row][col] != 0) {
// throw error, occupied
return 0;
}
board[row][col] = c;
if (hasWon(row, col, size, c)) {
return player;
}
return 0;
}
private boolean hasWon(int row, int col, char c) {
// check horizontal
boolean rowLine = true;
for (int i = 0; i < n; i++) {
rowLine = rowLine && (board[i][col] == c);
}
if (rowLine) return true;
// check vertical
boolean colLine = true;
for (int j = 0; j < n; j++) {
colLine = colLine && (board[row][j] == c);
}
if(colLine) return true;
// is diagonal
if(row == col) {
boolean diagLine1 = true;
for (int j = 0; j < n; j++) {
diagLine1 = diagLine1 && (board[j][j] == c);
}
if(diagLine1) return true;
}
// check anti-diagonal
if (row + col == n - 1) {
boolean diagLine2 = true;
for (int j = 0; j < n; j++) {
diagLine2 = diagLine2 && (board[n - 1 - j][j] == c);
}
if(diagLine2) return true;
}
return false;
}
}
/**
* Your TicTacToe object will be instantiated and called as such:
* TicTacToe obj = new TicTacToe(n);
* int param_1 = obj.move(row,col,player);
*/
Python
class TicTacToe:
def __init__(self, n: int):
self.n: int = n
self.board: List[List[str]] = [[''] * n for _ in range(n)]
self.X: str = 'X'
self.O: str = 'O'
def move(self, row: int, col: int, player: int) -> int:
c: str = self.X if player == 1 else self.O
if self.board[row][col] != '':
# invalid move, since the problem guarantees valid moves, we can omit this check
return 0
self.board[row][col] = c
if self.has_won(row, col, c):
return player
return 0
def has_won(self, row: int, col: int, c: str) -> bool:
# check horizontal
row_line: bool = all(self.board[row][i] == c for i in range(self.n))
if row_line:
return True
# check vertical
col_line: bool = all(self.board[i][col] == c for i in range(self.n))
if col_line:
return True
# check diagonal
if row == col:
diag_line1: bool = all(self.board[i][i] == c for i in range(self.n))
if diag_line1:
return True
# check anti-diagonal
if row + col == self.n - 1:
diag_line2: bool = all(self.board[i][self.n - 1 - i] == c for i in range(self.n))
if diag_line2:
return True
return False
Method 2 - Using arrays for rows and cols
The approach optimizes the process of determining the winner by utilizing counters for rows, columns, and diagonals, instead of maintaining the entire n x n
board.
Key Observations
- Winning Condition: To win Tic-tac-toe, a player must have all their marks in a single row, column, or diagonal.
- Optimized Tracking: Instead of tracking each cell, maintain counters for each row, column, and the two diagonals.
- Player Identification: Use +1 for Player 1 and -1 for Player 2, making it easy to count and identify winning conditions by the absolute value of the counters.
Steps
- Initialization:
- Create arrays to keep count of marks in each row and column (
rows
andcols
). - Use variables to keep track of the main diagonal and anti-diagonal counts.
- Create arrays to keep count of marks in each row and column (
- Making a Move:
- Update the corresponding row, column, and diagonal counters based on the player’s move.
- Check if the current move results in a win by evaluating if any counter equals
n
(the size of the grid), after adjusting for the player’s identifier.
- Check Win Condition:
- If any row, column, or diagonal counter reaches the absolute value
n
, the respective player has won.
- If any row, column, or diagonal counter reaches the absolute value
This ensures that each move and win check operates in constant time, making the implementation highly efficient.
Code
Java
public class TicTacToe {
private int[] rows;
private int[] cols;
private int diagonal;
private int antiDiagonal;
private int n;
/** Initialize your data structure here. */
public TicTacToe(int n) {
this.n = n;
rows = new int[n];
cols = new int[n];
}
/** Player {player} makes a move at ({row}, {col}).
@param row The row of the board.
@param col The column of the board.
@param player The player, can be either 1 or 2.
@return The current winning condition, can be either:
0: No one wins.
1: Player 1 wins.
2: Player 2 wins. */
public int move(int row, int col, int player) {
int toAdd = player == 1 ? 1 : -1;
rows[row] += toAdd;
cols[col] += toAdd;
if (row == col) {
diagonal += toAdd;
}
if (col + row == n - 1) {
antiDiagonal += toAdd;
}
if (Math.abs(rows[row]) == n || Math.abs(cols[col]) == n ||
Math.abs(diagonal) == n || Math.abs(antiDiagonal) == n) {
return player;
}
return 0;
}
}
We can skip using Math.abs(), by changing the target
:
class TicTacToe {
int[] rows, cols;
int d1, d2, n;
public TicTacToe(int n) {
rows = new int[n];
cols = new int[n];
d1 = 0;
d2 = 0;
this.n = n;
}
public int move(int row, int col, int player) {
int val = (player == 1) ? 1 : -1;
int target = (player == 1) ? n : -n;
if(row == col) { // diagonal
d1 += val;
if(d1 == target) return player;
}
if(row + col + 1 == n) { // anti diagonal
d2 += val;
if(d2 == target) return player;
}
rows[row] += val;
cols[col] += val;
if(rows[row] == target || cols[col] == target) return player;
return 0;
}
}
Python
class TicTacToe:
def __init__(self, n: int):
self.n: int = n
self.rows: List[int] = [0] * n
self.cols: List[int] = [0] * n
self.diagonal: int = 0
self.antiDiagonal: int = 0
def move(self, row: int, col: int, player: int) -> int:
to_add: int = 1 if player == 1 else -1
self.rows[row] += to_add
self.cols[col] += to_add
if row == col:
self.diagonal += to_add
if row + col == self.n - 1:
self.antiDiagonal += to_add
if abs(self.rows[row]) == self.n or \
abs(self.cols[col]) == self.n or \
abs(self.diagonal) == self.n or \
abs(self.antiDiagonal) == self.n:
return player
return 0