Minimum steps to win Snake Ladder

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.

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.