Tic Tac Toe

Functional Requirements

1. Board:
   - 3x3 grid (generalizable to NxN)
   - Each cell is empty, or holds X, or holds O

2. Players:
   - Two players: X and O
   - X always goes first
   - Players alternate turns

3. Moves:
   - Player selects a cell (row, col)
   - Cell must be empty and game must be in progress
   - After placement, check for win or draw

4. Win Condition:
   - Three of same mark in a row (horizontal, vertical, or diagonal)

5. Draw Condition:
   - Board is full and no player has won

6. Game End:
   - Game stops immediately on win or draw
   - No further moves accepted

Non-Functional Requirements

• Modularity: Win detection, board, and game logic are separate concerns
• Testability: Each component independently testable
• Extensibility: Easy to change board size, add AI, or support online play
• Performance: Move validation and win check must be O(N) for NxN board

Core Entities

Entity	Responsibility
Cell	Holds a player mark (X, O, or empty)
Board	NxN grid, place pieces, query cell state
Player	Symbol (X or O), name
Move	Row + column of a placement
MoveValidator	Checks if a move is legal
WinChecker	Checks rows, cols, diagonals for a winner
Game	Orchestrates turns, delegates validation and win checks

Game State Diagram

┌──────────────────────────────────────────────────────┐
│                   Game States                         │
├──────────────────────────────────────────────────────┤
│                                                       │
│   NOT_STARTED ──→ PLAYING ──→ WON ──→ GAME_OVER      │
│                        │                              │
│                        └──→ DRAW ──→ GAME_OVER        │
│                                                       │
└──────────────────────────────────────────────────────┘

Transitions:
  start()        : NOT_STARTED → PLAYING
  makeMove()     : PLAYING → PLAYING (valid move, no winner yet)
  makeMove()     : PLAYING → WON (move creates a winning line)
  makeMove()     : PLAYING → DRAW (move fills last cell, no winner)
  any after END  : throw IllegalStateException

Game Flow

Player makes move
       │
       ▼
┌─────────────┐     invalid     ┌──────────┐
│ Validate    │───────────────→ │ Reject   │
│ Move        │                 │ Move     │
└──────┬──────┘                 └──────────┘
       │ valid
       ▼
┌─────────────┐
│ Place piece │
│ on board    │
└──────┬──────┘
       │
       ▼
┌─────────────┐     yes        ┌──────────┐
│ Check Win?  │──────────────→ │ Set WON  │
└──────┬──────┘                └──────────┘
       │ no
       ▼
┌─────────────┐     yes        ┌──────────┐
│ Check Draw? │──────────────→ │ Set DRAW │
└──────┬──────┘                └──────────┘
       │ no
       ▼
┌─────────────┐
│ Switch      │
│ Player      │
└─────────────┘

Cell

A cell holds one of three states: empty, X, or O. An enum is the cleanest representation.

public enum CellState {
    EMPTY, X, O;
}

Board Class

The board owns the 2D grid and provides methods to place pieces, query cells, and check fullness.

public class Board {
    private final int size;
    private final CellState[][] grid;
    private int emptyCells;

    public Board(int size) {
        this.size = size;
        this.grid = new CellState[size][size];
        this.emptyCells = size * size;
        for (int r = 0; r < size; r++) {
            for (int c = 0; c < size; c++) {
                grid[r][c] = CellState.EMPTY;
            }
        }
    }

    public int getSize() { return size; }

    public CellState getCell(int row, int col) {
        checkBounds(row, col);
        return grid[row][col];
    }

    public void placePiece(int row, int col, CellState state) {
        checkBounds(row, col);
        if (grid[row][col] != CellState.EMPTY) {
            throw new IllegalStateException("Cell already occupied");
        }
        grid[row][col] = state;
        emptyCells--;
    }

    public boolean isFull() {
        return emptyCells == 0;
    }

    public boolean isEmpty(int row, int col) {
        checkBounds(row, col);
        return grid[row][col] == CellState.EMPTY;
    }

    private void checkBounds(int row, int col) {
        if (row < 0 || row >= size || col < 0 || col >= size) {
            throw new IndexOutOfBoundsException(
                "Position (" + row + "," + col + ") out of bounds"
            );
        }
    }
}

Coordinate Record

public record Position(int row, int col) {
    public Position {
        if (row < 0 || col < 0) {
            throw new IllegalArgumentException("Negative coordinates");
        }
    }
}

Board Visual (3x3)

     Col 0   Col 1   Col 2
    ┌───────┬───────┬───────┐
Row │       │       │       │
 0  │(0,0)  │(0,1)  │(0,2)  │
    ├───────┼───────┼───────┤
Row │       │       │       │
 1  │(1,0)  │(1,1)  │(1,2)  │
    ├───────┼───────┼───────┤
Row │       │       │       │
 2  │(2,0)  │(2,1)  │(2,2)  │
    └───────┴───────┴───────┘

Example mid-game:
    ┌───────┬───────┬───────┐
    │   X   │   O   │   X   │
    ├───────┼───────┼───────┤
    │       │   O   │       │
    ├───────┼───────┼───────┤
    │   O   │       │       │
    └───────┴───────┴───────┘

Time and Space Complexity

Operation	Time	Space
getCell(row, col)	O(1)	O(1)
placePiece(row, col)	O(1)	O(1)
isFull()	O(1)	O(1)
isEmpty(row, col)	O(1)	O(1)
Board construction	O(N²)	O(N²)

Strategy Pattern for Win Checking

Using Strategy pattern allows swapping win-checking algorithms (e.g., 3x3 vs NxN, or custom variants).

public interface WinChecker {
    boolean checkWinner(Board board, CellState lastMoveCell, int row, int col);
}

Standard 3x3 Win Checker

Only the row, column, and two diagonals passing through the last move need checking.

public class StandardWinChecker implements WinChecker {

    @Override
    public boolean checkWinner(Board board, CellState piece, int row, int col) {
        int size = board.getSize();

        // Check row
        boolean winRow = true;
        for (int c = 0; c < size; c++) {
            if (board.getCell(row, c) != piece) {
                winRow = false;
                break;
            }
        }
        if (winRow) return true;

        // Check column
        boolean winCol = true;
        for (int r = 0; r < size; r++) {
            if (board.getCell(r, col) != piece) {
                winCol = false;
                break;
            }
        }
        if (winCol) return true;

        // Check main diagonal (top-left to bottom-right)
        if (row == col) {
            boolean winDiag = true;
            for (int i = 0; i < size; i++) {
                if (board.getCell(i, i) != piece) {
                    winDiag = false;
                    break;
                }
            }
            if (winDiag) return true;
        }

        // Check anti-diagonal (top-right to bottom-left)
        if (row + col == size - 1) {
            boolean winAnti = true;
            for (int i = 0; i < size; i++) {
                if (board.getCell(i, size - 1 - i) != piece) {
                    winAnti = false;
                    break;
                }
            }
            if (winAnti) return true;
        }

        return false;
    }
}

NxN Generalized Win Checker (Connect K)

For an NxN board with a configurable "connect K" requirement:

public class GeneralizedWinChecker implements WinChecker {
    private final int connectK;

    public GeneralizedWinChecker(int connectK) {
        this.connectK = connectK;
    }

    @Override
    public boolean checkWinner(Board board, CellState piece, int row, int col) {
        int[][] directions = {{0,1}, {1,0}, {1,1}, {1,-1}};

        for (int[] dir : directions) {
            int count = 1;
            count += countInDirection(board, piece, row, col, dir[0], dir[1]);
            count += countInDirection(board, piece, row, col, -dir[0], -dir[1]);
            if (count >= connectK) return true;
        }
        return false;
    }

    private int countInDirection(Board board, CellState piece,
                                 int row, int col, int dr, int dc) {
        int count = 0;
        int r = row + dr;
        int c = col + dc;
        while (r >= 0 && r < board.getSize() &&
               c >= 0 && c < board.getSize() &&
               board.getCell(r, c) == piece) {
            count++;
            r += dr;
            c += dc;
        }
        return count;
    }
}

Draw Detection

public class DrawChecker {
    public static boolean isDraw(Board board) {
        return board.isFull();
    }
}

Win Detection Walkthrough

After X plays (0,0):
    ┌───────┬───────┬───────┐
    │   X   │       │       │
    ├───────┼───────┼───────┤
    │       │       │       │  Check: row 0, col 0,
    ├───────┼───────┼───────┤  diag (0,0), anti-diag N/A
    │       │       │       │  Result: NO WIN
    └───────┴───────┴───────┘

After X plays (0,1):
    ┌───────┬───────┬───────┐
    │   X   │   X   │       │
    ├───────┼───────┼───────┤
    │       │       │       │  Check: row 0 has 2 X's
    ├───────┼───────┼───────┤  Result: NO WIN
    │       │       │       │
    └───────┴───────┴───────┘

After X plays (0,2) — WIN:
    ┌───────┬───────┬───────┐
    │   X   │   X   │   X   │  ← Row 0 all X
    ├───────┼───────┼───────┤
    │       │       │       │  Check row 0: X X X ✓
    ├───────┼───────┼───────┤  Result: X WINS!
    │       │       │       │
    └───────┴───────┴───────┘

Complexity

Checker	Time	Notes
Standard 3x3	O(N)	N = board size, check 4 lines max
Generalized (connect K)	O(K)	Walk at most K cells in each direction
Draw	O(1)	Single counter check

Game Status Enum

public enum GameStatus {
    NOT_STARTED, PLAYING, WON, DRAW, GAME_OVER
}

Player Class

public class Player {
    private final String name;
    private final CellState symbol;

    public Player(String name, CellState symbol) {
        this.name = name;
        this.symbol = symbol;
    }

    public String getName() { return name; }
    public CellState getSymbol() { return symbol; }
}

Move Class

public record Move(Player player, int row, int col) {
    public Move {
        if (player == null) throw new NullPointerException("Player required");
    }
}

MoveValidator

public class MoveValidator {

    public void validate(Board board, GameStatus status, int row, int col) {
        if (status != GameStatus.PLAYING) {
            throw new IllegalStateException(
                "Game is not in progress. Status: " + status
            );
        }
        if (row < 0 || row >= board.getSize() ||
            col < 0 || col >= board.getSize()) {
            throw new IllegalArgumentException(
                "Position out of bounds: (" + row + "," + col + ")"
            );
        }
        if (!board.isEmpty(row, col)) {
            throw new IllegalStateException(
                "Cell (" + row + "," + col + ") is already occupied"
            );
        }
    }
}

Game Class — The Orchestrator

public class Game {
    private final Board board;
    private final Player playerX;
    private final Player playerO;
    private final MoveValidator validator;
    private final WinChecker winChecker;
    private GameStatus status;
    private Player currentPlayer;
    private final List<Move> moveHistory;
    private Player winner;

    public Game(Player playerX, Player playerO, int boardSize) {
        this(playerX, playerO, boardSize, new StandardWinChecker());
    }

    public Game(Player playerX, Player playerO, int boardSize,
                WinChecker winChecker) {
        this.playerX = playerX;
        this.playerO = playerO;
        this.board = new Board(boardSize);
        this.validator = new MoveValidator();
        this.winChecker = winChecker;
        this.status = GameStatus.NOT_STARTED;
        this.currentPlayer = playerX; // X always goes first
        this.moveHistory = new ArrayList<>();
        this.winner = null;
    }

    public void start() {
        if (status != GameStatus.NOT_STARTED) {
            throw new IllegalStateException("Game already started");
        }
        status = GameStatus.PLAYING;
    }

    public void makeMove(int row, int col) {
        validator.validate(board, status, row, col);

        CellState piece = currentPlayer.getSymbol();
        board.placePiece(row, col, piece);

        Move move = new Move(currentPlayer, row, col);
        moveHistory.add(move);

        if (winChecker.checkWinner(board, piece, row, col)) {
            status = GameStatus.WON;
            winner = currentPlayer;
        } else if (board.isFull()) {
            status = GameStatus.DRAW;
        } else {
            switchPlayer();
        }
    }

    private void switchPlayer() {
        currentPlayer = (currentPlayer == playerX) ? playerO : playerX;
    }

    public void reset() {
        for (int r = 0; r < board.getSize(); r++) {
            for (int c = 0; c < board.getSize(); c++) {
                // Recreate board to clear
            }
        }
        status = GameStatus.NOT_STARTED;
        currentPlayer = playerX;
        moveHistory.clear();
        winner = null;
    }

    // Getters
    public Board getBoard() { return board; }
    public GameStatus getStatus() { return status; }
    public Player getCurrentPlayer() { return currentPlayer; }
    public Player getWinner() { return winner; }
    public List<Move> getMoveHistory() {
        return Collections.unmodifiableList(moveHistory);
    }
    public int getMoveCount() { return moveHistory.size(); }
}

State Transition Table

Current State	Action	Condition	New State
NOT_STARTED	start()	—	PLAYING
PLAYING	makeMove()	Valid + Win	WON
PLAYING	makeMove()	Valid + Full	DRAW
PLAYING	makeMove()	Valid + No win	PLAYING
PLAYING	makeMove()	Invalid move	throw
WON	makeMove()	—	throw
DRAW	makeMove()	—	throw

Observer Pattern for Game Events

public interface GameListener {
    void onMoveMade(Move move, Board board);
    void onWin(Player winner, List<Move> moveHistory);
    void onDraw(List<Move> moveHistory);
}

// Usage in Game class:
private final List<GameListener> listeners = new ArrayList<>();

public void addListener(GameListener listener) {
    listeners.add(listener);
}

private void notifyMove(Move move) {
    listeners.forEach(l -> l.onMoveMade(move, board));
}

private void notifyWin(Player winner) {
    listeners.forEach(l -> l.onWin(winner, moveHistory));
}

private void notifyDraw() {
    listeners.forEach(l -> l.onDraw(moveHistory));
}

Follow-up 1: NxN Board with Connect-K

Swap the WinChecker strategy:

Game game = new Game(playerX, playerO, 5, new GeneralizedWinChecker(4));
// 5x5 board, connect 4 to win

Follow-up 2: Undo Move

Maintain a move stack and revert board state:

public class UndoableGame extends Game {
    private final Deque<Move> undoStack = new ArrayDeque<>();

    @Override
    public void makeMove(int row, int col) {
        super.makeMove(row, col);
        undoStack.push(new Move(getCurrentPlayer(), row, col));
    }

    public Move undo() {
        if (undoStack.isEmpty()) return null;
        Move last = undoStack.pop();
        // Revert board cell to EMPTY
        getBoard().getCell(last.row(), last.col()); // placeholder
        return last;
    }
}

Follow-up 3: AI Opponent (Random / Minimax)

public interface AIStrategy {
    Position getMove(Board board, CellState aiSymbol);
}

public class RandomAI implements AIStrategy {
    private final Random rand = new Random();

    @Override
    public Position getMove(Board board, CellState aiSymbol) {
        List<Position> empty = new ArrayList<>();
        for (int r = 0; r < board.getSize(); r++)
            for (int c = 0; c < board.getSize(); c++)
                if (board.isEmpty(r, c))
                    empty.add(new Position(r, c));
        return empty.get(rand.nextInt(empty.size()));
    }
}

public class MinimaxAI implements AIStrategy {
    @Override
    public Position getMove(Board board, CellState aiSymbol) {
        // Implement minimax with alpha-beta pruning
        // Evaluate board: +10 for AI win, -10 for opponent win, 0 for draw
        return null; // placeholder for full implementation
    }
}

Follow-up 4: Online Multiplayer

┌─────────┐     WebSocket      ┌─────────────┐
│ Player 1 │◄─────────────────►│  Game Server │
└─────────┘                    │  (Game Room) │
                               │              │
┌─────────┐     WebSocket      │  - Board     │
│ Player 2 │◄─────────────────►│  - Players   │
└─────────┘                    │  - State     │
                               └──────────────┘

• Each player sends moves via WebSocket
• Server validates and broadcasts state to both players
• Sync conflicts: server is source of truth

Follow-up 5: Tournament Mode

public class Tournament {
    private final List<Game> games;
    private final Map<Player, Integer> scores;

    public void recordWin(Player winner) {
        scores.merge(winner, 3, Integer::sum); // 3 pts for win
    }

    public void recordDraw(Player p1, Player p2) {
        scores.merge(p1, 1, Integer::sum); // 1 pt each
        scores.merge(p2, 1, Integer::sum);
    }

    public Player getLeader() {
        return scores.entrySet().stream()
            .max(Map.Entry.comparingByValue())
            .map(Map.Entry::getKey)
            .orElse(null);
    }
}

Design Pattern Summary

Pattern	Where Used	Why
Strategy	WinChecker interface	Swap 3x3 vs NxN vs custom rules
State	GameStatus enum + transitions	Enforce legal state changes
Observer	GameListener interface	Decouple UI from game logic
Factory	AI strategy selection	Create AI based on difficulty

Time & Space Complexity

Operation	Time	Space
makeMove()	O(N)	O(1)
Win check (3x3)	O(N)	O(1)
Win check (generalized)	O(K)	O(1)
Move history	O(M) total	O(M)
Undo	O(1)	O(M)

N = board size, K = connect length, M = total moves made