CSE Roadmap

Core tier · about 3 hours · 6 parts

Part 4 of 6 · 4 min read

The code

Place a mark and detect a win in one step.

The simple way to detect a win is to scan the row, column and diagonals after each move. That works. A faster way keeps a count for each line and mark.

class Board {
    private final int n; private final Mark[][] cells;
    private final int[][] rows, cols;            // rows[mark][r], cols[mark][c]
    private final int[] diag, anti;              // per mark
    private int filled;

    Board(int n) {
        if (n < 3) throw new IllegalArgumentException("n >= 3");
        this.n = n; cells = new Mark[n][n];
        rows = new int[2][n]; cols = new int[2][n]; diag = new int[2]; anti = new int[2];
    }

    boolean place(int r, int c, Mark m) {         // true if this move completes a line
        cells[r][c] = m; filled++;
        int k = m.ordinal();
        rows[k][r]++; cols[k][c]++;
        if (r == c)         diag[k]++;
        if (r + c == n - 1) anti[k]++;
        return rows[k][r] == n || cols[k][c] == n || diag[k] == n || anti[k] == n;
    }
    // inBounds, isEmpty, isFull, size omitted
}

Each move adds one to a row count, a column count and possibly two diagonal counts. A line is complete when its count reaches n. The work per move is constant, whatever the board size. A scan would cost about n steps per line.

The game applies the rules in a fixed order and changes state only after every check has passed (the failure atomicity of Level 5, module 1).

class Game {
    private final Board board;
    private Mark turn = Mark.X; private Status status = Status.IN_PROGRESS; private Mark winner;

    void play(int r, int c) throws InvalidMoveException {
        if (status != Status.IN_PROGRESS) throw new InvalidMoveException("game is over");
        if (!board.inBounds(r, c))        throw new InvalidMoveException("off the board");
        if (!board.isEmpty(r, c))         throw new InvalidMoveException("cell taken");
        boolean won = board.place(r, c, turn);
        if (won)                  { status = Status.WON; winner = turn; }
        else if (board.isFull())  status = Status.DRAW;
        else                      turn = (turn == Mark.X) ? Mark.O : Mark.X;
    }
}

The turn changes only when the game goes on. Out-of-turn moves cannot occur, because the game only accepts a move for whoever's turn it is.

A run on a 3 by 3 board:

Moves in order (row, column) Result
X(0,0) O(1,0) X(0,1) O(1,1) X(0,2) X wins on row 0
X(0,0) O(0,1) X(1,1) O(0,2) X(2,2) X wins on the diagonal
X(0,2) O(0,0) X(1,1) O(0,1) X(2,0) X wins on the other diagonal
Nine moves that fill the board with no line Draw
X(0,0) then O(0,0) "cell taken", the game goes on
X(3,0) "off the board"
A sixth move after X wins "game is over"
On a 4 by 4 board, X fills row 0 X wins, with the same code

The last line shows requirement R6 working: the same classes handle any size from 3 up.

A computer player needs only a MoveSource. The simplest one takes the first empty cell.

interface MoveSource { int[] next(Board b, Mark me); }
class FirstFree implements MoveSource {
    public int[] next(Board b, Mark me) {
        for (int r = 0; r < b.size(); r++)
            for (int c = 0; c < b.size(); c++)
                if (b.isEmpty(r, c)) return new int[]{r, c};
        throw new IllegalStateException("full");
    }
}

Two such bots playing each other end with X winning on the second diagonal after seven moves. A smarter bot is a new class and nothing else changes.

Constant time

An action takes constant time when its cost does not grow with the size of the input.

Example: the counter win check, which does the same few steps on a 3 by 3 or a 100 by 100 board.

Check yourself: 1. How many counters change when a mark is placed at the centre of a 3 by 3 board? 2. Why does turn change only in the last branch? 3. What does a new bot need to implement?