Build an ice puzzle generator + solver In Twitch Plays Pokémon, one of the most annoying obstacles one can face is an ice puzzle, where you must travel from one place to another by sliding all the way in one direction until you either hit a wall or a boulder.

Your task is to build a program that will generate a random difficult ice puzzle.

Your program will accept three numbers, M, N, and P, as input (with 10 &lt;= M &lt;= 30, 15 &lt;= N &lt;= 40, and 0 &lt;= P &lt; 65536):

12 18


and will output:


An M by N grid consisting of . and O, representing ice and a boulder respectively.
A position marker representing where the puzzle is entered from. This position marker consists of a letter L, R, T, or B, representing left, right, top, and bottom, followed by a number representing the position (from the left or top) on that side to be entered from.
A similar position marker representing where the puzzle is exited out of. 
The shortest solution to the puzzle, consisting of a sequence of L, R, U, and D respectively.


Example output:

..O...O...........
............O.....
..O...............
.......O..........
..................
...........O......
O..O...........O..
..........O.......
..O..........O....
........O.........
O....O.........O..
............O.....
R 4
B 5
LDLDRULD
(Note that this output is actually invalid because it is not actually long enough.)


For an input M and N, the solution to the puzzle must have at least min(M, N) steps and move at least 2 (M + N) total spaces. (For reference, the above puzzle moves a total of 12 steps, moving 69 spaces.) Your puzzle generator must generate a different M by N puzzle with a different solution path (i.e. a different sequence of steps for each solution) for each seed P.


Note that the requirement of a different solution path is to avoid solutions that try to systematically generate rock paths, like Claudiu's solution here. If there are two or three pairs of identical solutions due to quirks in randomness, that will be okay, as long as the program is not intentionally trying to systematically generate puzzles with the same sequence of moves.


The shortest code to do the above wins.
Python, 672 548 characters, more interesting puzzles

Although going strictly by the rules, my other Python program beats this one, I decided to write one that would generate more interesting puzzles anyway. Here it is:

R=range;import random as J;X=J.randint
x=(0,1,-1,0);y=x[2:]+x
g=lambda r,c:(0&lt;=r&lt;H)+(0&lt;=c&lt;W)&gt;1and f[r][c]or x[(r,c)in(A,E)]
l=lambda r,c:g(r+y[d],c+x[d])&lt;1and(r,c)or l(r+y[d],c+x[d])
H,W,P=input();J.seed(P)
while 1:
 A=(-1,X(0,W));E=(H,X(0,W));f=[[X(0,7)for _ in R(W)]for _ in R(H)]
 q=[(A,'')];n=z={}
 while q and n!=E:
    n,O=q.pop()
    for d in R(4):
     N=l(*n)
     if g(n[0]+y[d],n[1]+x[d])and N not in z:q[:0]=[(N,O+"URLD"[d])];z[N]=1
 if(n==E)*len(O)&gt;min(H,W):print"\n".join(''.join('O.'[c&gt;0]for c in T)for T in f),"\nT",A[1],"\nB",E[1],"\n",O;break


Indentation levels are space, tab, tab+space.

Samples:

$ echo [10,15,0] | python ice2.py
.....OO........
...............
...O....O.OO..O
...........O...
..O....O.......
.......O....O..
....O..........
.............O.
..............O
...............
T 1
B 10
DLURDRURULDRD


It uses P as a seed, so each P will generate the same puzzle, and each different P is exceedingly likely to be different:

$ echo [10,15,1] | python ice2.py
.OOO.O.........
...O......O.O.O
.......O.......
..O..........OO
.....O.........
.............O.
.O.............
.O............O
O....O.........
......O........
T 14
B 8
DLDRDLURULD


It works reasonably fast up to sizes of M=25,N=40 but past that it gets really slow. It should theoretically work for M=30, N=40 if you let it run long enough. I've manually written in the trail here since it is hard to follow - the program just outputs the puzzle.

$ echo [25,40,0] | python ice2.py
                   *
...................dO....urrrO..O..O....
....O.....O........dO....u..dO..........
..........O.....O..d....Ou.Odrrrrrrrrrrr
...........O.......d.O..Ou..O.....OOllld
.O....O.OO.........drrrrrrO....Olllud..O
O......O...O.O.....O............dO.ud...
O........OO..........O.........Od..ud..O
.........O......................d..ud...
....O.....O.O....O.....O........d..ud.O.
.....O..O...................O...d..udO..
.........O.........O..O.........d..ud...
.......O.O...O..O.OO....O...OOlldOOld...
........Olllllllllu....OO.OO..dOO...O...
.O.O....Od........u......O....d..O...O..
..O....O.d........u..O........d..O..O...
....O....d..O.....uO.....O....d.........
.........d........u...........d.........
.........d....O...u.O..O.....Od.O.......
........Od...O....u...........d.........
.O.....OuxrrrrO...u...OOOO..O.d.........
........udO..dO.O.u...........d.........
O..O.O..ud...d..urrO..........d.O...O...
........ud...d..u.O.O........Od..O...O..
..OO....ud..Od..u......OllllludO.....O..
..O....OldO..dOOlllllllld...Old...O..O..
             *
T 19
B 13
DRURDRDLDLULDLDLULDLURULDLURD


Explanation:

The program loops, generating a random start position on the top, a random end position on the bottom, and a random grid with a 12.5% chance for a boulder on any given spot. It then solves the puzzle with a breadth-first-search and if the solution exists and is bigger than min(H,W), it prints and exits.