Minimum steps to win Snake Ladder

Question

Given a snake and ladder game, write a function that returns the minimum number of jumps to take top or destination position. You can assume the die you throws results in always favor of you

**

Here is my solution, but not sure it's correct or not.

This problem is similar to frog jump in an array.But before that we will have to model the problem in that format.

Create an array of size 100 and for each position store 6 if there is no snake or ladder. store jump count . if ladder is present at that point . If snake is present then store -ve jump at that location.

Now we have to solve in how many minimum steps we can reach till end. Main problem can be solved using dynamic programing in O(n^2) time complexity and O(n ) space.

Answer 1

Have a look at this blog post, it does a full mathematical analysis of Chutes and Ladders, using both Monte-Carlo simulations and Markov chains. He does show a way of calculating the minimum number of steps to win (basically construct a transition matrix and see how many times you have to multiply the starting vector to get to a solution that has a non-zero final position). This is probably not the most efficient way of doing it, but the post is well worth the read.

Here is a quick solution in python, using sets. I got the numbers in the jump-table from the blog post. At every step, it simply calculates all the positions reachable from the previous step, and continues to do so until the final position is among the reachable positions:

jumps = {1: 38, 4: 14, 9: 31, 21: 42, 28: 84, 36: 44, 51: 67, 71: 91, 80: 100,
  98: 78, 95: 75, 93: 73, 87: 24, 64: 60, 62: 19, 56: 53, 49: 11, 48: 26, 16: 6}
final_pos = 100
positions = {0} #initial position off the board
nsteps = 0

while final_pos not in positions:
    nsteps += 1
    old_positions = positions
    positions = set()
    for pos in old_positions:
        for dice in range(1, 7):
            new_pos = pos + dice
            positions.add(jumps.get(new_pos, new_pos))

print 'Reached finish in %i steps' % nsteps            

Execution time is negligible and it spits out the correct answer (see blog) of 7.

Answer 2

Here's a simple breadth-first search solution in Python:

# the target square and the positions of the snakes and ladders:
top = 100
jump = { 1: 38,  4: 14,  9: 31, 16:  6, 21: 42, 28: 84, 36: 44,
        48: 26, 49: 11, 51: 67, 56: 53, 62: 19, 64: 60, 71: 91,
        80:100, 87: 24, 93: 73, 95: 75, 98: 78}

# start from square 0 (= outside the board) after 0 rolls
open = {0}
path = {0: ()}

while len(open) > 0:
    i = open.pop()
    p = path[i] + (i,)
    for j in xrange(i+1, i+7):
        if j > top: break
        if j in jump: j = jump[j]
        if j not in path or len(path[j]) > len(p):
            open.add(j)
            path[j] = p

for i in path:
    print "Square", i, "can be reached in", len(path[i]), "rolls via", path[i]

The board layout (i.e. the jump dictionary) is taken from the blog post linked to by Bas Swinckels in his answer. This code will print (one of the) shortest path(s) to each reachable square on the board, ending with:

Square 100 can be reached in 7 rolls via (0, 38, 41, 45, 67, 68, 74)

If you want the full output, see this demo on ideone.com.