Snake and Ladder Game Low Level Design

🙏
জয় শ্রী রাম
🕉

Algorithms and Data Structures: TheAlgorist.com
System Design: DistributedComputing.dev
Low Level Design: LowLevelDesign.io
Frontend Engineering: FrontendEngineering.io

Problem Statement:

Design Snake and Ladder game.
Cells in the snake and ladder game board are labeled from 1 to n² in a Boustrophedon style starting from the bottom left of the board and alternating direction each row.
Rules of Snake and Ladder game:

Start from cell 1.
Throw the dice and whatever number you get, move on the number of cells on the board.
If you reach a cell which is base of a ladder, then you have to climb up that ladder without a dice throw.
If you reach a cell is mouth of the snake, has to go down to the tail of snake without a dice throw.

Follow-up question:
Implement a method that returns the least number of moves required to reach the square n². If it is not possible to reach the square, return -1.

For the below board the least number of moves required to reach the square with value 36 is 4 by taking below moves:
1 --1st move--> (6 --ladder--> 18) --2nd move-> (15 --ladder-> 22) --3rd move--> (23 --ladder--> 35) --4th move-> 36

Solution:

Detailed Low Level Design:

While desigining the snake and ladder game board the main challenge is how to represent the snakes and ladders in the board. Let's look at how many different types of squares we can have in a snake and ladder board:

Squares that have bottom-end of a ladder in it:
Dice cannot stay in this square, because once the dice reaches this square it climbs up the ladder and reaches the square that has the top-end of the ladder.
Squares that have top-end of a ladder in it:
This does not have any special implication. If dice reaches this square it stays there. These squares are actually like the regular squares.
Squares that have snake mouth in it:
Dice cannot stay in this square, because once the dice reaches this square it goes down to the square that has the tail of the snake.
Squares that have snake tail in it:
This does not have any special implication. If dice reaches this square it stays there. These squares are actually like the regular squares.
Regular square:
Any square that does not have any snake or ladder in it.

Since dice cannot stay in the squares that have either ladder bottom-end or a snake mouth, we should replace the values in those squares with the values of the squares to which they lead.
Let's see following this above rule how we could represent the above snake and ladder board:

[
[36, 35, 22, 33, 32, 20],
[12, 26, 27, 28, 29, 30],
[24, 35, 22, 28,  5, 19],
[13, 14, 22,  2, 17, 18],
[12, 14, 10,  9,  8,  7],
[ 1,  2,  3,  4,  5, 18]
]

Using the discussion so far we get the below object-oriented design for Snake and Ladder game:

Java:


public class SnakeAndLadder {
    int[][] board;
    int dicePosition;
    int dimension;
    int finishValue;
    
    public SnakeAndLadder(int[][] squareMatrix) {
        board = squareMatrix;
        dicePosition = 1;
        dimension = squareMatrix.length;
        finishValue = dimension * dimension;
    }
    
    public boolean isgameOver() {
        return dicePosition == (finishValue);
    }
    
    // return position of dice after making next move
    public int rollDice() {
       int random = rand(1, 6);
        int nextPosition = dicePosition + random;
        if (nextPosition > finishValue) {
            return dicePosition;
        }
        int[] coordinateOfNewPosition = getCoordinate(dicePosition);
        return board[coordinateOfNewPosition[0]][coordinateOfNewPosition[1]]; // instead of returning
        // new dice position directly we are getting the value from board because
        // the corresponding value in board might be different of the new dice position
        // has snake mouth or ladder bottom-end
    }
    
    // Random number between lower and higher, both inclusive
    // [lower, higher]
    private int rand(int lower, int higher) {
        return lower + (int)(Math.random() * (higher - lower + 1)); // Range of Math.random() = [0.0, 1.0)
    }

    // method to find coordinate of squares
    // in the snake and ladder game board in which squares are labeled from 1 to (n * n)
    // in a Boustrophedon style starting from the bottom left of the board and
    // alternating direction each row.
    private int[] getCoordinate(int num) {
        boolean rightToLeftRow = ((num - 1) / dimension) % 2 != 0;
        int row = (dimension - 1) - ((num - 1) / dimension);
        int col = (num % dimension) - 1 == -1 ? (dimension - 1) : (num % dimension) - 1;
        if (rightToLeftRow) {
            col = dimension - 1 - col;
        }
        return new int[] {row, col};
    }
}

Python:


import random
import math


class SnakeAndLadder:
    def __init__(self, squareMatrix):
        self.board = [[]]
        self.dicePosition = 0
        self.dimension = 0
        self.finishValue = 0

        self.board = squareMatrix
        self.dicePosition = 1
        self.dimension = len(squareMatrix)
        self.finishValue = self.dimension * self.dimension

    def isgameOver(self):
        return self.dicePosition == (self.finishValue)

    def rollDice(self):
        random = self._rand(1, 6)
        nextPosition = self.dicePosition + random
        if nextPosition > self.finishValue:
            return self.dicePosition
        coordinateOfNewPosition = self._getCoordinate(self.dicePosition)
        return self.board[coordinateOfNewPosition[0]][coordinateOfNewPosition[1]]

    def _rand(self, lower, higher):
        return lower + int((random.random() * (higher - lower + 1)))

    def _getCoordinate(self, num):
        rightToLeftRow = math.fmod((math.trunc((num - 1) / float(self.dimension))), 2) != 0
        row = (self.dimension - 1) - (math.trunc((num - 1) / float(self.dimension)))
        col = (self.dimension - 1) if (math.fmod(num, self.dimension)) - 1 == -1 else (math.fmod(num,
                                                                                                 self.dimension)) - 1
        if rightToLeftRow:
            col = self.dimension - 1 - col
        return [row, col]

Finding the least number of moves required to reach the finish square:

What we are looking for here is the shortest path from start square (which is 1) to finish square. Every time roll dice we move from one square to another (except of course when the the dice roll tries to lead us to a square greater than the finish square). So these squares could be thought of as nodes in a directed graph. If we are at square i then the child nodes of square i would be (i + 1), (i + 2), (i + 3), (i + 4), (i + 5) and (i + 6).
Weights of all the edges are 1. From the knowledge we have gained from our Algorithms course in the BFS chapter that BFS is an efficient way to find shortest path between source and destination in a graph with all edges with edge-weight equal to one. We have implemented this algorithm in below code. I have discussed in more details in the inline comments in the code below:

Java:


class SnakeAndLadder {

    int diceRollSides = 6; // number of sides the dice has

    public int getLeastNumberOfMovesRequiredToReachFinishSquare(int[][] board) {
        int len = board.length;

        // the only time that there would be no solution is if the square (n ^ 2)
        // has a snake mouth, since every time you reach here you go down to some other square
        // so there is no way you can stay at square (n ^ 2)
        if ((len % 2 == 0 && board[0][0] != len * len) 
                    || (len % 2 != 0 && board[0][len - 1] != len * len)) {
            return -1;
        }
        
        int source = 1;
        int destination = len * len;
        
        Queue<Integer> bfsQueue = new ArrayDeque<>();
        Set<Integer> processed = new HashSet<>(); // hashset offers efficient search
        bfsQueue.add(source);
        
        int[] numberOfEdgesFromSource = new int[len * len];
        
        // BFS
        while (!bfsQueue.isEmpty()) {
            int parent = bfsQueue.poll();
            processed.add(parent);
            for (int i = 1; i <= diceRollSides; i++) {
                int[] coordinate = getCoordinate(parent + i, len);
                int cellValue = board[coordinate[0]][coordinate[1]];
                if (!processed.contains(cellValue)) { // do not revisit a square which has already been processed before
                    if (numberOfEdgesFromSource[cellValue - 1] == 0) { // if we have already found a path from source to this node we do not need to update the value since we are interested in the shortest path with all edges with weight 1 
                        numberOfEdgesFromSource[cellValue - 1] = numberOfEdgesFromSource[parent - 1] + 1;
                    }
                    if (cellValue == destination) {
                        return numberOfEdgesFromSource[len * len - 1];
                    }
                    bfsQueue.add(cellValue);
                }
            }
        }
        
        return -1;
    }

    // method to find coordinate of squares
    // in the snake and ladder game board in which squares are labeled from 1 to (n * n) 
    // in a Boustrophedon style starting from the bottom left of the board and 
    // alternating direction each row.
    private int[] getCoordinate(int num, int dimension) {
        boolean rightToLeftRow = ((num - 1) / dimension) % 2 != 0;
        int row = (dimension - 1) - ((num - 1) / dimension);
        int col = (num % dimension) - 1 == -1 ? (dimension - 1) : (num % dimension) - 1;
        if (rightToLeftRow) {
            col = dimension - 1 - col;
        }
        return new int[] {row, col};
    }
}

Python:


import math


class SnakeAndLadder:

    def __init__(self):
        self.diceRollSides = 6

    def getLeastNumberOfMovesRequiredToReachFinishSquare(self, board):
        board_size = len(board)
        if (math.fmod(board_size, 2) == 0 and board[0][0] != board_size * board_size) or (
                math.fmod(board_size, 2) != 0 and board[0][board_size - 1] != board_size * board_size):
            return -1
        source = 1
        destination = board_size * board_size
        bfsQueue = []
        processed = set()
        bfsQueue.append(source)
        numberOfEdgesFromSource = [0 for _ in range(board_size * board_size)]
        while not len(bfsQueue) == 0:
            parent = bfsQueue.pop()
            processed.add(parent)
            i = 1
            while i <= self.diceRollSides:
                coordinate = self._getCoordinate(parent + i, board_size)
                cellValue = board[coordinate[0]][coordinate[1]]
                if not cellValue in processed:
                    if numberOfEdgesFromSource[cellValue - 1] == 0:
                        numberOfEdgesFromSource[cellValue - 1] = numberOfEdgesFromSource[parent - 1] + 1
                    if cellValue == destination:
                        return numberOfEdgesFromSource[board_size * board_size - 1]
                    bfsQueue.append(cellValue)
                i += 1
        return -1

    @staticmethod
    def _getCoordinate(num, dimension):
        rightToLeftRow = math.fmod((math.trunc((num - 1) / float(dimension))), 2) != 0
        row = (dimension - 1) - (math.trunc((num - 1) / float(dimension)))
        col = (dimension - 1) if (math.fmod(num, dimension)) - 1 == -1 else (math.fmod(num, dimension)) - 1
        if rightToLeftRow:
            col = dimension - 1 - col
        return [row, col]

Updated Code as of June 01, 2022:

Java:


class SnakeAndLadder {
    int diceRollSides = 6; // number of sides the dice has
    public int snakesAndLadders(int[][] board) {
        int len = board.length;
        for (int j = 1; j <= len * len; j++) {
            int[] coord = getCoordinate(j, len);
            if (board[coord[0]][coord[1]] == -1) {
                board[coord[0]][coord[1]] = j;
            }
        }
        
        // the only time that there would be no solution is if the square (n ^ 2)
        // has a snake mouth, since every time you reach here you go down to some other square
        // so there is no way you can stay at square (n ^ 2)
        if ((len % 2 == 0 && board[0][0] != len * len) 
                    || (len % 2 != 0 && board[0][len - 1] != len * len)) {
            return -1;
        }
        
        int source = 1;
        int destination = len * len;
        
        Queue<Integer> bfsQueue = new ArrayDeque<>();
        Set<Integer> visited = new HashSet<>(); // hashset offers efficient search
        bfsQueue.add(source);
        
        int[] numberOfEdgesFromSource = new int[len * len];
        int count = 0;
        // BFS
        while (!bfsQueue.isEmpty()) {
            count++;
            int queueSize = bfsQueue.size();
            for (int i = 0; i < queueSize; i++) {
                int curr = bfsQueue.poll();
                visited.add(curr);
                for (int j = 1; j <= diceRollSides; j++) {
                    int[] coordinate = getCoordinate(curr + j, len);
                    int cellValue = board[coordinate[0]][coordinate[1]];
                    if (cellValue == destination) {
                        return count;
                    }
                    if (!visited.contains(cellValue)) {
                        bfsQueue.add(cellValue);
                    }
                }
            }
        }
        return -1;
    }
    
    private int[] getCoordinate(int num, int dimension) {
        int equivalentZeroBasedIndex = num - 1;
        boolean evenRow = ((num - 1) / dimension) % 2 == 0; // zero based -> row index starts from 0 which is even
                                // all even rows have numbers in ascending order from left to right.
                                // this indexing is done brom bottom to top which 
                                // is reverse of the index order in given matrix/board.
        int row = (dimension - 1) - ((num - 1) / dimension);
        int col = (num - 1) % dimension;
        if (!evenRow) {
            col = dimension - 1 - col;
        }
        return new int[] {row, col};
    }
}

Python:


import math


class SnakeAndLadder:

    def __init__(self):
        self.diceRollSides = 6

    def snakesAndLadders(self, board):
        board_size = len(board)
        j = 1
        while j <= board_size * board_size:
            coord = self._getCoordinate(j, board_size)
            if board[coord[0]][coord[1]] == -1:
                board[coord[0]][coord[1]] = j
            j += 1
        if (math.fmod(board_size, 2) == 0 and board[0][0] != board_size * board_size) or (
                math.fmod(board_size, 2) != 0 and board[0][board_size - 1] != board_size * board_size):
            return -1
        source = 1
        destination = board_size * board_size
        bfsQueue = []
        visited = set()
        bfsQueue.append(source)
        numberOfEdgesFromSource = [0 for _ in range(board_size * board_size)]
        count = 0
        while not len(bfsQueue) == 0:
            count += 1
            queueSize = len(bfsQueue)
            for i in range(0, queueSize):
                curr = bfsQueue.pop()
                visited.add(curr)
                j = 1
                while j <= self.diceRollSides:
                    coordinate = self._getCoordinate(curr + j, board_size)
                    cellValue = board[coordinate[0]][coordinate[1]]
                    if cellValue == destination:
                        return count
                    if cellValue not in visited:
                        bfsQueue.append(cellValue)
                    j += 1
        return -1

    @staticmethod
    def _getCoordinate(num, dimension):
        equivalentZeroBasedIndex = num - 1
        evenRow = math.fmod((math.trunc((num - 1) / float(dimension))), 2) == 0
        row = (dimension - 1) - (math.trunc((num - 1) / float(dimension)))
        col = math.fmod((num - 1), dimension)
        if not evenRow:
            col = dimension - 1 - col
        return [row, col]