Snake and Ladder Problem

Given a snake and ladder board, find the minimum number of dice throws required to reach the destination. And suppose you have control over outcome of dice throw.

If you gets ladder you will climb up, but in case of snake you will be moved down.

Algorithm

1. Create a visited boolean array to hold visited vertices info
2. Create an Class name Entry to hold following attributes’ value:
   1. vertex
   2. moves
3. Create a queue which will hold above above
4. Create an object of Entry with value vertex=0 and moves=0
5. Iterate till queue is not empty
   1. entry = queue.dequeue
   2. If entry.vertex == goalVertex then
      1. return entry.moves
   3. Iterate from entry.vertex +1 to entry.vertex+ 6
      1. if vertex is not visited then
      2. Create and new entry with vertex=vertex and moves=entry.moves+1
      3. queue.enqueue(entry)

Video

Latest Source Code:
Github: SnakeLadder.java

Output:

 Number move required : 3