348. Design Tic-Tac-Toe

Problem¶

Design an \(n \times n\) Tic-Tac-Toe game. Each valid move places a player's mark in an empty cell; return that player's number if the move completes a row, column, or diagonal, otherwise return 0.

n = 2
move(0, 0, 1) -> 0
move(1, 0, 2) -> 0
move(0, 1, 1) -> 1

class TicTacToe:
    def __init__(self, n: int):
        pass

    def move(self, int row, int col, int player):
        pass

Key trick¶

Track a signed count for each row, column, and diagonal: add 1 for player 1 and -1 for player 2. A count with absolute value \(n\) identifies a winning line.

Trap¶

The anti-diagonal condition is row + col == n - 1. Return the player number, not a zero-based player index.

Why is it interesting?¶

It turns a board-scanning problem into an \(O(1)\) update by storing only the information needed to detect a win.

Python solution¶

class TicTacToe:
    def __init__(self, n: int):
        self.n = n
        self.rows = [0] * n
        self.cols = [0] * n
        self.diag = 0
        self.anti_diag = 0

    def move(self, row: int, col: int, player: int) -> int:
        # Opposite signs let one counter represent both players.
        delta = 1 if player == 1 else -1
        self.rows[row] += delta
        self.cols[col] += delta

        if row == col:
            self.diag += delta
        if row + col == self.n - 1:
            self.anti_diag += delta

        if (
            abs(self.rows[row]) == self.n
            or abs(self.cols[col]) == self.n
            or abs(self.diag) == self.n
            or abs(self.anti_diag) == self.n
        ):
            return player
        return 0

Complexity: \(O(1)\) time per move and \(O(n)\) space.

Comment on my solution¶

Your counter idea gives constant-time moves, but the code has three correctness issues:

The method signature needs Python annotations, such as row: int.
The anti-diagonal check uses undefined n instead of self.n.
Winning returns cur_player, which is 0 for player 1; it must return player.

The two sets of balances also duplicate information: each player's balance is the negative of the other's.

# Ideas:
# - The cost is checking if a played makes you win the
#   row, column or diagonal.
#   - (naive) walk the row, column, diagonal and count
#   - trade memory for time by keeping counters for
#     rows (columns, diagonal) telling if:
#     - a move makes player win
#     - a move can make win because both player already have
#       moved on that row (column, diagonal)


class TicTacToe:
    def __init__(self, n: int):
        self.n = n
        # [rows, cols, diag_top_left, diag_bottom_left] for 2 players
        self.balances = [[[0]*n for _ in range(2)] + [0, 0] for _ in range(2)]

    def move(self, int row, int col, int player):

        cur_player = player - 1
        other_player = 1 - cur_player

        # rows
        self.balances[cur_player][0][row] += 1
        self.balances[other_player][0][row] -= 1
        if self.balances[cur_player][0][row] == self.n:
            return cur_player

        # columns
        self.balances[cur_player][1][col] += 1
        self.balances[other_player][1][col] -= 1
        if self.balances[cur_player][1][col] == self.n:
            return cur_player

        # diag_top_left
        if row == col:
            self.balances[cur_player][2] += 1
            self.balances[other_player][2] -= 1
            if self.balances[cur_player][2] == self.n:
                return cur_player

        # diag_bottom_left
        if col == n - row - 1:
            self.balances[cur_player][3] += 1
            self.balances[other_player][3] -= 1
            if self.balances[cur_player][3] == self.n:
                return cur_player

        return 0

Extra¶

Problem description¶

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]

Explanation
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 n^2 calls will be made to move.

Follow-up: Could you do better than O(n^2) per move() operation?