Modeling boards and grids

01The intuition

The problem it solves

You are asked to write tic-tac-toe. The first version is a list of lists and a function that checks all eight lines after every move, with the rules of the board scattered through the code that reads input.

board = [["", "", ""], ["", "", ""], ["", "", ""]]

def play(r: int, c: int, mark: str) -> bool:
    board[r][c] = mark
    for i in range(3):
        if board[i][0] == board[i][1] == board[i][2] == mark:
            return True
        if board[0][i] == board[1][i] == board[2][i] == mark:
            return True
    if board[0][0] == board[1][1] == board[2][2] == mark:
        return True
    return board[0][2] == board[1][1] == board[2][0] == mark

Three things are wrong. Nothing stops a move on an occupied cell or outside the board. The win check is written for exactly three in a row and breaks the moment the interviewer says "now make it n by n". And the board is a global, so there is no second game and no test that starts from a known position.

Build it one piece at a time

Step one: make the board an object that owns its cells and enforces its rules. Bounds and occupancy checks live in one place, and the caller gets a clear error instead of a silent corrupt state.

class Board:
    def __init__(self, n: int) -> None:
        self.n = n
        self.cells: list[list[str]] = [["" for _ in range(n)] for _ in range(n)]

    def in_bounds(self, r: int, c: int) -> bool:
        return 0 <= r < self.n and 0 <= c < self.n

    def place(self, r: int, c: int, mark: str) -> None:
        if not self.in_bounds(r, c):
            raise ValueError("off the board")
        if self.cells[r][c]:
            raise ValueError("cell taken")
        self.cells[r][c] = mark

Step two: replace the eight hand-written lines with counters. For an n by n board keep, per player, a count for each row, each column and the two diagonals. A move adds one to the counts it touches; a win is any count reaching n. The check becomes O(1) and works for any n.

class Game:
    def __init__(self, n: int) -> None:
        self.board = Board(n)
        self.n = n
        self.rows = {"X": [0] * n, "O": [0] * n}
        self.cols = {"X": [0] * n, "O": [0] * n}
        self.diag = {"X": 0, "O": 0}
        self.anti = {"X": 0, "O": 0}

    def move(self, r: int, c: int, mark: str) -> bool:
        self.board.place(r, c, mark)
        self.rows[mark][r] += 1
        self.cols[mark][c] += 1
        if r == c:
            self.diag[mark] += 1
        if r + c == self.n - 1:
            self.anti[mark] += 1
        n = self.n
        return (self.rows[mark][r] == n or self.cols[mark][c] == n
                or self.diag[mark] == n or self.anti[mark] == n)

Step three: direction vectors. For games like Connect Four, Gomoku or an infinite grid, counting lines is replaced by walking from the placed cell in each of four directions and its opposite, adding up a run. The directions are data, so a new rule such as "five in a row" is a number, not new code.

DIRS = [(0, 1), (1, 0), (1, 1), (1, -1)]

class InfiniteGame:
    def __init__(self, k: int) -> None:
        self.k = k
        self.marks: dict[tuple[int, int], str] = {}

    def move(self, r: int, c: int, mark: str) -> bool:
        if (r, c) in self.marks:
            raise ValueError("cell taken")
        self.marks[(r, c)] = mark
        for dr, dc in DIRS:
            run = 1
            for sign in (1, -1):
                rr, cc = r + dr * sign, c + dc * sign
                while self.marks.get((rr, cc)) == mark:
                    run += 1
                    rr, cc = rr + dr * sign, cc + dc * sign
            if run >= self.k:
                return True
        return False

State after X plays (0,0), O plays (1,1), X plays (0,1) on a 3 by 3 counter board:

Why it works

The invariant of the counter version is that each counter equals the number of that player's marks on that line. Because a move touches exactly the lines through its cell, the update is constant and the invariant survives. The dictionary-based version has a different invariant: a cell is in the map if and only if it is occupied, so the board can be unbounded and sparse at no memory cost for empty cells.

Where it breaks: the counter trick assumes marks are never removed. Undo, captures or a sliding window (as in 2048 or Snake) need either recounting the affected lines or a different model. The other trap is mixing coordinates: decide once whether (r, c) is row-then-column and keep every method in that order.

per move: eight lines × n cells = 8n comparisons, versus 4 counter updates and 4 comparisons

The trade-off you must say out loud

Counters are fast but only answer "is there a full line"; direction walks cost up to 8k per move but handle any board size, any k and sparse grids. For a 3 by 3 game, the plain version is honestly fine, and saying so is a point in your favour. Then name the extension you are ready for: n by n, k in a row, infinite grid, undo. The follow-up that usually comes next is a second rule set, such as gravity in Connect Four, which belongs in the board's place, not in the win check.

Where it shows up in the 100 Google problems

• Tic-tac-toe: counters for O(1) wins, then the infinite-grid variant with direction walks.
• Snake: the grid is a set of occupied cells plus a deque for the body, so collision is a set lookup.
• 2048: rows are slid and merged as pure functions; rotating the board reuses one function for four directions.
• Minesweeper: neighbour iteration with the eight direction vectors, bounds checks in one helper.
• Chess: a board of squares where pieces, not the board, decide legal moves.

02Used in these problems

• Design tic-tac-toe
• Design chess
• Design the Snake game
• Design Snake and Ladder
• Design 2048
• Design Minesweeper