Tic-Tac-Toe / Board Game Design

A prompt worth over-generalizing deliberately — the value isn't a working tic-tac-toe, it's a design that survives "now make it Connect-4" as a follow-up.

Core separation of concerns

class Board {
    private final char[][] grid;
    private final int size;
    Board(int size) { this.size = size; this.grid = new char[size][size]; }

    boolean placeMark(int row, int col, char symbol) {
        if (grid[row][col] != 0) return false; // cell occupied
        grid[row][col] = symbol;
        return true;
    }
    char get(int row, int col) { return grid[row][col]; }
    int getSize() { return size; }
}

class Player {
    private final String name;
    private final char symbol;
}

enum GameState { IN_PROGRESS, WON, DRAW }

class Game {
    private final Board board;
    private final List<Player> players;
    private final WinningStrategy winningStrategy; // pluggable — the key generalization point
    private int currentPlayerIndex = 0;
    private GameState state = GameState.IN_PROGRESS;

    boolean makeMove(int row, int col) {
        Player current = players.get(currentPlayerIndex);
        if (!board.placeMark(row, col, current.getSymbol())) return false;
        if (winningStrategy.checkWin(board, current.getSymbol())) state = GameState.WON;
        else if (isBoardFull()) state = GameState.DRAW;
        else currentPlayerIndex = (currentPlayerIndex + 1) % players.size();
        return true;
    }
}

WinningStrategy as the generalization point

interface WinningStrategy { boolean checkWin(Board board, char symbol); }

class ThreeInARowStrategy implements WinningStrategy {
    public boolean checkWin(Board board, char symbol) {
        int n = board.getSize();
        for (int i = 0; i < n; i++) {
            if (checkRow(board, i, symbol) || checkColumn(board, i, symbol)) return true;
        }
        return checkDiagonals(board, symbol);
    }
    // checkRow/checkColumn/checkDiagonals: scan for `n` consecutive matching symbols
}

class ConnectKStrategy implements WinningStrategy {
    private final int k; // 4 for Connect-4
    ConnectKStrategy(int k) { this.k = k; }
    public boolean checkWin(Board board, char symbol) {
        // scan every direction (horizontal, vertical, both diagonals) for k consecutive matches
        return hasKConsecutive(board, symbol, k);
    }
}

This is Strategy Pattern applied to "what counts as a win" — Game, Board, and Player never need to know or care whether winning means three-in-a-row or four-in-a-row; they only ever call winningStrategy.checkWin(board, symbol). Supporting Connect-4 means writing one new WinningStrategy implementation and configuring Game with it — zero changes to Board, Player, or Game's own turn-management logic.

Extending to an N x N board

The design already supports this — Board's constructor already takes a size parameter, and ThreeInARowStrategy's row/column/diagonal scans are already written generically in terms of board.getSize(), not a hard-coded 3. The only assumption worth calling out explicitly: for tic-tac-toe specifically, a win condition of "N in a row on an N x N board" is a design choice, not a law of nature — a 5x5 board might reasonably still only require 3 (or 4) in a row to win, which would mean decoupling the win-length from the board size as two separate configuration values rather than assuming they're always equal.

O(1) win detection with line counters

Checking the whole board after each move costs O(n²) for an n × n board. There's a neat trick: a move can only complete lines that pass through the cell just played (its row, its column, and at most two diagonals). Keep a running count per line, and the check becomes O(1):

final class LineCounter {
    private final int n;
    private final int[] rows, cols;
    private int diag, antiDiag;

    LineCounter(int n) { this.n = n; rows = new int[n]; cols = new int[n]; }

    /** player: +1 for X, -1 for O. Returns true if this move completes a line. */
    boolean record(int r, int c, int player) {
        rows[r] += player;
        cols[c] += player;
        if (r == c) diag += player;
        if (r + c == n - 1) antiDiag += player;
        int target = player * n;
        return rows[r] == target || cols[c] == target || diag == target || antiDiag == target;
    }
}

A row sums to +n only if X holds every cell in it, since any O would subtract. This works for full-line wins on any n × n board with two players. It's a well-known interview optimization, and fits directly behind the WinningStrategy interface as an alternative implementation, without changing Game.

It doesn't directly handle "k in a row on a larger board" (Gomoku, Connect Four). For those, check outward from the last move in four directions (horizontal, vertical and both diagonals), counting consecutive matching symbols. That's O(k) per move:

boolean connectsK(Board b, int r, int c, char sym, int k) {
    int[][] dirs = {{0, 1}, {1, 0}, {1, 1}, {1, -1}};
    for (int[] d : dirs) {
        int count = 1 + countDir(b, r, c, d[0], d[1], sym) + countDir(b, r, c, -d[0], -d[1], sym);
        if (count >= k) return true;
    }
    return false;
}

private int countDir(Board b, int r, int c, int dr, int dc, char sym) {
    int count = 0;
    for (int i = r + dr, j = c + dc; b.inBounds(i, j) && b.get(i, j) == sym; i += dr, j += dc) count++;
    return count;
}

Validating moves and managing turns

The Game class owns the rules of turn-taking. Make illegal states unrepresentable, rather than trusting callers:

final class Game {
    private final Board board; private final List<Player> players; private final WinningStrategy wins;
    private int turn = 0; private int movesMade = 0;
    private GameState state = GameState.IN_PROGRESS; private Player winner;

    Game(Board board, List<Player> players, WinningStrategy wins) {
        this.board = board; this.players = List.copyOf(players); this.wins = wins;
    }

    MoveResult play(Player who, int r, int c) {
        if (state != GameState.IN_PROGRESS) return MoveResult.rejected("game is over");
        if (who != players.get(turn)) return MoveResult.rejected("not " + who.name() + "'s turn");
        if (!board.inBounds(r, c) || !board.isEmpty(r, c)) return MoveResult.rejected("invalid cell");

        board.place(r, c, who.symbol());
        movesMade++;
        if (wins.checkWin(board, r, c, who.symbol())) { state = GameState.WON; winner = who; }
        else if (movesMade == board.size() * board.size()) state = GameState.DRAW;
        else turn = (turn + 1) % players.size();                       // works for any number of players
        return MoveResult.accepted(state);
    }
}

• Return a result instead of throwing for expected invalid moves. Illegal input from a user isn't exceptional, and the UI needs a reason to display.
• Check the win using only the last move, as above, and pass its position to the strategy.
• turn = (turn + 1) % players.size() generalizes to 3+ players without any change.

Undo and a computer opponent

• Undo: record each move as a Command (Move(r, c, symbol)) on a stack. Undo clears the cell, restores the turn, and rolls back the counters. The counter approach makes that trivial: subtract the player's value.
• A computer player: for 3 × 3, minimax searches the whole game tree (at most 9! positions, far fewer with pruning) and plays perfectly. Model it as a MoveStrategy for a Player, so human, random and minimax players are interchangeable. For larger boards, depth-limited minimax with alpha-beta pruning and a heuristic evaluation is the standard approach.

Follow-up questions this topic invites — and their answers

Q: Why does checkWin() take the board and symbol as parameters instead of the strategy holding a reference to the board itself? A: Keeping WinningStrategy stateless (no board reference stored) means a single strategy instance can be reused across multiple concurrent games safely, and it makes the strategy trivially unit-testable in isolation by passing in any board configuration directly, without needing to construct a full Game first.

Q: How would you support a 3-player variant? A: The design already generalizes reasonably well — Game already holds a List<Player> and cycles through it via modulo, not a hard-coded two-player assumption. The larger design question a 3-player variant actually raises is what a 'win' even means with three competing symbols, which is a WinningStrategy concern, not a Game/Board concern.

Q: Is Board responsible for checking whether a move is legal beyond 'is this cell empty'? A: For tic-tac-toe, cell-occupancy is the only legality rule — but naming this explicitly matters, because a different board game (chess, say) would need move legality to depend on piece type and game rules far beyond simple occupancy, which is exactly the kind of complexity Chess Engine Design tackles separately as its own concern, not bolted onto a generic Board class.

Q: How can you detect a win in O(1) per move? A: Keep a running sum for each row, each column and both diagonals, adding +1 for one player and −1 for the other. After a move, only the lines through that cell can change. A line whose sum reaches ±n is complete.

Q: How would you support Connect Four using the same design? A: Swap the board (gravity: a move chooses a column, and the piece drops to the lowest empty cell) and the winning strategy (four in a row, checked outward from the last move). Game's turn handling and result reporting stay the same.

Q: How would you add undo? A: Store each move as a command on a history stack. Undo pops the last move, clears its cell, restores the previous player's turn and any win-tracking state, and sets the game back to in progress.