LLD Question 04

Tic Tac Toe

Design a two-player Tic Tac Toe game with configurable board size, win detection via a pluggable strategy, move history, and draw detection.

Learning note

Win detection belongs in a strategy, not in the board or the game loop. The board stores symbols, not players, because it only needs to know what is in a cell.

Problem Statement

Design a two-player Tic Tac Toe game where players alternate placing symbols on a grid. The game ends when one player fills an entire row, column, or diagonal, or when the board is full with no winner.

Functional Requirements

Two players each have a unique symbol.
Players take turns. Each turn a player picks a row and column.
A move is invalid if the cell is already occupied or out of bounds.
After each move, check if the last move caused a win.
If the board is full and no one has won, the result is a draw.
The game should work on any N×N board, not just 3×3.
The win rule should be pluggable so different win conditions can be used.

Core Entities

Entity	Responsibility
`Symbol`	Enum for X and O.
`GameStatus`	Enum for IN_PROGRESS, WIN, and DRAW.
`Player`	Holds player name and assigned symbol.
`Move`	Encapsulates row, column, and the player who made the move.
`Board`	Manages the grid, validates moves, applies moves, detects full board.
`WinStrategy`	Interface for win detection logic.
`StandardWinStrategy`	Checks row, column, and diagonals of the last move in O(N).
`Game`	Orchestrates the game loop, turn switching, and result announcement.

Design Decisions

Board Stores Symbols Not Players

Board uses Symbol[][] instead of Player[][] because the board only needs to know what is in a cell, not who placed it. This reduces coupling between Board and Player.

Win Detection as Strategy

Board should only manage state. Game should only orchestrate turns. Win detection is a rule, so it belongs in WinStrategy. Swapping in a different win condition requires zero changes to Board or Game.

Only Check Lines Through Last Move

A win can only occur on the row, column, or diagonal that contains the last played cell. Checking all lines every turn is unnecessary. StandardWinStrategy always checks exactly four lines per turn regardless of board size.

Move Object for Extensibility

Using a Move object instead of raw row/col integers allows move history to be stored as a list. This enables undo support later.

Dependency Injection at Composition Root

WinStrategy is injected into Game through the constructor. Main is the only place where all dependencies are wired together. Swapping strategies requires changing only Main.

Main Flow

Create two players with symbols.
Inject a WinStrategy and create a Game.
Game loop starts.
Current player is prompted for row and column.
Move is validated by Board.
Move is applied and recorded in move history.
WinStrategy.checkWinner() is called with the last move coordinates.
If winner found, announce and end.
If board full, announce draw and end.
Otherwise switch to next player and repeat.

Complete Code: Bottom-Up

1. enums/Symbol.java

package enums;
 
public enum Symbol {
    X, O
}

2. enums/GameStatus.java

package enums;
 
public enum GameStatus {
    IN_PROGRESS,
    WIN,
    DRAW
}

3. models/Player.java

package models;
 
import enums.Symbol;
 
public class Player {
 
    private final String name;
    private final Symbol symbol;
 
    public Player(String name, Symbol symbol) {
        this.name = name;
        this.symbol = symbol;
    }
 
    public String getName() {
        return name;
    }
 
    public Symbol getSymbol() {
        return symbol;
    }
 
    @Override
    public String toString() {
        return name + " (" + symbol + ")";
    }
}

4. models/Move.java

package models;
 
// Having a Move object instead of raw row/col ints allows
// a move history list to be added to Game for undo support.
public class Move {
 
    private final int row;
    private final int col;
    private final Player player;
 
    public Move(int row, int col, Player player) {
        this.row = row;
        this.col = col;
        this.player = player;
    }
 
    public int getRow() {
        return row;
    }
 
    public int getCol() {
        return col;
    }
 
    public Player getPlayer() {
        return player;
    }
}

5. models/Board.java

package models;
 
import enums.Symbol;
 
// Responsibilities: maintain grid state, validate moves, apply moves,
// expose cell state via getCell() for WinStrategy, render to console.
//
// What Board does NOT do: win detection — that is a game rule owned by WinStrategy.
public class Board {
 
    private final int size;
    private final Symbol[][] grid;
 
    public Board(int size) {
        this.size = size;
        this.grid = new Symbol[size][size];
        // null means empty
    }
 
    public boolean isValidMove(int row, int col) {
        if (row < 0 || row >= size || col < 0 || col >= size) {
            return false;
        }
        return grid[row][col] == null;
    }
 
    public void makeMove(int row, int col, Symbol symbol) {
        grid[row][col] = symbol;
    }
 
    public boolean isFull() {
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                if (grid[i][j] == null) {
                    return false;
                }
            }
        }
        return true;
    }
 
    // Clean read API for WinStrategy — raw grid is never exposed.
    public Symbol getCell(int row, int col) {
        return grid[row][col];
    }
 
    public void printBoard() {
        System.out.print("    ");
        for (int j = 1; j <= size; j++) {
            System.out.printf("  %d ", j);
        }
        System.out.println();
 
        for (int i = 0; i < size; i++) {
            if (i > 0) {
                System.out.print("    ");
                System.out.println("----".repeat(size) + "-");
            }
 
            System.out.printf("  %d ", i + 1);
 
            for (int j = 0; j < size; j++) {
                if (j > 0) System.out.print("|");
                String cell = (grid[i][j] == null) ? "." : grid[i][j].toString();
                System.out.printf(" %s  ", cell);
            }
            System.out.println();
        }
        System.out.println();
    }
 
    public int getSize() {
        return size;
    }
}

6. strategy/WinStrategy.java

package strategy;
 
import enums.Symbol;
import models.Board;
 
// Strategy interface for win detection.
// Board manages state. Game orchestrates turns. WinStrategy owns the win rule.
// Swap the rule by swapping the implementation — zero changes to Board or Game.
public interface WinStrategy {
 
    // Only the row, column, and diagonals through (lastRow, lastCol) need checking.
    // A win can only occur on lines touched by the last move.
    Symbol checkWinner(Board board, int lastRow, int lastCol);
}

7. strategy/StandardWinStrategy.java

package strategy;
 
import enums.Symbol;
import models.Board;
 
// Standard win rule: fill an entire row, column, or diagonal.
//
// Optimization: only the four lines through the last move are checked.
// This is always O(N) per turn regardless of board size.
public class StandardWinStrategy implements WinStrategy {
 
    @Override
    public Symbol checkWinner(Board board, int lastRow, int lastCol) {
        int size = board.getSize();
        Symbol symbol = board.getCell(lastRow, lastCol);
 
        if (symbol == null) return null;
 
        if (checkRow(board, lastRow, size, symbol))         return symbol;
        if (checkColumn(board, lastCol, size, symbol))      return symbol;
        if (checkMainDiagonal(board, size, symbol))         return symbol;
        if (checkAntiDiagonal(board, size, symbol))         return symbol;
 
        return null;
    }
 
    private boolean checkRow(Board board, int row, int size, Symbol symbol) {
        for (int col = 0; col < size; col++) {
            if (board.getCell(row, col) != symbol) return false;
        }
        return true;
    }
 
    private boolean checkColumn(Board board, int col, int size, Symbol symbol) {
        for (int row = 0; row < size; row++) {
            if (board.getCell(row, col) != symbol) return false;
        }
        return true;
    }
 
    private boolean checkMainDiagonal(Board board, int size, Symbol symbol) {
        for (int i = 0; i < size; i++) {
            if (board.getCell(i, i) != symbol) return false;
        }
        return true;
    }
 
    private boolean checkAntiDiagonal(Board board, int size, Symbol symbol) {
        for (int i = 0; i < size; i++) {
            if (board.getCell(i, size - 1 - i) != symbol) return false;
        }
        return true;
    }
}

8. game/Game.java

package game;
 
import enums.GameStatus;
import enums.Symbol;
import models.Board;
import models.Move;
import models.Player;
import strategy.WinStrategy;
 
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
 
// Orchestrates the game loop.
// Does NOT do win detection — delegated to WinStrategy.
// Does NOT inspect Board internals — reads only via Board's public API.
// WinStrategy is injected via constructor (Dependency Injection).
public class Game {
 
    private final Board board;
    private final List<Player> players;
    private final WinStrategy winStrategy;
    private int currentPlayerIndex;
    private GameStatus status;
    private final List<Move> moveHistory;
    private final Scanner scanner;
 
    public Game(List<Player> players, int boardSize, WinStrategy winStrategy) {
        this.board = new Board(boardSize);
        this.players = new ArrayList<>(players);
        this.winStrategy = winStrategy;
        this.currentPlayerIndex = 0;
        this.status = GameStatus.IN_PROGRESS;
        this.moveHistory = new ArrayList<>();
        this.scanner = new Scanner(System.in);
    }
 
    public void start() {
        System.out.println("=============================");
        System.out.println("   Welcome to Tic Tac Toe!  ");
        System.out.println("=============================");
        printPlayerInfo();
        board.printBoard();
 
        while (status == GameStatus.IN_PROGRESS) {
            Player currentPlayer = getCurrentPlayer();
            System.out.println("Turn: " + currentPlayer);
 
            Move move = getValidMove(currentPlayer);
 
            board.makeMove(move.getRow(), move.getCol(), currentPlayer.getSymbol());
            moveHistory.add(move);
            board.printBoard();
 
            // Delegate win detection — only pass last move coordinates.
            Symbol winner = winStrategy.checkWinner(board, move.getRow(), move.getCol());
            if (winner != null) {
                status = GameStatus.WIN;
                System.out.println("Congratulations! " + currentPlayer.getName() + " wins!");
                break;
            }
 
            if (board.isFull()) {
                status = GameStatus.DRAW;
                System.out.println("It's a draw! Well played by both players.");
                break;
            }
 
            switchTurn();
        }
 
        System.out.println("Game over. Final status: " + status);
        scanner.close();
    }
 
    private Move getValidMove(Player player) {
        while (true) {
            try {
                System.out.printf(
                    "Enter row and column (1-%d) separated by space: ",
                    board.getSize()
                );
                int row = scanner.nextInt() - 1;
                int col = scanner.nextInt() - 1;
 
                if (board.isValidMove(row, col)) {
                    return new Move(row, col, player);
                } else {
                    System.out.println("Invalid move! Cell is occupied or out of bounds. Try again.");
                }
            } catch (Exception e) {
                System.out.println("Invalid input! Please enter two numbers separated by space.");
                scanner.nextLine();
            }
        }
    }
 
    private void switchTurn() {
        currentPlayerIndex = (currentPlayerIndex + 1) % players.size();
    }
 
    private Player getCurrentPlayer() {
        return players.get(currentPlayerIndex);
    }
 
    private void printPlayerInfo() {
        System.out.println("Players:");
        for (Player p : players) {
            System.out.println("  " + p);
        }
        System.out.println("Board size: " + board.getSize() + "x" + board.getSize());
        System.out.println("Win rule: " + winStrategy.getClass().getSimpleName());
        System.out.println("Enter moves as: row col (both 1-indexed)");
        System.out.println("-----------------------------");
    }
 
    public GameStatus getStatus() {
        return status;
    }
 
    public List<Move> getMoveHistory() {
        return new ArrayList<>(moveHistory);
    }
}

9. Main.java

import enums.Symbol;
import game.Game;
import models.Player;
import strategy.StandardWinStrategy;
import strategy.WinStrategy;
 
import java.util.Arrays;
import java.util.List;
 
// Composition root: the single place where all dependencies are wired.
// Swapping StandardWinStrategy for any other WinStrategy requires only this file.
public class Main {
 
    public static void main(String[] args) {
        Player player1 = new Player("Alice", Symbol.X);
        Player player2 = new Player("Bob", Symbol.O);
 
        List<Player> players = Arrays.asList(player1, player2);
 
        // Inject win rule. Swap this to change the win condition.
        WinStrategy winStrategy = new StandardWinStrategy();
 
        // Change 3 to 4 for a 4x4 board.
        Game game = new Game(players, 3, winStrategy);
        game.start();
    }
}

What I Learned

Win detection should be a strategy, not embedded in the board or the game loop.
Board stores Symbol[][] not Player[][] because the board only cares what is in each cell.
Checking only the four lines through the last move keeps win detection O(N) per turn.
A Move object instead of raw integers prepares the design for undo support.
Injecting WinStrategy at the composition root means Main is the only class that changes when the win rule changes.

Possible Improvements

Add HumanPlayer and BotPlayer subclasses each overriding a getMove() method to support AI without changing Game.
Add undo by popping the last Move from moveHistory and clearing that cell.
Add N-in-a-row win strategy for games where you need only K consecutive symbols, not the full line.
Add unit tests for draw detection, out-of-bounds input, and diagonal win conditions.