Demonstrate how to find a solution to a given Sokoban level. For the purpose of this task (formally, a PSPACE-complete problem) any method may be used. However a move-optimal or push-optimal (or any other -optimal) solutions is preferred.

Sokoban levels are usually stored as a character array where

 space is an empty square
 # is a wall
 @ is the player
 $ is a box
 . is a goal
 + is the player on a goal
 * is a box on a goal
#######
#     #
#     #
#. #  #
#. $$ #
#.$$  #
#.#  @#
#######
Sokoban solutions are usually stored in the LURD format, where lowercase l, u, r and d represent a move in that (left, up, right, down) direction and capital LURD represents a push.

Please state if you use some other format for either the input or output, and why.

For more information, see the Sokoban wiki.



 
589*+0g"0"-25**689*+0g"0"-+50p     v # Sokoban - (c) Matthew Westcott 2000 # 03
83*>10p99*2->:00p10gg"x"-#v_v p01g<> ## # # # # # # # # # # # # # # # # # # #
<< ^  -1g01_^#!:     -1g00< > v      # # # # # # # # # # # # # # # # # # # # #
|-"8"_v#-"2":_v#-"6":_v#-"4":~<  <0 #
> 1  0>$1+2  0>$2+3%\0>$1+3%40v  $4<#
v -"0"gp04:-1+g<v:-1+g00p03:p <  $p #
>#v_"X">30g40gv0>40g10g+1-g:"#"-!|0 #
 0>"x" ^v1g00p<^1g04p03:_v#`\ "9"<0 #
v:g-2++<>0gg"X"-#v_"0">00 g10gp30g^ #
4#     ^g04g04g0<>" " ^v3<          #
>8*-#v_$"o"   v ^1-1+g0< >00g30g30v #
 #   >"0"-#v_v>          ^v01-2++g< #
 ^>#$" " 0#<v>"@"50g1-50p^>g40g40gv #
v_^#!-"@"g-1+g04g01:-1+g03g00p-2++< #
>"0"50g1+50p>\10g40g+1-p30g02050g  |#
>,#-:#3_@#"a\rx#glg#lw$Zhoo#Grqh$"0<#
#####################################
                                                                       ########
                                                                       #      #
                                                                       # o@0o #
                                                                        #    #
                                                                         # o#
                                                                       ###  ###
                                                                       #0  x 0#
                                                                       ########
 