# Design a Snake Ladder game

• Data structure you can use to Design a Snake Ladder game

• I understand the problem here is the need of ds to keep board's configuration. An array of Strings may be used as described below.

String[] board = new String[100];
board[0] = ..
board[1] = ..
board[2] = ..
.
.
.
board[20] = "d6"; //denotes that if a player lands on # 21, she must go down to # 6 (d6) due to a snake bite
.
.
.
board[32] = "u47"; //denotes that if a player lands on # 33. she must go up to # 47 (u47) as he climbs up the ladder.
.
.
.

• We can reduce it to a sparse weighted graph, which we can then store as an adjacency list.

• We can use a hashmap to store snakes and ladders.
i.e Key -> startingPosition of snake / ladder
Value -> length of snake / ladder
length is negative for snake
If we are able to find current position in HashMap then next is value with this position as key.
Otherwise next is 1 + currentPosition
It takes O(snake + ladder) space

``````// defualt is 0 in map in c++
class SnakeAndLadder{
private:
map <int, int> length;
public:
int getNext(int current)
{
return current +  length[current] + 1;
}
};``````

• @sehgaldam121

I believe hash map is a good data structure for this design. need one more variable n to define the total game board size. maybe need to define a Player class, which has the current position, and could throw a dice to get a random value from 1 to 6.

• ``````public interface Board {
public void reset();
}
// Should be singleton
public class SnakeBoard implements Board {
List<Snake> snakes;
List<Ladder> ladders;
List<SnakeGamePlayer> players;
Cell[][] cells;
SixFaceDice dice = new SixFaceDice();
SnakeBoard() {
// initialize snakes, ladder, cells & players
}
SnakeBoard(List<SnakeGamePlayer> snakes, List<Ladders> ladders,
List<Player> players, int row, int column) {
// assign member vars
this.cell = new Cell[row][column]
}
boolean winner() {
// return null until no one won the game
}
public void reset() {}
public void bite() {
//  if new position of player is same as anyone of the snake head pos, update player position
}
public void moveUpTheLadder() {}
}

class Ladder {
private int start;
private end;
}

class Snake {
private int[] head;//x,y co-ordinate of player
private  int[] tail;
}

public interface Player {
public int score();
public int move();
}

public SnakeGamePlayer implements Player {
private int pid;
// implement score and move method
public int[]  currPositionOnBoard() {
// return x,y co-ordinate of player in board
}
}

public interface Dice {
public int roll();
}
public class SixFaceDice implements Dice {
private static SixFaceDice s;
public int roll() {
// generate random number between 1 to 6
}
static private SixFaceDice() {
}
public void getSixFaceDice() {
if (s == null) { return new SixFaceDice()}
else {
return this.s;
}
}
}
public class Cell {
List<Integer> ids; // players ids who are in the cell
int num;
int row;
int column;
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.