Design Tic-Tac-Toe (NxN) in Java

Tic-tac-toe is the smallest game that still exercises a full design: a board with invariants, a turn rule, a terminal state and interchangeable players. Interviewers usually follow the first version with "make it NxN" and "make the win check O(1)". This article designs for those follow-ups from the start, using the steps in the LLD interview framework.

Requirements

Functional

Two players, X and O, alternate turns. X moves first.
The board is N x N with N >= 3. A player wins by owning a full row, a full column or either main diagonal.
If every cell is filled and nobody has won, the game is a draw.
Illegal moves (outside the board, on an occupied cell, after the game ended) are rejected and change nothing.
A player can be a human, a scripted sequence or a bot. The game must not care which.

Non-functional and scope

Recording a move and detecting a win must cost O(1), not O(N).
Two players on one machine, no networking, no persistence, no undo (see the extensions).

Assumptions to state aloud: the win length equals N (not the "K in a row" variant), and coordinates are zero-based (row, col).

Entities

Nouns from the requirements: game, board, cell, mark, position, player, game state. Some become types and some become fields.

classDiagram
    class Game {
        -Board board
        -Player x
        -Player o
        +run() GameState
    }
    class Board {
        -Mark[] cells
        -int[] rows
        -int[] cols
        +place(Position) GameState
    }
    class Player {
        <<interface>>
        +nextMove(Board, Mark) Position
    }
    class Mark {
        <<enum>>
    }
    class GameState {
        <<sealed interface>>
    }
    Game *-- Board
    Game o-- Player
    Player <|.. ScriptedPlayer
    Player <|.. FirstFreeBot
    Board --> Mark
    Board --> GameState

Decisions visible in the diagram:

Mark is an enum and GameState is a sealed interface with record variants, because both sets are closed and the variants of GameState carry different data. A player is an interface because the set of players is open. See modeling domains in Java.
The board owns its state and the turn order. The Game only asks players for moves and forwards them, so all rules live in one place.
There is no Cell class. A cell is either empty or owned by a mark, so the board stores a Mark[] in which null means empty. The array is private, and the public get method returns an Optional<Mark>.

API

Java

Board(int size)                                  // throws IllegalArgumentException if size < 3
GameState Board.place(Position pos)              // throws IllegalMoveException
List<Position> Board.freePositions()
interface Player { Position nextMove(Board board, Mark mark); }
GameState Game.run()                             // throws IllegalMoveException

place takes no mark. The board knows whose turn it is, so a caller cannot move out of turn.

Design decisions

The game state is a sealed interface

The state is one of three situations, and the data differs per situation: an unfinished game has a next player, a won game has a winner, a draw has neither. A sealed interface lists exactly these variants, and a switch over it must cover all of them, with no default branch.

Java

public class Main {
    enum Mark {
        X, O;

        Mark other() {
            return this == X ? O : X;
        }
    }

    sealed interface GameState {
        record InProgress(Mark next) implements GameState {}
        record Won(Mark winner) implements GameState {}
        record Draw() implements GameState {}
    }

    static String describe(GameState state) {
        return switch (state) {
            case GameState.InProgress(Mark next) -> next + " to move";
            case GameState.Won(Mark winner) -> winner + " wins";
            case GameState.Draw() -> "draw";
        };
    }

    public static void main(String[] args) {
        var states = new GameState[] {
            new GameState.InProgress(Mark.X.other()),
            new GameState.Won(Mark.X),
            new GameState.Draw()
        };
        for (var s : states) {
            System.out.println(describe(s));
        }
    }
}

Output

O to move
X wins
draw

A class with a Mark winner field and a boolean finished field could hold a nonsense combination such as finished = false with a winner. The sealed type cannot. If a fourth variant is added later, every switch without a default stops compiling until it handles the new case. See state machines with sealed types.

O(1) win detection with line counters

The naive check scans the row, the column and possibly both diagonals after every move: O(N) per move. The counter approach keeps one running total per line and updates only the lines that the new cell belongs to.

Give X the weight +1 and O the weight -1. A line holds a sum. If the absolute value of a sum reaches N, then all N cells are owned by the same player, because a single opposite mark would reduce the magnitude. A cell (r, c) touches at most four counters: rows[r], cols[c], the main diagonal when r == c, and the anti-diagonal when r + c == N - 1.

Java

public class Main {
    static class Lines {
        private final int n;
        private final int[] rows;
        private final int[] cols;
        private int diag;
        private int anti;

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

        /** weight is +1 for X and -1 for O. Returns true if this move completes a line. */
        boolean record(int row, int col, int weight) {
            rows[row] += weight;
            cols[col] += weight;
            boolean hit = Math.abs(rows[row]) == n || Math.abs(cols[col]) == n;
            if (row == col) {
                diag += weight;
                hit |= Math.abs(diag) == n;
            }
            if (row + col == n - 1) {
                anti += weight;
                hit |= Math.abs(anti) == n;
            }
            return hit;
        }
    }

    public static void main(String[] args) {
        var lines = new Lines(3);
        // X plays the main diagonal, O plays elsewhere.
        int[][] moves = {{0, 0, 1}, {0, 1, -1}, {1, 1, 1}, {0, 2, -1}, {2, 2, 1}};
        for (var m : moves) {
            boolean won = lines.record(m[0], m[1], m[2]);
            System.out.println("(%d,%d) weight %+d -> win %b".formatted(m[0], m[1], m[2], won));
        }
    }
}

Output

(0,0) weight +1 -> win false
(0,1) weight -1 -> win false
(1,1) weight +1 -> win false
(0,2) weight -1 -> win false
(2,2) weight +1 -> win true

The cost is O(N) memory for the counters and O(1) time per move. The check is only valid right after a move, and it only needs to examine that move's lines, since no other line changed.

Checking the counters against a brute-force scan

A clever check deserves a cross-check. The next program plays many pseudo-random legal games on a 5x5 board. After each move it compares the counter result with a full scan of the grid. It uses a Random with a fixed seed, so the games are the same on every run.

Java

import java.util.ArrayList;
import java.util.Random;

public class Main {
    static final int N = 5;

    static boolean scanWins(int[][] grid, int row, int col) {
        int w = grid[row][col];
        boolean rowFull = true, colFull = true, diagFull = row == col, antiFull = row + col == N - 1;
        for (int i = 0; i < N; i++) {
            rowFull &= grid[row][i] == w;
            colFull &= grid[i][col] == w;
            diagFull &= grid[i][i] == w;
            antiFull &= grid[i][N - 1 - i] == w;
        }
        return rowFull || colFull || diagFull || antiFull;
    }

    public static void main(String[] args) {
        var random = new Random(12345);
        int wins = 0, mismatches = 0;
        for (int game = 0; game < 2000; game++) {
            var grid = new int[N][N];
            var rows = new int[N];
            var cols = new int[N];
            int diag = 0, anti = 0;
            var free = new ArrayList<int[]>();
            for (int i = 0; i < N * N; i++) {
                free.add(new int[] {i / N, i % N});
            }
            int w = 1;
            while (!free.isEmpty()) {
                var cell = free.remove(random.nextInt(free.size()));
                int r = cell[0], c = cell[1];
                grid[r][c] = w;
                rows[r] += w;
                cols[c] += w;
                boolean fast = Math.abs(rows[r]) == N || Math.abs(cols[c]) == N;
                if (r == c) {
                    diag += w;
                    fast |= Math.abs(diag) == N;
                }
                if (r + c == N - 1) {
                    anti += w;
                    fast |= Math.abs(anti) == N;
                }
                boolean slow = scanWins(grid, r, c);
                if (fast != slow) {
                    mismatches++;
                }
                if (slow) {
                    wins++;
                    break;
                }
                w = -w;
            }
        }
        System.out.println("games 2000, decided by a win " + wins + ", mismatches " + mismatches);
    }
}

Output

games 2000, decided by a win 806, mismatches 0

Zero mismatches means the counters agree with the definition on every move of every game. The scan is O(N) per move and is correct by inspection, which is why it works as the reference.

Players are an interface, and moves are always validated

Player is open behavior: a human reading stdin, a network client, a minimax bot. The game holds one Player reference for each side. The interface method receives the Board so a bot can look at the cells. Java has no read-only reference, so a bot could also call place itself. The contract says it must not, and a read-only interface that Board implements (for example BoardView) would close that gap. The game validates whatever comes back from nextMove: a misbehaving bot causes an IllegalMoveException, not a corrupted board.

Validation and errors

The constructor validates N >= 3 with an IllegalArgumentException, the standard signal for a bad argument. place rejects out-of-bounds cells, occupied cells and moves after the game ended, and it checks all three before changing anything. These failures use an unchecked IllegalMoveException that carries a reason from the MoveError enum. Unchecked is the choice because a player returning an illegal move is a caller bug that the game loop does not recover from, and a checked exception would spread through the Player interface. See errors in domain design.

Full implementation

Java

import java.util.ArrayList;
import java.util.List;
import java.util.Objects;
import java.util.Optional;

enum Mark {
    X, O;

    Mark other() {
        return this == X ? O : X;
    }

    int weight() {
        return this == X ? 1 : -1;
    }
}

record Position(int row, int col) {}

sealed interface GameState {
    record InProgress(Mark next) implements GameState {}
    record Won(Mark winner) implements GameState {}
    record Draw() implements GameState {}
}

enum MoveError { GAME_OVER, OUT_OF_BOUNDS, OCCUPIED }

class IllegalMoveException extends RuntimeException {
    private final MoveError error;

    IllegalMoveException(MoveError error, Position pos) {
        super("illegal move %s at (%d, %d)".formatted(error, pos.row(), pos.col()));
        this.error = error;
    }

    MoveError error() {
        return error;
    }
}

class Board {
    private final int size;
    private final Mark[] cells; // null means empty; never exposed
    private final int[] rows;
    private final int[] cols;
    private int diag;
    private int anti;
    private int filled;
    private GameState state = new GameState.InProgress(Mark.X);

    Board(int size) {
        if (size < 3) {
            throw new IllegalArgumentException("board size %d is below the minimum of 3".formatted(size));
        }
        this.size = size;
        this.cells = new Mark[size * size];
        this.rows = new int[size];
        this.cols = new int[size];
    }

    int size() {
        return size;
    }

    GameState state() {
        return state;
    }

    Optional<Mark> get(Position pos) {
        if (pos.row() < 0 || pos.row() >= size || pos.col() < 0 || pos.col() >= size) {
            return Optional.empty();
        }
        return Optional.ofNullable(cells[pos.row() * size + pos.col()]);
    }

    List<Position> freePositions() {
        var free = new ArrayList<Position>();
        for (int row = 0; row < size; row++) {
            for (int col = 0; col < size; col++) {
                if (cells[row * size + col] == null) {
                    free.add(new Position(row, col));
                }
            }
        }
        return free;
    }

    /** Places the mark of the player whose turn it is. O(1). */
    GameState place(Position pos) {
        Objects.requireNonNull(pos);
        if (!(state instanceof GameState.InProgress(Mark mark))) {
            throw new IllegalMoveException(MoveError.GAME_OVER, pos);
        }
        if (pos.row() < 0 || pos.row() >= size || pos.col() < 0 || pos.col() >= size) {
            throw new IllegalMoveException(MoveError.OUT_OF_BOUNDS, pos);
        }
        int idx = pos.row() * size + pos.col();
        if (cells[idx] != null) {
            throw new IllegalMoveException(MoveError.OCCUPIED, pos);
        }

        cells[idx] = mark;
        filled++;
        int w = mark.weight();
        rows[pos.row()] += w;
        cols[pos.col()] += w;
        boolean won = Math.abs(rows[pos.row()]) == size || Math.abs(cols[pos.col()]) == size;
        if (pos.row() == pos.col()) {
            diag += w;
            won |= Math.abs(diag) == size;
        }
        if (pos.row() + pos.col() == size - 1) {
            anti += w;
            won |= Math.abs(anti) == size;
        }

        if (won) {
            state = new GameState.Won(mark);
        } else if (filled == size * size) {
            state = new GameState.Draw();
        } else {
            state = new GameState.InProgress(mark.other());
        }
        return state;
    }

    @Override
    public String toString() {
        var sb = new StringBuilder();
        for (int row = 0; row < size; row++) {
            for (int col = 0; col < size; col++) {
                if (col > 0) {
                    sb.append(' ');
                }
                var mark = cells[row * size + col];
                sb.append(mark == null ? "." : mark.toString());
            }
            sb.append('\n');
        }
        return sb.toString();
    }
}

interface Player {
    String name();

    Position nextMove(Board board, Mark mark);
}

/** Plays a fixed list of (row, col) moves. */
class ScriptedPlayer implements Player {
    private final String label;
    private final List<Position> moves;
    private int next;

    ScriptedPlayer(String label, List<Position> moves) {
        this.label = label;
        this.moves = List.copyOf(moves);
    }

    @Override
    public String name() {
        return label;
    }

    @Override
    public Position nextMove(Board board, Mark mark) {
        if (next >= moves.size()) {
            throw new IllegalStateException("script ran out of moves");
        }
        return moves.get(next++);
    }
}

/** A bot that always takes the first free cell in row-major order. */
class FirstFreeBot implements Player {
    @Override
    public String name() {
        return "first-free-bot";
    }

    @Override
    public Position nextMove(Board board, Mark mark) {
        return board.freePositions().getFirst();
    }
}

class Game {
    private final Board board;
    private final Player x;
    private final Player o;

    Game(int size, Player x, Player o) {
        this.board = new Board(size);
        this.x = Objects.requireNonNull(x);
        this.o = Objects.requireNonNull(o);
    }

    Board board() {
        return board;
    }

    GameState run() {
        while (board.state() instanceof GameState.InProgress(Mark next)) {
            Player player = next == Mark.X ? x : o;
            Position pos = player.nextMove(board, next);
            System.out.println("%s (%s) plays (%d, %d)".formatted(player.name(), next, pos.row(), pos.col()));
            board.place(pos);
        }
        return board.state();
    }
}

public class Main {
    static Position at(int row, int col) {
        return new Position(row, col);
    }

    public static void main(String[] args) {
        // 1. Two bots on 3x3: X takes the first free cells.
        var game = new Game(3, new FirstFreeBot(), new FirstFreeBot());
        var result = game.run();
        System.out.print(game.board());
        System.out.println("result: " + result + "\n");

        // 2. A scripted 4x4 game: O wins the second column.
        var x = new ScriptedPlayer("alice", List.of(at(0, 0), at(2, 2), at(3, 3), at(0, 3)));
        var o = new ScriptedPlayer("bob", List.of(at(0, 1), at(1, 1), at(2, 1), at(3, 1)));
        game = new Game(4, x, o);
        result = game.run();
        System.out.print(game.board());
        System.out.println("result: " + result + "\n");

        // 3. Rejected moves leave the board unchanged.
        var board = new Board(3);
        board.place(at(1, 1));
        for (var bad : List.of(at(1, 1), at(3, 0))) {
            try {
                board.place(bad);
            } catch (IllegalMoveException e) {
                System.out.println(e.getMessage());
            }
        }
        System.out.println("state after errors: " + board.state());

        // 4. A draw on 3x3.
        int[][] drawMoves = {{0, 0}, {0, 1}, {0, 2}, {1, 1}, {1, 0}, {1, 2}, {2, 1}, {2, 0}, {2, 2}};
        board = new Board(3);
        for (var m : drawMoves) {
            board.place(at(m[0], m[1]));
        }
        System.out.println("final: " + board.state());
        try {
            board.place(at(0, 0));
        } catch (IllegalMoveException e) {
            System.out.println("after game over: " + e.error());
        }

        // 5. Setup validation.
        try {
            new Board(2);
        } catch (IllegalArgumentException e) {
            System.out.println(e.getMessage());
        }
    }
}

Output

first-free-bot (X) plays (0, 0)
first-free-bot (O) plays (0, 1)
first-free-bot (X) plays (0, 2)
first-free-bot (O) plays (1, 0)
first-free-bot (X) plays (1, 1)
first-free-bot (O) plays (1, 2)
first-free-bot (X) plays (2, 0)
X O X
O X O
X . .
result: Won[winner=X]

alice (X) plays (0, 0)
bob (O) plays (0, 1)
alice (X) plays (2, 2)
bob (O) plays (1, 1)
alice (X) plays (3, 3)
bob (O) plays (2, 1)
alice (X) plays (0, 3)
bob (O) plays (3, 1)
X O . X
. O . .
. O X .
. O . X
result: Won[winner=O]

illegal move OCCUPIED at (1, 1)
illegal move OUT_OF_BOUNDS at (3, 0)
state after errors: InProgress[next=O]
final: Draw[]
after game over: GAME_OVER
board size 2 is below the minimum of 3

The three properties to point out: place validates before it mutates, so an exception never leaves half an update; the win check reads only four counters; and Game.run never trusts a player, since every move passes through Board.place.

Extensions

Follow-up	Change
Undo	Store the move history in a `Deque<Position>`. Undo clears the cell, subtracts the weight from the same four counters, and restores the state. Counters are reversible, which a scan-based design does not need but a cached-winner design would.
K in a row on a larger board	The counter trick no longer works, because a line can be longer than K. Scan outward from the last move in the four directions and count consecutive marks: O(K) per move.
Smarter bot	Add a `MinimaxBot` implementing `Player`. It needs a copy of the board to explore moves, so add a copy constructor to `Board`. Nothing else changes, which is the payoff of the interface.
More than two players	Replace `Mark` weights with per-player counters, for example an `int[][]` indexed by player and line. The `+1/-1` sum trick is specific to two players.
Human input	A `ConsolePlayer` reads stdin, and on an invalid move the game reports the error and asks again. Retry logic belongs in the game loop, not the board.
Networked play	`nextMove` becomes asynchronous (for example it returns a `CompletableFuture<Position>`); the testability approach of injecting the player keeps the core unchanged.

Interview points

Closed sets (mark, game state, move errors) are enums or sealed types. Open behavior (player) is an interface.
The board owns the rules and the turn order, so no caller can move out of turn or skip validation.
One signed counter per row, column and both diagonals gives O(1) detection with O(N) memory. The +1/-1 trick holds for two players only.
Validation happens before mutation, so a rejected move changes nothing.
A fast algorithm is checked against a simple scan on many seeded random games.

Summary

Model closed sets (mark, game state, errors) as enums and sealed types and open behavior (player) as an interface.
The board owns the rules and the turn order, so no caller can move out of turn or skip validation.
Track one signed counter per row, column and both diagonals. A move updates at most four counters and a line is won when its magnitude reaches N, giving O(1) detection.
Validate before mutating, and signal a bad move with a domain exception carrying a reason.
Cross-check a clever algorithm against a simple one on many generated inputs.
The Player interface lets scripted players, bots and humans share one game loop without changes to the core.