Tic Tac Toe: win detection in code and extensions

With the win check placed on Board, the satisfying part of this problem is making it fast. This lesson writes it three ways — each faster and no longer than the last — and then works through the follow-ups, every one of which tests whether the earlier decisions were really general.

Win detection, in code

The satisfying part of this problem. Write the naive version, show what it costs, then replace it with something that is both faster and shorter.

The naive version: rescan everything

1public boolean hasWinner() {2    for (int r = 0; r < n; r++)                          // rows3        if (allSame(grid[r])) return true;4    for (int c = 0; c < n; c++)                          // columns5        if (allSame(column(c))) return true;6    return allSame(mainDiagonal()) || allSame(antiDiagonal());7}

For 3×3 this is correct and costs about 24 cell reads per move. Nobody would improve it.

For a 15×15 board with K=5 it becomes badly wrong in two ways. It reads roughly 900 cells per move, and — more importantly — it is not even correct, because with K < N a win is any run of K in a row anywhere, not a full line. The general version needs to scan every window of K cells in every row, column, and both diagonal directions: hundreds of windows per move.

The insight

A win can only involve the cell that was just played. Nothing else on the board changed.

So instead of asking "is there a winning line anywhere?", ask "did this move complete a line?" That reduces the work from the whole board to four directions through one cell.

Version two: check four directions through the last move

1private static final int[][] DIRECTIONS = {{0,1}, {1,0}, {1,1}, {1,-1}};  // →, ↓, ↘, ↙23public boolean isWinningMove(int row, int col) {4    Piece piece = grid[row][col];5    for (int[] d : DIRECTIONS) {6        int count = 17            + countInDirection(row, col, d[0], d[1], piece)      // one way8            + countInDirection(row, col, -d[0], -d[1], piece);   // and back9        if (count >= k) return true;10    }11    return false;12}1314private int countInDirection(int row, int col, int dr, int dc, Piece piece) {15    int count = 0;16    int r = row + dr, c = col + dc;17    while (r >= 0 && r < n && c >= 0 && c < n && grid[r][c] == piece) {18        count++; r += dr; c += dc;19    }20    return count;21}

Cost per move: at most 4 × 2 × K cell reads. For K=5 that is about 40 reads instead of several hundred, it handles any N and any K, and it is fifteen lines. For most interviews this is the right place to stop — it is correct, general, and clearly better than the scan.

Version three: O(1) with counters, for the full-line case

When K equals N — the classic rule, a full row, column, or diagonal — you can do better still. Keep a running count per line instead of reading cells at all.

1public class Board {2    private final int[] rowScore, colScore;      // +1 for X, -1 for O3    private int diagScore, antiDiagScore;45    public boolean recordMove(int row, int col, Piece piece) {6        grid[row][col] = piece;7        int delta = (piece == Piece.X) ? 1 : -1;89        rowScore[row] += delta;10        colScore[col] += delta;11        if (row == col)            diagScore     += delta;12        if (row + col == n - 1)    antiDiagScore += delta;1314        return Math.abs(rowScore[row])  == n15            || Math.abs(colScore[col])  == n16            || Math.abs(diagScore)      == n17            || Math.abs(antiDiagScore)  == n;18    }19}

Four additions and four comparisons per move, regardless of board size. A line reaches ±N only when all N of its cells hold the same piece, because each X adds one and each O subtracts one — mixed lines can never reach the magnitude.

The honest limits of version three

Say these out loud; they are what makes the answer look considered rather than memorised:

• It only works when K = N. Counting a whole line cannot express "five in a row somewhere in a fifteen-wide row". For K < N, use version two.
• Undo must decrement the counters. A move stack that only restores the grid leaves the counters wrong, and the bug appears several moves later — a genuinely nasty one.
• It assumes exactly two pieces. The +1/−1 trick breaks with three players; you would need a count per piece per line.

Extensions

1. N×N boards and K in a row

Already handled if you took the advice in The problem, and the questions to ask: N and K are constructor parameters, the win check is the four-direction walk, and the same class plays 3×3 tic tac toe and 19×19 Gomoku with no changes.

If your attempt hard-coded 3, this is the extension the interviewer will ask for, and the answer is a rewrite of the win check rather than a parameter. That is the cost of hard-coding, and it is worth feeling once.

2. A computer player behind a Strategy interface

The move that makes bots and humans interchangeable:

1public interface MoveStrategy {2    Move chooseMove(BoardView board, Piece piece);   // BoardView is read-only3}45public class RandomStrategy implements MoveStrategy {6    public Move chooseMove(BoardView board, Piece piece) {7        List<Position> empty = board.emptyPositions();8        return new Move(empty.get(random.nextInt(empty.size())), piece);9    }10}

BoardView being read-only is the detail worth pointing out: a bot is asked what it would do and cannot change anything. That is the same "player decides, game applies" separation as in Finding the objects, now enforced by the type.

Minimax, the perfect-play strategy, is another implementation of the same interface: try every legal move, recurse assuming the opponent plays optimally, and take the best outcome. For 3×3 the game tree is small enough to search exhaustively — at most 9! = 362,880 orderings, and far fewer in practice with early termination. For a 15×15 board it is hopeless without depth limits and a heuristic, which is worth saying because it shows you know where the approach stops working.

The design point is that neither bot changes Game. That is requirement N2 satisfied.

3. Undo via a move stack

1public class Game {2    private final Deque<Move> history = new ArrayDeque<>();34    public void undo() {5        if (history.isEmpty()) throw new NothingToUndoException();6        Move last = history.pop();7        board.remove(last.getRow(), last.getCol());   // must also decrement counters8        currentPlayer = last.getPlayer();9        status = GameStatus.IN_PROGRESS;              // a finished game becomes live again10    }11}

Three things to say while writing it:

• The per-line counters from version three above must be decremented, or the board's summary drifts from its grid.
• Undoing a winning move must reopen the game, which means status is derived state that undo has to restore.
• This is the Command pattern in embryo (The seven patterns that actually appear). If moves gained variety — place, swap, pass — each becoming a Command with execute and undo would be the right step. With one kind of move, a Move record on a stack is enough, and saying that is better than adding the pattern.

4. Generalising to Connect Four

An excellent final question, because the answer reveals whether your model was really general.

Connect Four is an N×M board, K=4, with gravity: you choose a column and the piece falls to the lowest empty row. Almost everything transfers:

The single change is in move placement:

1public int dropInColumn(int col, Piece piece) {2    for (int row = rows - 1; row >= 0; row--) {        // from the bottom up3        if (grid[row][col] == null) { grid[row][col] = piece; return row; }4    }5    throw new ColumnFullException(col);6}

One new method and a different validation rule. If your design needs more than that, the win check was tied to the board size or the move was tied to a cell rather than to a placement rule — and that diagnosis is worth saying out loud.