Data Structure USed for Snake and Ladder game

Question

I came across a interview question "Suggest data structures you would use for snake & ladder game? "

I would use a 2D array (same as we do in chess ) to design each block of game. But is it possible to design it in 1D array ? Many people has suggested this but no one has explained how to do it.

Answer 1

Rules for Snake and Ladder are:

1. There are two players in this game and board size is 100.(10 X 10)
2. Possible outcomes by throwing a dice are 1,2,3,4,5,6.
3. If output is 6 then current player will get a chance again to throw the Dice.
4. If outcome of the Dice is 1,2,3,4,5,6 and player positioned on mouth of snake then his current position will change to tail of snake, and he will not get other chance until he throws a dice which has value 6.
5. If outcome of the Dice is 1,2,3,4,5,6 and player positioned at below of ladder then His current position will change to topmost position of ladder and he will get another chance to throw the dice again.
6. If player's current position+ roll >100 then take the following considerations i. if(roll==6) current player will get the chance again ,otherwise other player will get.
7. Any player reach 100 earlier than other player will be the winner and game will end.

We are passing only one HashMap, which contains the current position as key and next position as value. I think one HashMap will complete all the requirement of the Ladder and Snake,

int playSnakeAndLadder(HashMap<Integer, Integer> hashMap){
    int player1=1, player2=1;// Initial position of players
    int chance=0;// This value show the change of players if chance is odd then player1 will play
                 // if chance is even then player2 will play
    while(1){
        if((player1==100)||(player2==100))// if any of player's position is 100 return chance;
            return chance;// Here chance shows who win the game, if chance is even player1 wins other //wise player2 wins
    int roll=Randon(6);// this will generate random number from 1 to 6.
    if(chance%2==0){
         int key=roll+player1;// new position of player1             
         boolean isLadder=false;// This is for checking the turn current player if againTurn is ture 
         // then the current player will player again.
         if(hashMap.contains(Key)){
             player1=hashMap.getValue(Key);
             // Here player current position will automatically update according to the hashMap.
             // if there is a snake the key value is greater than it mapping value.
             // if there is a ladder then key value is less than it mapping value. 
             if(Key<hashMap.getValue(Key))
                 isLadder=true;// Here player gets ladder.
             if(isLadder==true && roll==6 || isLadder==true)
               chance=chance;
             else
               chance=(chance+1)%2;
         }
         else if(player1+roll>100 && roll!=6)
               chance=(chance+1)%2;
            else if(player1+roll>100 && roll==6)
               chance=chance;
            else if(roll==6){
               player1=player1+roll;
               chance=chance;
            }
            else{
               player1=player1+roll;
               chance1=(chance1+1)%2;
            }                 
       }


    else{// Now similarly for player2
              {
             int key=roll+player2;// new position of player2             
             boolean isLadder=false;// This is for checking the turn current player if againTurn is ture 
             // then the current player will player again.
             if(hashMap.contains(Key)){
                 player2=hashMap.getValue(Key);
                 // Here player current position will automatically update according to the hashMap.
                 // if there is snake the key value is greater than it mapping value.
                 // if there is ladder then key value is less than it mapping value. 
                 if(Key<hashMap.getValue(Key))
                     isLadder=true;// Here player gets ladder.
                 if(isLadder==true && roll==6 || isLadder==true)
                   chance=chance;
                 else
                   chance=(chance+1)%2;
             }
             else if(player2+roll>100 && roll!=6)
                   chance=(chance+1)%2;
                else if(player2+roll>100 && roll==6)
                   chance=chance;
                else if(roll==6){
                   player2=player2+roll;
                   chance=chance;
                }
                else{
                   player2=player2+roll;
                   chance=(chance+1)%2;
                }                 
        }
       }
     }
  }

Answer 2

Vakh is correct. "Yes it is possible: every 2D array can be represented as a 1D array."

The array

int board[100] =
{
     0,  0,  0, 10,  0,  0,  0,  0, 22,  0,
     0,  0,  0,  0,  0,  0,-10,  0,  0, 18,
     0,  0,  0,  0,  0,  0,  0, 56,  0,  0,
     0,  0,  0,  0,  0,  0,  0,  0,  0, 19,
    17,  0,  0,-20,  0,  0,  0,  0,  0,  0,
     0,-43, 18, -4,  0,  0,  0,  0,  0,  0,
    20,  0,  0,  0,  0,  0,  0,  0,  0,  0,
     0,  0,  0,  0,  0,  0,  0,-63,  0,  0,
     0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
     0,  0,-20,  0,-20,  0,  0,  0,-21,  0
};

can hold ladders 4->14, 9->13, 20->38, 28->84, 40->59, 51->67, 63->81, 71->91 and snakes 17->7, 54->34, 62->19, 64->60, 87->24, 93->73, 95->75, 99->78

if red is at position 2 (i.e. r=2) and scores 2 (i.e. s=2) then new position of red is

    2+2+board[2+2-1] = 14

i.e.

    r = r + s + board[r+s-1])

@Jan Dvorak, "jagged arrays are not 2D array"