Tic-Tac-Toe

Design an N by N tic-tac-toe where K marks in a row win, with a computer player you can plug in and a win check that does not scan the board. A small problem that tests how you split rules from data.

Design a tic-tac-toe game. The board is N by N, and a player wins with K of their marks in a row. Two players take turns. Either player can be a computer. After each move, tell the caller whether the game goes on, was won or is a draw. Show how you find a win without scanning the whole board.

Questions to ask first

How big is the board, and how many marks win? Assume any N from 3 upward and any K from 1 up to N. The classic game is N = 3 and K = 3.
Who moves first? Assume X always moves first and the players take turns after that.
Is a computer player needed now? Assume yes, as a pluggable idea: a player is either a human whose moves arrive from outside, or a computer that picks its own move. The first computer rule is simple.
Does the row have to be unbroken? Assume yes. K marks side by side along a row, a column or a diagonal.
What happens on a bad move, such as a taken cell or a cell outside the board? Assume the game refuses it with a clear reason and the same player tries again.
Do we need undo, a score board or a network game? Assume none of them now. Undo is a likely follow-up, so leave room for it.

Requirements

Start a game with the board size N, the winning length K, and a kind (human or computer) for each of the two players.
Accept a move at a row and column for the player whose turn it is, and refuse it if the cell is taken, outside the board, or the game is over.
Report the result of every accepted move: the game goes on, a player won, or the board is full with no winner (a draw).
Let a computer player choose its own move through a rule that can be swapped for a smarter one without editing the game.
Find a win in constant time per move when a full line wins, and in time that depends only on K, not on the board size, when fewer marks win.

Out of scope

A screen, a console loop or any user interface (the game is a class that a front end calls).
Networking and more than two players.
A strong computer opponent. The first rule picks the first empty cell.
Saving finished games.

Entities

Game: the turn order and the result; play(row, col), playComputerTurn(), undo()
Board: the grid of marks; place(mark, row, col), isEmpty(row, col), isFull()
Mark: X or O, an enum
Player: a mark and, for a computer, a MoveStrategy
MoveStrategy: choose(board, mark), the rule a computer uses to pick a cell
WinChecker: placed(board, mark, row, col) tells whether the move just made wins
CounterWinChecker and LineScanWinChecker: two ways to answer that question
Move: a row and a column, a small immutable record
GameStatus: IN_PROGRESS, WON or DRAW

Classes in the model design

Game (class)
Board (class)
Mark (enum)
GameStatus (enum)
Player (class)
MoveStrategy (interface)
FirstFreeStrategy (class)
WinChecker (interface)
CounterWinChecker (class)
LineScanWinChecker (class)
Move (class)

The main use case, step by step

The caller starts a 5 by 5 game where 4 in a row wins. `Game` builds a `Board`, two `Player` objects and a `WinChecker`. Because K is not equal to N, it picks `LineScanWinChecker`. With K equal to N it would pick `CounterWinChecker`.
The caller sends `play(1, 0)`. `Game` first checks that the cell is on the board and empty. A bad cell is refused here, before anything changes, and the turn stays with the same player.
`Game` asks `current()` for the player whose turn it is, and tells `Board` to place that player's mark. It pushes the `Move` on the history stack so a later undo can find it.
`Game` calls `checker.placed(board, mark, 1, 0)`. The checker looks only at lines through that one cell, and answers true or false. The checker never scans the whole board.
If the answer is true, the status becomes WON and the winner is that mark. If the board is full, the status becomes DRAW. Otherwise the turn passes to the other player and the result is OK.
When it is a computer's turn, the caller calls `playComputerTurn()`. `Game` asks the player's `MoveStrategy` for a `Move` and then runs the same `play` path. A computer move is checked exactly like a human move.

Patterns used

Strategy (the computer player): MoveStrategy with FirstFreeStrategy, held by a computer Player.. How a computer chooses a cell changes often: first free, win or block, or search. With an interface, a smarter player is one new class, and Game does not change.
Strategy (win detection): WinChecker with CounterWinChecker and LineScanWinChecker, chosen once in the Game constructor.. There are two correct ways to find a win, with different limits. Game picks one by comparing K with N and then asks the same question on every move.
Separation of responsibilities: Board stores marks, Game owns turns and results, WinChecker owns the winning rule.. A change to the winning rule, such as diagonals not counting, touches one class. A Board that also knew the rules would need edits for every variant.

Key code

Players, the move strategy and the win checker interface

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

public record Move(int row, int col) { }

/** How a computer picks its cell. A human player has no strategy. */
public interface MoveStrategy {
    Move choose(Board board, Mark me);
}

public final class FirstFreeStrategy implements MoveStrategy {
    @Override
    public Move choose(Board board, Mark me) {
        for (int r = 0; r < board.size(); r++)
            for (int c = 0; c < board.size(); c++)
                if (board.isEmpty(r, c)) return new Move(r, c);
        throw new IllegalStateException("board is full");
    }
}

public interface WinChecker {
    /** Called once after each placed mark. True if that mark now completes a winning line. */
    boolean placed(Board board, Mark mark, int row, int col);
    /** Called when a move is undone. */
    void removed(Mark mark, int row, int col);
}

CounterWinChecker: one counter per line, O(1) per move

public final class CounterWinChecker implements WinChecker {
    private final int n;
    private final int[][] rows;                     // rows[player][row]
    private final int[][] cols;                     // cols[player][col]
    private final int[] diagonal = new int[2];      // top left to bottom right
    private final int[] anti = new int[2];          // top right to bottom left

    public CounterWinChecker(int n) {
        this.n = n;
        this.rows = new int[2][n];
        this.cols = new int[2][n];
    }

    @Override
    public boolean placed(Board board, Mark mark, int r, int c) {
        int p = mark.ordinal();
        boolean won = ++rows[p][r] == n;            // this cell is in exactly one row
        won |= ++cols[p][c] == n;                   // and one column
        if (r == c) won |= ++diagonal[p] == n;      // and maybe the main diagonal
        if (r + c == n - 1) won |= ++anti[p] == n;  // and maybe the other diagonal
        return won;
    }

    @Override
    public void removed(Mark mark, int r, int c) {
        int p = mark.ordinal();
        rows[p][r]--;
        cols[p][c]--;
        if (r == c) diagonal[p]--;
        if (r + c == n - 1) anti[p]--;
    }
}

LineScanWinChecker (any K) and Game.play

public final class LineScanWinChecker implements WinChecker {
    private static final int[][] DIRECTIONS = {{0, 1}, {1, 0}, {1, 1}, {1, -1}};
    private final int k;

    public LineScanWinChecker(int k) { this.k = k; }

    @Override
    public boolean placed(Board board, Mark mark, int r, int c) {
        for (int[] d : DIRECTIONS) {
            int run = 1 + count(board, mark, r, c, d[0], d[1]) + count(board, mark, r, c, -d[0], -d[1]);
            if (run >= k) return true;
        }
        return false;
    }

    /** Marks of the same player next to (r, c) in one direction, at most k - 1 of them. */
    private int count(Board board, Mark mark, int r, int c, int dr, int dc) {
        int count = 0;
        for (r += dr, c += dc; count < k - 1 && board.inBounds(r, c) && board.at(r, c) == mark; r += dr, c += dc) count++;
        return count;
    }

    @Override
    public void removed(Mark mark, int row, int col) { }   // nothing stored, nothing to undo
}

// inside Game
public MoveResult play(int row, int col) {
    if (!board.inBounds(row, col)) return MoveResult.OUT_OF_BOUNDS;
    if (!board.isEmpty(row, col)) return MoveResult.OCCUPIED;
    Mark mark = current().mark();
    board.place(mark, row, col);
    history.push(new Move(row, col));
    if (checker.placed(board, mark, row, col)) { status = GameStatus.WON; winner = mark; return MoveResult.WIN; }
    if (board.isFull()) { status = GameStatus.DRAW; return MoveResult.DRAW; }
    turn = 1 - turn;
    return MoveResult.OK;
}

Deep dives

Finding a win without scanning the board

Weak: After every move, look at every row, every column and both diagonals of the whole board. On an N by N board that is about N squared cell reads per move. For 3 by 3 it is instant, but the interviewer will ask what happens at 1,000 by 1,000.

Good: Look only at the four lines that pass through the cell just played: its row, its column and its two diagonals. Walk outward in each direction while the marks match, and stop after K minus 1 cells. This takes at most 4 times (K minus 1) reads per move, so it depends on K and not on the board size. It works for any K. This is LineScanWinChecker.

Great: When a full line wins (K equals N), keep one counter per row, per column and for the two diagonals, for each player. A move adds 1 to its row counter, its column counter, and the diagonal counters if it sits on them: at most 4 additions. A counter that reaches N means that player holds a whole line. This is O(1) per move and needs about 2N + 2 integers per player. Only these counters can change, because a cell belongs to exactly one row, one column and at most two diagonals. This is CounterWinChecker.

Why counters fail when K is less than N: With N = 5 and K = 4, the row XX.XX holds four X marks, so its counter says 4, but there is no run of four. A counter counts marks and not neighbours. For K less than N use the line scan. Say this out loud: it shows you know where the trick stops working.

Trade-off: Counters are the fastest and the answer interviewers expect for the classic game, but they hold state that undo must reverse. The scan holds no state, is correct for every K, and costs a few reads. Hide both behind WinChecker and choose in the Game constructor.

Plugging in a computer player

Weak: An if (player.isComputer()) block inside Game that picks a cell with its own loop. The computer rule lives inside Game, so a smarter computer edits Game and can break the turn logic.

Good: A MoveStrategy interface and a FirstFreeStrategy class. A computer Player holds a strategy, and Game asks it for a Move. A new computer is a new class. A human is a Player with no strategy, whose moves arrive from the caller.

Great: Game never trusts the strategy. It runs the strategy's Move through the same play method as a human move, so a computer that returns a taken cell is refused exactly like a person would be. Give the strategy a read-only view of the board, so it can look but not place marks. A test can then pass a strategy that returns a fixed list of moves, which makes computer games repeatable.

Trade-off: A null strategy for humans is the least code. If your game has a console loop, a HumanStrategy that reads input makes every player look the same to Game, at the cost of a blocking call inside the strategy. Choose by who drives the loop: the caller, or the game.

Undo

Weak: Copy the whole board after each move and restore the copy on undo. That costs N squared memory per move, and the win counters, the turn and the status are not restored, so the game is wrong after the first undo.

Good: Keep a stack of moves. Undo pops the last move, clears that cell, flips the turn back and resets the status. Every piece of state that a move changed must be changed back: this is why WinChecker has a removed method that subtracts the same counters that placed added.

Great: Make each move an object that knows how to apply and how to revert itself. This is the command pattern. The same object then gives you redo for free, and a log of moves that can replay a game. A move after an undo clears the redo stack.

Trade-off: A stack of plain moves is enough for undo and simple to test. Command objects cost a class and give redo and replay. Offer the stack first and mention commands when the interviewer asks for redo.

Now add one more feature

Now add undo. Game keeps a stack of moves. `undo()` pops one, clears the cell, calls `checker.removed` so the counters go back, flips the turn and sets the status to IN_PROGRESS. Undo after a win must not flip the turn, because the turn was never passed.
Now add a smarter computer. Write `SmartStrategy`: play a cell that wins at once, else a cell that blocks the opponent from winning, else the first empty cell. Give the player this strategy. Game, Board and the checkers do not change.
Now allow three or four players. Replace the `Mark` enum with a player index or a longer enum. The counters become `int[players][n]`, and the turn moves with `(turn + 1) % players`. The win rule is unchanged.
Now show the game on a screen and keep a scoreboard. Game publishes events (a move was made, the game ended) to listeners. A screen and a scoreboard subscribe, so Game does not know that either exists. This is the observer pattern.

What each level is expected to show

SDE-1: Clean classes for Game, Board, Player and Mark, a refusal for every bad move, and a win check that looks only at lines through the new cell. A working computer player behind an interface. Can explain why scanning the whole board is wasteful.

SDE-2: All of SDE-1, plus the counter method with its O(1) cost and the reason it fails when K is less than N, with the line scan as the general answer. Undo that reverses every counter. Treats a computer move like a human move so that one code path checks both.

Common mistakes

Scanning the whole board for a win after every move, and then having no answer when asked about a 1,000 by 1,000 board.
Using row and column counters when K is less than N. A row with K marks that are not side by side is not a win.
Putting the winning rule inside Board, so Board needs edits for every rule change. Board should only store marks.
Letting a computer move skip the checks of a human move, so a bad strategy can overwrite a mark or play after the game ended.
Passing the turn on a refused move. A taken cell or a cell outside the board must leave the same player to move.
Forgetting to undo the counters, the turn and the status together, so the game is wrong after the first undo.
Checking for a draw before checking for a win, so a win on the last cell is reported as a draw.