androidinterview.com

Low Level Design (LLD) Interview Questions

Design Ludo

Tier: EssentialDifficulty: MediumAsked of: Mid, SeniorAsked at: Freshworks

Design a Ludo game where four players move four tokens each around a shared track and into their own home lane.

The problem

A token starts in its yard. A six can bring it onto the track or move a token already in play. Landing on an opponent on an unsafe square sends that opponent back to its yard. The first player to bring all four tokens home wins.

Agree on the rules before coding. This version gives another turn after a successful move on six. It has safe squares and an exact roll to reach home. It leaves out blockades, a three-sixes penalty and bonus turns for captures. If no token can move, the player passes.

How to explain the design

“I store how far each token has travelled. Minus one means the yard, zero means its entry square, and 57 means home. First I find which tokens can legally use the roll. The player chooses one. I move it, check for captures, then decide whether the player wins or the turn advances.”

Steps 0 through 51 are on the shared track. Steps 52 through 57 are in the player's private home lane. Each player's entry point is 13 squares after the previous player's, so travelled steps can be converted into a shared board square when checking captures.

Walk through a turn

  1. A player rolls six and chooses a yard token.
  2. Its position changes from minus one to zero. Entering does not move it six more squares.
  3. The player rolls again and advances that token.
  4. If it lands on an unsafe square occupied by an opponent, reset the opponent to the yard.
  5. A non-six ends the turn unless the move completed the player's fourth token.

Interview implementation

Ludo keeps token positions, turn and winner. The caller supplies the die roll and selected token. Pass a null token only when legalTokens returns an empty list.

Java

Ludo.java

package interview.ludo;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Set;

public class Ludo {
    private final int[][] tokens = new int[4][4];
    private final Set<Integer> safe = Set.of(0, 8, 13, 21, 26, 34, 39, 47);
    private int turn;
    private Integer winner;

    public Ludo() { for (int[] player : tokens) Arrays.fill(player, -1); }
    public int position(int player, int token) { return tokens[player][token]; }
    public int turn() { return turn; }
    public Integer winner() { return winner; }

    public List<Integer> legalTokens(int roll) {
        if (roll < 1 || roll > 6) throw new IllegalArgumentException("Invalid roll");
        List<Integer> legal = new ArrayList<>();
        for (int token = 0; token < 4; token++) {
            int steps = tokens[turn][token];
            if (steps == -1 ? roll == 6 : steps < 57 && steps + roll <= 57) legal.add(token);
        }
        return legal;
    }

    public void move(int player, Integer token, int roll) {
        if (winner != null || player != turn) throw new IllegalStateException("Not this player's turn");
        List<Integer> legal = legalTokens(roll);
        if (legal.isEmpty()) {
            if (token != null) throw new IllegalArgumentException("Pass when no move is available");
            turn = (turn + 1) % 4;
            return;
        }
        if (token == null || !legal.contains(token)) throw new IllegalArgumentException("Invalid token");
        int previous = tokens[player][token];
        int next = previous == -1 ? 0 : previous + roll;
        tokens[player][token] = next;
        if (next < 52) {
            int square = (player * 13 + next) % 52;
            if (!safe.contains(square)) {
                for (int opponent = 0; opponent < 4; opponent++) for (int other = 0; other < 4; other++) {
                    int steps = tokens[opponent][other];
                    if (opponent != player && steps >= 0 && steps < 52 && (opponent * 13 + steps) % 52 == square) {
                        tokens[opponent][other] = -1;
                    }
                }
            }
        }
        if (Arrays.stream(tokens[player]).allMatch(steps -> steps == 57)) winner = player;
        else if (roll != 6) turn = (turn + 1) % 4;
    }
}

package interview.ludo;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Set;

public class Ludo {
    private final int[][] tokens = new int[4][4];
    private final Set<Integer> safe = Set.of(0, 8, 13, 21, 26, 34, 39, 47);
    private int turn;
    private Integer winner;

    public Ludo() { for (int[] player : tokens) Arrays.fill(player, -1); }
    public int position(int player, int token) { return tokens[player][token]; }
    public int turn() { return turn; }
    public Integer winner() { return winner; }

    public List<Integer> legalTokens(int roll) {
        if (roll < 1 || roll > 6) throw new IllegalArgumentException("Invalid roll");
        List<Integer> legal = new ArrayList<>();
        for (int token = 0; token < 4; token++) {
            int steps = tokens[turn][token];
            if (steps == -1 ? roll == 6 : steps < 57 && steps + roll <= 57) legal.add(token);
        }
        return legal;
    }

    public void move(int player, Integer token, int roll) {
        if (winner != null || player != turn) throw new IllegalStateException("Not this player's turn");
        List<Integer> legal = legalTokens(roll);
        if (legal.isEmpty()) {
            if (token != null) throw new IllegalArgumentException("Pass when no move is available");
            turn = (turn + 1) % 4;
            return;
        }
        if (token == null || !legal.contains(token)) throw new IllegalArgumentException("Invalid token");
        int previous = tokens[player][token];
        int next = previous == -1 ? 0 : previous + roll;
        tokens[player][token] = next;
        if (next < 52) {
            int square = (player * 13 + next) % 52;
            if (!safe.contains(square)) {
                for (int opponent = 0; opponent < 4; opponent++) for (int other = 0; other < 4; other++) {
                    int steps = tokens[opponent][other];
                    if (opponent != player && steps >= 0 && steps < 52 && (opponent * 13 + steps) % 52 == square) {
                        tokens[opponent][other] = -1;
                    }
                }
            }
        }
        if (Arrays.stream(tokens[player]).allMatch(steps -> steps == 57)) winner = player;
        else if (roll != 6) turn = (turn + 1) % 4;
    }
}

Kotlin

Ludo.kt

package interview.ludo

class Ludo {
    private val tokens = Array(4) { IntArray(4) { -1 } }
    private val safe = setOf(0, 8, 13, 21, 26, 34, 39, 47)
    var turn = 0
        private set
    var winner: Int? = null
        private set

    fun position(player: Int, token: Int) = tokens[player][token]

    fun legalTokens(roll: Int): List<Int> {
        require(roll in 1..6)
        return (0..3).filter { token ->
            val steps = tokens[turn][token]
            if (steps == -1) roll == 6 else steps < 57 && steps + roll <= 57
        }
    }

    fun move(player: Int, token: Int?, roll: Int) {
        check(winner == null && player == turn) { "Not this player's turn" }
        val legal = legalTokens(roll)
        if (legal.isEmpty()) {
            require(token == null) { "Pass when no move is available" }
            turn = (turn + 1) % 4
            return
        }
        require(token != null && token in legal)
        val previous = tokens[player][token]
        val next = if (previous == -1) 0 else previous + roll
        tokens[player][token] = next
        if (next < 52) {
            val square = (player * 13 + next) % 52
            if (square !in safe) {
                for (opponent in 0..3) for (other in 0..3) {
                    val steps = tokens[opponent][other]
                    if (opponent != player && steps in 0..51 && (opponent * 13 + steps) % 52 == square) {
                        tokens[opponent][other] = -1
                    }
                }
            }
        }
        if (tokens[player].all { it == 57 }) winner = player
        else if (roll != 6) turn = (turn + 1) % 4
    }
}

package interview.ludo

class Ludo {
    private val tokens = Array(4) { IntArray(4) { -1 } }
    private val safe = setOf(0, 8, 13, 21, 26, 34, 39, 47)
    var turn = 0
        private set
    var winner: Int? = null
        private set

    fun position(player: Int, token: Int) = tokens[player][token]

    fun legalTokens(roll: Int): List<Int> {
        require(roll in 1..6)
        return (0..3).filter { token ->
            val steps = tokens[turn][token]
            if (steps == -1) roll == 6 else steps < 57 && steps + roll <= 57
        }
    }

    fun move(player: Int, token: Int?, roll: Int) {
        check(winner == null && player == turn) { "Not this player's turn" }
        val legal = legalTokens(roll)
        if (legal.isEmpty()) {
            require(token == null) { "Pass when no move is available" }
            turn = (turn + 1) % 4
            return
        }
        require(token != null && token in legal)
        val previous = tokens[player][token]
        val next = if (previous == -1) 0 else previous + roll
        tokens[player][token] = next
        if (next < 52) {
            val square = (player * 13 + next) % 52
            if (square !in safe) {
                for (opponent in 0..3) for (other in 0..3) {
                    val steps = tokens[opponent][other]
                    if (opponent != player && steps in 0..51 && (opponent * 13 + steps) % 52 == square) {
                        tokens[opponent][other] = -1
                    }
                }
            }
        }
        if (tokens[player].all { it == 57 }) winner = player
        else if (roll != 6) turn = (turn + 1) % 4
    }
}

Follow-up questions

A roll goes past home?

“That token is not a legal choice because reaching home requires an exact roll.” A token at step 55 can move with a 2 to reach 57, but not with a 3. Let the player choose another legal token. If none can move, they must pass. The turn advances on a pass in this version, including a six with no legal move.

Two tokens share a safe square?

“They both stay there because capture is disabled on safe squares.” Compare each token's shared board square, since different players have different starting points. On an unsafe shared square, this version sends opposing tokens back to their yards. Tokens on their private home paths cannot be captured.

A different local rule set?

“I would agree on one rule before changing the code.” For example, if a successful six should no longer grant an extra turn, remove the six check from the final turn update. Entry still requires a six. This fragment replaces that final update after movement and capture.

Kotlin

if (tokens[player].all { it == 57 }) winner = player
else turn = (turn + 1) % 4

Java

boolean finished = true;
for (int steps : tokens[player]) finished &= steps == 57;
if (finished) winner = player;
else turn = (turn + 1) % 4;

If a variant adds a penalty for three consecutive sixes, also track that count per turn and reset it when the turn ends. Do not add every regional rule before agreeing on the interview scope.

What should I test?

“A token in the yard should enter only on six, and a successful six should keep the turn under the original rules.” A roll with no legal token should allow only a pass. Unsafe squares should capture, safe squares should not, and overshooting home should be rejected. Bringing all four tokens home should declare the winner and reject later moves.

Extended implementation and optional features

This reference explores a larger scope. Use it after you can explain and write the interview version. Its extra types and features are not required for the scope above.

Java

com.androidinterview.ludo.game.Game.java

package com.androidinterview.ludo.game;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.List;
import java.util.function.IntSupplier;

import com.androidinterview.ludo.model.Move;
import com.androidinterview.ludo.model.Token;
import com.androidinterview.ludo.rules.MoveValidator;

// The turn loop, and it stays short because it delegates twice. The validator
// says what is legal and the strategy says what is played, so this class only
// owns turn order, extra turns and the win check.
public final class Game {

    private final MoveValidator validator;
    private final IntSupplier dice;
    private final Deque<Player> turnOrder = new ArrayDeque<>();
    private final List<Token> allTokens;

    private Player winner;

    public Game(MoveValidator validator, IntSupplier dice, List<Player> players) {
        this.validator = validator;
        this.dice = dice;
        this.turnOrder.addAll(players);
        this.allTokens = players.stream().flatMap(player -> player.tokens().stream()).toList();
    }

    public Player winner() {
        return winner;
    }

    public void play() {
        while (winner == null) {
            playTurn();
        }
    }

    // One player's whole turn, including any extra rolls a six or a capture
    // earns them.
    public void playTurn() {
        Player player = turnOrder.poll();
        int sixes = 0;
        boolean rollAgain = true;

        while (rollAgain) {
            int roll = dice.getAsInt();
            sixes = roll == 6 ? sixes + 1 : 0;
            if (sixes == 3) {
                // Three sixes forfeits the turn and the third roll is not
                // played at all.
                break;
            }
            List<Move> legal = validator.legalMoves(player.tokens(), allTokens, roll);
            if (legal.isEmpty()) {
                // No legal move is a normal outcome, not an error. Forgetting
                // this is the most common bug in a ludo implementation.
                break;
            }
            Move move = player.strategy().choose(legal);
            apply(move);
            if (player.hasWon()) {
                winner = player;
                return;
            }
            rollAgain = roll == 6 || move.isCapture();
        }
        turnOrder.add(player);
    }

    private void apply(Move move) {
        move.token().moveTo(move.toSteps());
        move.captured().forEach(Token::returnToYard);
    }
}

package com.androidinterview.ludo.game;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.List;
import java.util.function.IntSupplier;

import com.androidinterview.ludo.model.Move;
import com.androidinterview.ludo.model.Token;
import com.androidinterview.ludo.rules.MoveValidator;

public final class Game {

    private final MoveValidator validator;
    private final IntSupplier dice;
    private final Deque<Player> turnOrder = new ArrayDeque<>();
    private final List<Token> allTokens;

    private Player winner;

    public Game(MoveValidator validator, IntSupplier dice, List<Player> players) {
        this.validator = validator;
        this.dice = dice;
        this.turnOrder.addAll(players);
        this.allTokens = players.stream().flatMap(player -> player.tokens().stream()).toList();
    }

    public Player winner() {
        return winner;
    }

    public void play() {
        while (winner == null) {
            playTurn();
        }
    }

    public void playTurn() {
        Player player = turnOrder.poll();
        int sixes = 0;
        boolean rollAgain = true;

        while (rollAgain) {
            int roll = dice.getAsInt();
            sixes = roll == 6 ? sixes + 1 : 0;
            if (sixes == 3) {
                break;
            }
            List<Move> legal = validator.legalMoves(player.tokens(), allTokens, roll);
            if (legal.isEmpty()) {
                break;
            }
            Move move = player.strategy().choose(legal);
            apply(move);
            if (player.hasWon()) {
                winner = player;
                return;
            }
            rollAgain = roll == 6 || move.isCapture();
        }
        turnOrder.add(player);
    }

    private void apply(Move move) {
        move.token().moveTo(move.toSteps());
        move.captured().forEach(Token::returnToYard);
    }
}

com.androidinterview.ludo.game.Player.java

package com.androidinterview.ludo.game;

import java.util.List;
import java.util.stream.IntStream;

import com.androidinterview.ludo.model.Color;
import com.androidinterview.ludo.model.Token;
import com.androidinterview.ludo.rules.MoveSelectionStrategy;

// A player is a colour, four tokens and a way of choosing. The choosing is a
// strategy, so a person and three bots of different difficulty sit at the same
// table with no branching anywhere in the game.
public record Player(String name, Color color, List<Token> tokens, MoveSelectionStrategy strategy) {

    public static Player of(String name, Color color, MoveSelectionStrategy strategy) {
        return new Player(name, color, IntStream.range(0, 4).mapToObj(id -> new Token(color, id)).toList(), strategy);
    }

    public boolean hasWon() {
        return tokens.stream().allMatch(Token::isHome);
    }
}

package com.androidinterview.ludo.game;

import java.util.List;
import java.util.stream.IntStream;

import com.androidinterview.ludo.model.Color;
import com.androidinterview.ludo.model.Token;
import com.androidinterview.ludo.rules.MoveSelectionStrategy;

public record Player(String name, Color color, List<Token> tokens, MoveSelectionStrategy strategy) {

    public static Player of(String name, Color color, MoveSelectionStrategy strategy) {
        return new Player(name, color, IntStream.range(0, 4).mapToObj(id -> new Token(color, id)).toList(), strategy);
    }

    public boolean hasWon() {
        return tokens.stream().allMatch(Token::isHome);
    }
}

com.androidinterview.ludo.model.Board.java

package com.androidinterview.ludo.model;

import java.util.Set;

// The geometry, and nothing else. It answers one question that matters, which
// shared cell is this token standing on, and one that supports a rule variant,
// is that cell safe.
public final class Board {

    public static final int TRACK_CELLS = 52;

    // Steps 0 to 50 are the shared track, steps 51 to 56 are the private home
    // column, and step 56 is home. One number line for the whole journey.
    public static final int LAST_TRACK_STEP = 50;
    public static final int HOME_STEP = 56;

    private final Set<Integer> safeCells;

    public Board() {
        // The four entry cells and the four star cells eight ahead of them.
        this(Set.of(0, 8, 13, 21, 26, 34, 39, 47));
    }

    public Board(Set<Integer> safeCells) {
        this.safeCells = safeCells;
    }

    // The only place steps become a cell, and only for a token still on the
    // shared track. Two colours collide when this returns the same number.
    public int cellAt(Color color, int steps) {
        return (color.entryCell() + steps) % TRACK_CELLS;
    }

    public int cellOf(Token token) {
        return cellAt(token.color(), token.steps());
    }

    public boolean isSafe(int cell) {
        return safeCells.contains(cell);
    }
}

package com.androidinterview.ludo.model;

import java.util.Set;

public final class Board {

    public static final int TRACK_CELLS = 52;

    public static final int LAST_TRACK_STEP = 50;
    public static final int HOME_STEP = 56;

    private final Set<Integer> safeCells;

    public Board() {
        this(Set.of(0, 8, 13, 21, 26, 34, 39, 47));
    }

    public Board(Set<Integer> safeCells) {
        this.safeCells = safeCells;
    }

    public int cellAt(Color color, int steps) {
        return (color.entryCell() + steps) % TRACK_CELLS;
    }

    public int cellOf(Token token) {
        return cellAt(token.color(), token.steps());
    }

    public boolean isSafe(int cell) {
        return safeCells.contains(cell);
    }
}

com.androidinterview.ludo.model.Color.java

package com.androidinterview.ludo.model;

// A colour ties a player, four tokens, a yard and a home column together. It
// also carries where that colour joins the shared track, which is the only
// per colour number the rest of the design needs.
public enum Color {
    RED(0),
    GREEN(13),
    YELLOW(26),
    BLUE(39);

    private final int entryCell;

    Color(int entryCell) {
        this.entryCell = entryCell;
    }

    public int entryCell() {
        return entryCell;
    }
}

package com.androidinterview.ludo.model;

public enum Color {
    RED(0),
    GREEN(13),
    YELLOW(26),
    BLUE(39);

    private final int entryCell;

    Color(int entryCell) {
        this.entryCell = entryCell;
    }

    public int entryCell() {
        return entryCell;
    }
}

com.androidinterview.ludo.model.Move.java

package com.androidinterview.ludo.model;

import java.util.List;

// A candidate move, already knowing what it would capture. The validator works
// that out once, so the game does not have to recompute it when it applies the
// move, and a bot can score the move without touching the board.
public record Move(Token token, int fromSteps, int toSteps, List<Token> captured) {

    public boolean isCapture() {
        return !captured.isEmpty();
    }
}

package com.androidinterview.ludo.model;

import java.util.List;

public record Move(Token token, int fromSteps, int toSteps, List<Token> captured) {

    public boolean isCapture() {
        return !captured.isEmpty();
    }
}

com.androidinterview.ludo.model.Token.java

package com.androidinterview.ludo.model;

// A token stores how far it has travelled, not which cell it is standing on.
// Every colour enters the track at a different place, so an absolute cell
// would force per colour arithmetic into every rule. Steps travelled makes all
// four colours identical, and it makes the home column a continuation of the
// same number line rather than a special case.
public final class Token {

    public static final int YARD = -1;

    private final Color color;
    private final int id;
    private int steps = YARD;

    public Token(Color color, int id) {
        this.color = color;
        this.id = id;
    }

    public Color color() {
        return color;
    }

    public int id() {
        return id;
    }

    public int steps() {
        return steps;
    }

    // The four token states are derived, never stored. A stored state field is
    // a second source of truth that can disagree with the step count.
    public boolean isInYard() {
        return steps == YARD;
    }

    public boolean isHome() {
        return steps == Board.HOME_STEP;
    }

    public boolean isOnSharedTrack() {
        return steps >= 0 && steps <= Board.LAST_TRACK_STEP;
    }

    public void moveTo(int steps) {
        this.steps = steps;
    }

    public void returnToYard() {
        this.steps = YARD;
    }

    @Override
    public String toString() {
        return color + " " + id;
    }
}

package com.androidinterview.ludo.model;

public final class Token {

    public static final int YARD = -1;

    private final Color color;
    private final int id;
    private int steps = YARD;

    public Token(Color color, int id) {
        this.color = color;
        this.id = id;
    }

    public Color color() {
        return color;
    }

    public int id() {
        return id;
    }

    public int steps() {
        return steps;
    }

    public boolean isInYard() {
        return steps == YARD;
    }

    public boolean isHome() {
        return steps == Board.HOME_STEP;
    }

    public boolean isOnSharedTrack() {
        return steps >= 0 && steps <= Board.LAST_TRACK_STEP;
    }

    public void moveTo(int steps) {
        this.steps = steps;
    }

    public void returnToYard() {
        this.steps = YARD;
    }

    @Override
    public String toString() {
        return color + " " + id;
    }
}

com.androidinterview.ludo.rules.MoveSelectionStrategy.java

package com.androidinterview.ludo.rules;

import java.util.Comparator;
import java.util.List;

import com.androidinterview.ludo.model.Move;
import com.androidinterview.ludo.model.Token;

// The choice, which is the whole thing that makes ludo harder than snake and
// ladder. The validator says which moves are legal, this says which one is
// played, and swapping a person for a bot changes nothing else.
@FunctionalInterface
public interface MoveSelectionStrategy {

    // The caller guarantees the list is not empty. An empty list is a passed
    // turn and the game loop deals with it, so no strategy has to.
    Move choose(List<Move> legalMoves);

    // Deterministic, so a game replays identically in a test. A bot that needs
    // a seeded random generator to be testable is a worse bot.
    static MoveSelectionStrategy firstLegal() {
        return moves -> moves.get(0);
    }

    // Take a capture, otherwise get a token out of the yard, otherwise push
    // the token that is furthest along. Three lines of heuristic, and it plays
    // a recognisable game.
    static MoveSelectionStrategy aggressive() {
        return moves -> moves.stream().max(Comparator.comparingInt(MoveSelectionStrategy::score)).orElseThrow();
    }

    private static int score(Move move) {
        if (move.isCapture()) {
            return 200 + move.captured().size();
        }
        if (move.fromSteps() == Token.YARD) {
            return 100;
        }
        return move.toSteps();
    }
}

package com.androidinterview.ludo.rules;

import java.util.Comparator;
import java.util.List;

import com.androidinterview.ludo.model.Move;
import com.androidinterview.ludo.model.Token;

@FunctionalInterface
public interface MoveSelectionStrategy {

    Move choose(List<Move> legalMoves);

    static MoveSelectionStrategy firstLegal() {
        return moves -> moves.get(0);
    }

    static MoveSelectionStrategy aggressive() {
        return moves -> moves.stream().max(Comparator.comparingInt(MoveSelectionStrategy::score)).orElseThrow();
    }

    private static int score(Move move) {
        if (move.isCapture()) {
            return 200 + move.captured().size();
        }
        if (move.fromSteps() == Token.YARD) {
            return 100;
        }
        return move.toSteps();
    }
}

com.androidinterview.ludo.rules.MoveValidator.java

package com.androidinterview.ludo.rules;

import java.util.ArrayList;
import java.util.List;

import com.androidinterview.ludo.model.Board;
import com.androidinterview.ludo.model.Move;
import com.androidinterview.ludo.model.Token;

// Every rule in the game is in this one class. Keeping it out of the game loop
// is the biggest structural decision in the design, because it turns a sixty
// line if chain into a list the caller can look at, score and choose from.
public final class MoveValidator {

    private final Board board;

    public MoveValidator(Board board) {
        this.board = board;
    }

    // The list may be empty, and that is a real outcome, not an error. All
    // four tokens in the yard and a roll of three means the turn simply passes.
    public List<Move> legalMoves(List<Token> playerTokens, List<Token> allTokens, int roll) {
        List<Move> moves = new ArrayList<>();
        for (Token token : playerTokens) {
            if (token.isHome()) {
                continue;
            }
            if (token.isInYard()) {
                // A six is the only way out of the yard, onto step zero, which
                // is this colour's entry cell.
                if (roll == 6) {
                    moves.add(candidate(token, 0, allTokens));
                }
                continue;
            }
            int destination = token.steps() + roll;
            // The exact finish rule. Overshooting home is not a legal move, so
            // it never reaches the player as an option at all.
            if (destination <= Board.HOME_STEP) {
                moves.add(candidate(token, destination, allTokens));
            }
        }
        return moves;
    }

    private Move candidate(Token token, int destination, List<Token> allTokens) {
        return new Move(token, token.steps(), destination, capturesAt(token, destination, allTokens));
    }

    private List<Token> capturesAt(Token mover, int destination, List<Token> allTokens) {
        // The home column is private, so nothing can be captured there.
        if (destination > Board.LAST_TRACK_STEP) {
            return List.of();
        }
        int cell = board.cellAt(mover.color(), destination);
        if (board.isSafe(cell)) {
            return List.of();
        }
        List<Token> captured = new ArrayList<>();
        for (Token other : allTokens) {
            if (other.color() != mover.color() && other.isOnSharedTrack() && board.cellOf(other) == cell) {
                captured.add(other);
            }
        }
        return captured;
    }
}

package com.androidinterview.ludo.rules;

import java.util.ArrayList;
import java.util.List;

import com.androidinterview.ludo.model.Board;
import com.androidinterview.ludo.model.Move;
import com.androidinterview.ludo.model.Token;

public final class MoveValidator {

    private final Board board;

    public MoveValidator(Board board) {
        this.board = board;
    }

    public List<Move> legalMoves(List<Token> playerTokens, List<Token> allTokens, int roll) {
        List<Move> moves = new ArrayList<>();
        for (Token token : playerTokens) {
            if (token.isHome()) {
                continue;
            }
            if (token.isInYard()) {
                if (roll == 6) {
                    moves.add(candidate(token, 0, allTokens));
                }
                continue;
            }
            int destination = token.steps() + roll;
            if (destination <= Board.HOME_STEP) {
                moves.add(candidate(token, destination, allTokens));
            }
        }
        return moves;
    }

    private Move candidate(Token token, int destination, List<Token> allTokens) {
        return new Move(token, token.steps(), destination, capturesAt(token, destination, allTokens));
    }

    private List<Token> capturesAt(Token mover, int destination, List<Token> allTokens) {
        if (destination > Board.LAST_TRACK_STEP) {
            return List.of();
        }
        int cell = board.cellAt(mover.color(), destination);
        if (board.isSafe(cell)) {
            return List.of();
        }
        List<Token> captured = new ArrayList<>();
        for (Token other : allTokens) {
            if (other.color() != mover.color() && other.isOnSharedTrack() && board.cellOf(other) == cell) {
                captured.add(other);
            }
        }
        return captured;
    }
}

Kotlin

com.androidinterview.ludo.game.Game.kt

package com.androidinterview.ludo.game

import com.androidinterview.ludo.model.Color
import com.androidinterview.ludo.model.Move
import com.androidinterview.ludo.model.Token
import com.androidinterview.ludo.rules.MoveSelectionStrategy
import com.androidinterview.ludo.rules.MoveValidator
import kotlin.random.Random

typealias Dice = () -> Int

fun dice(random: Random = Random.Default): Dice = { random.nextInt(1, 7) }

// A player is a colour, four tokens and a way of choosing. Choosing is a
// strategy, so a person and three bots of different difficulty sit at one
// table with no branching in the game.
class Player(val name: String, val color: Color, val strategy: MoveSelectionStrategy) {
    val tokens = List(4) { id -> Token(color, id) }
    val hasWon get() = tokens.all { it.isHome }
}

// The turn loop, short because it delegates twice. The validator says what is
// legal and the strategy says what is played, so this class owns turn order,
// extra turns and the win check, and nothing else.
class Game(
    private val validator: MoveValidator,
    private val dice: Dice,
    players: List<Player>,
) {

    private val turnOrder = ArrayDeque(players)
    private val allTokens = players.flatMap { it.tokens }

    var winner: Player? = null
        private set

    fun play() {
        while (winner == null) playTurn()
    }

    // One player's whole turn, including any extra rolls a six or a capture
    // earns them.
    fun playTurn() {
        val player = turnOrder.removeFirst()
        var sixes = 0
        var rollAgain = true

        while (rollAgain) {
            val roll = dice()
            sixes = if (roll == 6) sixes + 1 else 0
            // Three sixes forfeits the turn and the third roll is not played.
            if (sixes == 3) break

            val legal = validator.legalMoves(player.tokens, allTokens, roll)
            // No legal move is a normal outcome, not an error. Forgetting this
            // is the most common bug in a ludo implementation.
            if (legal.isEmpty()) break

            val move = player.strategy(legal)
            apply(move)
            if (player.hasWon) {
                winner = player
                return
            }
            // A six or a capture earns one more roll, never two.
            rollAgain = roll == 6 || move.isCapture
        }
        turnOrder.addLast(player)
    }

    private fun apply(move: Move) {
        move.token.moveTo(move.toSteps)
        move.captured.forEach(Token::returnToYard)
    }
}

package com.androidinterview.ludo.game

import com.androidinterview.ludo.model.Color
import com.androidinterview.ludo.model.Move
import com.androidinterview.ludo.model.Token
import com.androidinterview.ludo.rules.MoveSelectionStrategy
import com.androidinterview.ludo.rules.MoveValidator
import kotlin.random.Random

typealias Dice = () -> Int

fun dice(random: Random = Random.Default): Dice = { random.nextInt(1, 7) }

class Player(val name: String, val color: Color, val strategy: MoveSelectionStrategy) {
    val tokens = List(4) { id -> Token(color, id) }
    val hasWon get() = tokens.all { it.isHome }
}

class Game(
    private val validator: MoveValidator,
    private val dice: Dice,
    players: List<Player>,
) {

    private val turnOrder = ArrayDeque(players)
    private val allTokens = players.flatMap { it.tokens }

    var winner: Player? = null
        private set

    fun play() {
        while (winner == null) playTurn()
    }

    fun playTurn() {
        val player = turnOrder.removeFirst()
        var sixes = 0
        var rollAgain = true

        while (rollAgain) {
            val roll = dice()
            sixes = if (roll == 6) sixes + 1 else 0
            if (sixes == 3) break

            val legal = validator.legalMoves(player.tokens, allTokens, roll)
            if (legal.isEmpty()) break

            val move = player.strategy(legal)
            apply(move)
            if (player.hasWon) {
                winner = player
                return
            }
            rollAgain = roll == 6 || move.isCapture
        }
        turnOrder.addLast(player)
    }

    private fun apply(move: Move) {
        move.token.moveTo(move.toSteps)
        move.captured.forEach(Token::returnToYard)
    }
}

com.androidinterview.ludo.model.Board.kt

package com.androidinterview.ludo.model

// A colour ties a player, four tokens, a yard and a home column together, and
// carries the one per colour number the rest of the design needs, where that
// colour joins the shared track.
enum class Color(val entryCell: Int) {
    RED(0),
    GREEN(13),
    YELLOW(26),
    BLUE(39),
}

const val YARD = -1

// Steps 0 to 50 are the shared track, 51 to 56 are the private home column,
// and 56 is home. One number line for the whole journey.
const val LAST_TRACK_STEP = 50
const val HOME_STEP = 56
const val TRACK_CELLS = 52

// A token stores how far it has travelled, not the cell it stands on. Each
// colour joins the track somewhere different, so an absolute cell would push
// per colour arithmetic into every rule. Steps make all four colours identical
// and turn the home column into more of the same number line.
class Token(val color: Color, val id: Int) {

    var steps: Int = YARD
        private set

    // The four states are derived, never stored. A stored state field is a
    // second source of truth that can disagree with the step count.
    val isInYard get() = steps == YARD
    val isHome get() = steps == HOME_STEP
    val isOnSharedTrack get() = steps in 0..LAST_TRACK_STEP

    fun moveTo(steps: Int) {
        this.steps = steps
    }

    fun returnToYard() {
        steps = YARD
    }

    override fun toString() = "$color $id"
}

// A candidate move that already knows what it would capture. The validator
// works that out once, so the game does not repeat it and a bot can score a
// move without touching the board.
data class Move(val token: Token, val fromSteps: Int, val toSteps: Int, val captured: List<Token>) {
    val isCapture get() = captured.isNotEmpty()
}

// The geometry, and nothing else. Safe cells are a constructor argument
// because which cells are safe is exactly the rule that varies by region.
class Board(private val safeCells: Set<Int> = setOf(0, 8, 13, 21, 26, 34, 39, 47)) {

    // The only place steps become a cell, and only for a token still on the
    // shared track. Two colours collide when this returns the same number.
    fun cellAt(color: Color, steps: Int) = (color.entryCell + steps) % TRACK_CELLS

    fun cellOf(token: Token) = cellAt(token.color, token.steps)

    fun isSafe(cell: Int) = cell in safeCells
}

package com.androidinterview.ludo.model

enum class Color(val entryCell: Int) {
    RED(0),
    GREEN(13),
    YELLOW(26),
    BLUE(39),
}

const val YARD = -1

const val LAST_TRACK_STEP = 50
const val HOME_STEP = 56
const val TRACK_CELLS = 52

class Token(val color: Color, val id: Int) {

    var steps: Int = YARD
        private set

    val isInYard get() = steps == YARD
    val isHome get() = steps == HOME_STEP
    val isOnSharedTrack get() = steps in 0..LAST_TRACK_STEP

    fun moveTo(steps: Int) {
        this.steps = steps
    }

    fun returnToYard() {
        steps = YARD
    }

    override fun toString() = "$color $id"
}

data class Move(val token: Token, val fromSteps: Int, val toSteps: Int, val captured: List<Token>) {
    val isCapture get() = captured.isNotEmpty()
}

class Board(private val safeCells: Set<Int> = setOf(0, 8, 13, 21, 26, 34, 39, 47)) {

    fun cellAt(color: Color, steps: Int) = (color.entryCell + steps) % TRACK_CELLS

    fun cellOf(token: Token) = cellAt(token.color, token.steps)

    fun isSafe(cell: Int) = cell in safeCells
}

com.androidinterview.ludo.rules.Rules.kt

package com.androidinterview.ludo.rules

import com.androidinterview.ludo.model.Board
import com.androidinterview.ludo.model.HOME_STEP
import com.androidinterview.ludo.model.LAST_TRACK_STEP
import com.androidinterview.ludo.model.Move
import com.androidinterview.ludo.model.Token
import com.androidinterview.ludo.model.YARD

// The choice, which is the whole thing that makes ludo harder than snake and
// ladder. The validator says what is legal, this says what is played, and it
// is a function type because it has one job.
//
// The caller guarantees the list is not empty. An empty list is a passed turn
// and the game loop deals with it, so no strategy has to.
typealias MoveSelectionStrategy = (legalMoves: List<Move>) -> Move

// Deterministic, so a game replays identically in a test. A bot that needs a
// seeded random generator to be testable is a worse bot.
val FirstLegal: MoveSelectionStrategy = { moves -> moves.first() }

// Take a capture, otherwise leave the yard, otherwise push the token furthest
// along. Three lines of heuristic and it plays a recognisable game.
val Aggressive: MoveSelectionStrategy = { moves ->
    moves.maxBy { move ->
        when {
            move.isCapture -> 200 + move.captured.size
            move.fromSteps == YARD -> 100
            else -> move.toSteps
        }
    }
}

// Every rule in the game is in this one class. Keeping it out of the turn loop
// is the biggest structural decision here, because it turns a sixty line if
// chain into a list the caller can look at, score and choose from.
class MoveValidator(private val board: Board) {

    // The list may be empty, and that is a real outcome rather than an error.
    // Four tokens in the yard and a roll of three means the turn passes.
    fun legalMoves(playerTokens: List<Token>, allTokens: List<Token>, roll: Int): List<Move> =
        playerTokens.mapNotNull { token ->
            when {
                token.isHome -> null
                // A six is the only way out of the yard, onto step zero, which
                // is this colour's entry cell.
                token.isInYard -> if (roll == 6) token.candidate(0, allTokens) else null
                // The exact finish rule. Overshooting home is not legal, so it
                // never reaches the player as an option at all.
                token.steps + roll <= HOME_STEP -> token.candidate(token.steps + roll, allTokens)
                else -> null
            }
        }

    private fun Token.candidate(destination: Int, allTokens: List<Token>) =
        Move(this, steps, destination, capturesAt(destination, allTokens))

    private fun Token.capturesAt(destination: Int, allTokens: List<Token>): List<Token> {
        // The home column is private, so nothing can be captured there.
        if (destination > LAST_TRACK_STEP) return emptyList()
        val cell = board.cellAt(color, destination)
        if (board.isSafe(cell)) return emptyList()
        return allTokens.filter { it.color != color && it.isOnSharedTrack && board.cellOf(it) == cell }
    }
}

package com.androidinterview.ludo.rules

import com.androidinterview.ludo.model.Board
import com.androidinterview.ludo.model.HOME_STEP
import com.androidinterview.ludo.model.LAST_TRACK_STEP
import com.androidinterview.ludo.model.Move
import com.androidinterview.ludo.model.Token
import com.androidinterview.ludo.model.YARD

typealias MoveSelectionStrategy = (legalMoves: List<Move>) -> Move

val FirstLegal: MoveSelectionStrategy = { moves -> moves.first() }

val Aggressive: MoveSelectionStrategy = { moves ->
    moves.maxBy { move ->
        when {
            move.isCapture -> 200 + move.captured.size
            move.fromSteps == YARD -> 100
            else -> move.toSteps
        }
    }
}

class MoveValidator(private val board: Board) {

    fun legalMoves(playerTokens: List<Token>, allTokens: List<Token>, roll: Int): List<Move> =
        playerTokens.mapNotNull { token ->
            when {
                token.isHome -> null
                token.isInYard -> if (roll == 6) token.candidate(0, allTokens) else null
                token.steps + roll <= HOME_STEP -> token.candidate(token.steps + roll, allTokens)
                else -> null
            }
        }

    private fun Token.candidate(destination: Int, allTokens: List<Token>) =
        Move(this, steps, destination, capturesAt(destination, allTokens))

    private fun Token.capturesAt(destination: Int, allTokens: List<Token>): List<Token> {
        if (destination > LAST_TRACK_STEP) return emptyList()
        val cell = board.cellAt(color, destination)
        if (board.isSafe(cell)) return emptyList()
        return allTokens.filter { it.color != color && it.isOnSharedTrack && board.cellOf(it) == cell }
    }
}