How do I get more Klotski in my life? I really love sliding tile puzzles, but recently, I haven't had time for them.  Hence, I need a program to give me my fix of sliding-tile puzzles, specifically Klotski puzzles.

Your input will be in the following format:

#######
#001gg#
##.222#
.######


where # represents walls, . represents an open area, g represents the goal, and adjacent numbers represent different blocks.  You can assume that:


There will be no more than 10 blocks
There won't be two blocks with the same number
All blocks will be enclosed by walls
The grid is rectangular
The 0 block is large enough to cover all of the goal squares.
There is a valid solution


You need to return a sequence of moves that will put the 0 block so that it covers all of the goal squares.  Blocks cannot pass through walls or other blocks.  For the above puzzle, an appropriate sequence would be

2L,1R,1R,1D,0R,0R,0R


while represents moving the 2 block 1 square left, the 1 block 2 squares right (on top of the goal) then 1 square down, and then 0 block 3 squares right.

There are actually several sequences that will work for the above problem, and producing any of them is acceptable.  Your solution should be optimal, meaning that it should produce a sequence that solves the puzzle in as few as steps as possible.

The sequence should be printed out as above, but can be comma, newline, or space 
separated.  I don't care if there are trailing commas or whitespace.  You should produce the output in reasonable time (maximum 120 seconds on the puzzles below).

Puzzle 1:

..####..
..#00#..
###00###
#......#
#.1122.#
##3124##
.#3344#.
.##55##.
..#gg#..
..####..


Puzzle 2:

######
#1002#
#1002#
#3445#
#3675#
#8gg9#
######


Puzzle 3:

.####.
##1g##
#22g3#
#4255#
#4.56#
#.006#
#7008#
######


Puzzle 4:

.####.
##00##
#.00g#
#.0.1#
#..g2#
######


This is code-golf, so the shortest solution (in bytes) wins!
Python, 1761
Kind of burnt out on this question, so couldn't bring myself to golf it. Either way, right now it's the only solution that solves everything within the time limit (longest, #3, takes 27 seconds).
pieces = {}
taken = set()
goals = set()

y = 0
while True:
    try:
        for x, c in enumerate(input()):
            if c == &quot;.&quot;: continue
            if c == &quot;g&quot;:
                goals.add((x, y))
            else:
                if c in &quot;0123456789&quot;:
                    if c not in pieces: pieces[c] = set()
                    pieces[c].add((x, y))
                taken.add((x, y))

        y += 1

    except: break

def translate_comp(coords):
    o = min(sorted(coords))
    return set((c[0] - o[0], c[1] - o[1]) for c in coords)

similar = {}
for piece in pieces:
    k = tuple(translate_comp(pieces[piece]))
    if k not in similar: similar[k] = []
    similar[k].append(piece)


seen = set()
states = [(pieces, taken, ())]
while states:
    state = states.pop(0)
    if not goals - state[0][&quot;0&quot;]:
        names = {
            (-1, 0): &quot;L&quot;,
            (1, 0): &quot;R&quot;,
            (0, 1): &quot;D&quot;,
            (0, -1): &quot;U&quot;,
        }

        print(len(state[2]))
        print(&quot; &quot;.join(piece + names[d] for d, piece in state[2]))
        break

    for piece in pieces:
        for d in ((-1, 0), (1, 0), (0, 1), (0, -1)):
            new_pieces = state[0].copy()
            new_pieces[piece] = {(c[0] + d[0], c[1] + d[1]) for c in state[0][piece]}
            new_taken = state[1] - state[0][piece]

            # Collision
            if new_pieces[piece] &amp; new_taken:
                continue

            gist = tuple(frozenset().union(*(new_pieces[piece] for piece in similar_set))
                         for similar_set in similar.values())

            if gist in seen:
                continue

            seen.add(gist)
            new_taken |= new_pieces[piece]
            states.append((new_pieces, new_taken, state[2] + ((d, piece),)))