Tic-Tac-Toe

import java.util.*;

enum Piece {
    X(+1), O(-1);
    final int value;                       // +1 / -1 is what makes one counter per line enough
    Piece(int value) { this.value = value; }
}

record Player(String name, Piece piece) {}

/** A fact about the past — immutable, which is what gives us undo and replay. */
record Move(int row, int col, Player player) {}

class InvalidMoveException extends RuntimeException {
    InvalidMoveException(String msg) { super(msg); }
}

class Board {
    private final int n;
    private final Piece[][] cells;
    private final int[] rows, cols;
    private int diag, antiDiag;
    private int filled;

    Board(int n) {
        this.n = n;
        this.cells = new Piece[n][n];
        this.rows = new int[n];
        this.cols = new int[n];
    }

    int size()      { return n; }
    boolean isFull(){ return filled == n * n; }
    boolean inBounds(int r, int c) { return r >= 0 && r < n && c >= 0 && c < n; }
    boolean isEmpty(int r, int c)  { return cells[r][c] == null; }
    Piece at(int r, int c)         { return cells[r][c]; }

    /** Writes the piece and updates at most four counters. Returns true if this move wins. */
    boolean place(int r, int c, Piece piece) {
        cells[r][c] = piece;
        filled++;
        int v = piece.value;
        rows[r] += v;
        cols[c] += v;
        if (r == c)          diag += v;
        if (r + c == n - 1)  antiDiag += v;

        return Math.abs(rows[r]) == n
            || Math.abs(cols[c]) == n
            || Math.abs(diag) == n
            || Math.abs(antiDiag) == n;
    }

    /** Undo is the same arithmetic with the sign flipped — no snapshots. */
    void remove(int r, int c) {
        Piece piece = cells[r][c];
        if (piece == null) return;
        cells[r][c] = null;
        filled--;
        int v = piece.value;
        rows[r] -= v;
        cols[c] -= v;
        if (r == c)          diag -= v;
        if (r + c == n - 1)  antiDiag -= v;
    }

    void print() {
        for (int r = 0; r < n; r++) {
            StringBuilder sb = new StringBuilder("   ");
            for (int c = 0; c < n; c++) sb.append(cells[r][c] == null ? "." : cells[r][c].name()).append(' ');
            System.out.println(sb);
        }
    }
}

enum Status { IN_PROGRESS, WON, DRAW }

class Game {
    private final Board board;
    private final Deque<Player> turnOrder = new ArrayDeque<>();   // a queue, so 3 players costs one line
    private final List<Move> history = new ArrayList<>();
    private Status status = Status.IN_PROGRESS;
    private Player winner;

    Game(int n, List<Player> players) {
        if (players.size() < 2) throw new IllegalArgumentException("need at least two players");
        this.board = new Board(n);
        this.turnOrder.addAll(players);
    }

    Status status()   { return status; }
    Player winner()   { return winner; }
    Player current()  { return turnOrder.peekFirst(); }
    Board board()     { return board; }

    Status play(int r, int c) {
        // ---- validate first; nothing has changed yet ----
        if (status != Status.IN_PROGRESS)   throw new InvalidMoveException("game is over");
        if (!board.inBounds(r, c))          throw new InvalidMoveException("off the board: " + r + "," + c);
        if (!board.isEmpty(r, c))           throw new InvalidMoveException("cell taken: " + r + "," + c);

        // ---- now mutate ----
        Player player = turnOrder.removeFirst();
        history.add(new Move(r, c, player));
        boolean won = board.place(r, c, player.piece());

        if (won) { status = Status.WON; winner = player; return status; }
        if (board.isFull()) { status = Status.DRAW; return status; }

        turnOrder.addLast(player);                 // rotate only when the game continues
        return status;
    }

    void undo() {
        if (history.isEmpty()) return;
        Move m = history.remove(history.size() - 1);
        board.remove(m.row(), m.col());
        if (status == Status.IN_PROGRESS) turnOrder.removeLast();   // un-rotate
        turnOrder.addFirst(m.player());
        status = Status.IN_PROGRESS;
        winner = null;
    }
}

public class Main {
    public static void main(String[] args) {
        Player asha = new Player("Asha", Piece.X);
        Player ravi = new Player("Ravi", Piece.O);
        Game game = new Game(3, List.of(asha, ravi));

        int[][] script = {{0,0},{0,1},{1,1},{0,2},{2,2}};    // X wins on the \ diagonal
        for (int[] mv : script) {
            System.out.println(game.current().name() + " plays " + mv[0] + "," + mv[1]);
            Status s = game.play(mv[0], mv[1]);
            game.board().print();
            if (s == Status.WON)  { System.out.println("=> " + game.winner().name() + " wins"); break; }
            if (s == Status.DRAW) { System.out.println("=> draw"); break; }
        }

        try { game.play(1, 0); }
        catch (InvalidMoveException e) { System.out.println("rejected: " + e.getMessage()); }

        game.undo();
        System.out.println("after undo, status=" + game.status() + ", next=" + game.current().name());

        // the follow-up: same code, bigger board
        Game big = new Game(5, List.of(asha, ravi));
        for (int i = 0; i < 5; i++) { big.play(0, i); if (big.status() == Status.IN_PROGRESS) big.play(1, i); }
        System.out.println("5x5 => " + big.status() + " by " + big.winner().name());
    }
}