The recent godzillagolf titled Rush Hour was the first golf in a while where my solution contained anything worth explaining. Here's all 157 characters of the solution:

#!perl -n0
sub
R{$b<0?reverse:$_}sub
M{/
/?s^\pL^$b=$#A**pos;push@_,"$& $b
";$c=8*($<
Z);s/$&/ /,s/(($&)\C{$c}) /$1$2/<++${$_=R}or&M
for~~R;pop^ge:exit
print@_}M

The code uses a depth-first search, which can be roughly divided into the following steps (the actual code doesn't do things quite in this order):

  1. If current board has already been visited, backtrack to step 4.
  2. Mark current board as visited
  3. If a car is in the target space, print the moves that have been accumulated and quit.
  4. Move one of the cars one step in either direction
    • If no cars can be moved, backtrack
    • If backtracking to here, try another car/direction
  5. Go to step 1.

There are several subproblems that need to be solved to implement the algorithm:

  1. Detect whether the win condition has been reached.
  2. Accumulate the moves. (Preferably without using too much memory; I have a 149 character solution that uses 200MB, which isn't really justifyable for this problem).
  3. Iterate over all valid moves (car/direction pairs) for a board.
  4. Given a board and a move, generate another board.
  5. Ensure that the backtracking works.
  6. Detect whether the board has already been visited

The board is of course stored in the original format as a string. There's no room for any fancy datastructures... Given that, here are my solutions to the subproblems:

  1. Just check whether the board contains a space followed by a newline:
    / \n/ ? ... : ...  # If the regexp fails, win)
  2. Keep the moves stored as strings in @_ in the correct order:
    push@_,"$& $b\n"; # $& is the current car, $b is either -1 or 1
...   # execute the rest of the algorithm. This quits on success...
pop;  # ... so reaching this line means that we're backtracking,
      # and need to remove the move
  3. Given a board, iterate over all valid car-characters in the string (I used \pL here instead of the obvious \w for reasons that are still unclear to me). For each character, generate a value $b as either 1 or -1, so that it's guaranteed that for any board both values are generated at least once for each car. Since each line is 9 characters long and there are at least 2 characters in each car, each car must have at least one character in an even and one in an odd position in the string. Hence (-1)**pos generates a proper value.
    s^\pL^$b=$#A**pos; ... ^ge
    $#A is just a shorter way of writing (-1). Unfortunately the operator precedence of unary - is smaller than that of **.
  4. First let's solve the problem only for positive values of $b (i.e. down or up).
    $c=8*($< Z);  # $c = 8 if car moves up/down, 0 otherwise
s/$&/ /;        # Remove the first character of the car
s/(($&)\C{$c}) /$1$2/
# Find last character of car that's followed by a space exactly $c
# characters from it, and substitute the space with the character.
# For example "bbcc." => "bb.cc". If this substitution fails,
# the move was impossible and we should backtrack.
    To handle negative values of $b, just conditionally reverse $_ before and after it's modified (nobody else did this in the golf, which I found suprising):
    5. sub R{$b<0?reverse:$_}
$_=R;...;$_=R
  5. The backtracking can be implemented just by wrapping the code inside a recursive subroutine and restoring the original state if the recursive call returns. There are three interesting bits of state:
    • $_. Saved by binding $_ again with for:
      ... for"$_"  # Can't use ... for$_, since that just
               # aliases the current $_ to the new $_
      Since $_ needs to be conditionally reversed in d, we can just use the return value of R instead.
      ... for~~R   # ~~ needed to give scalar context to the reverse
    • The moves that haven't been tried for this board yet. Since these are generated from the substitution in subsolution 3, nothing special needs to be done.
    • The accumulated moves. This was handled correctly in subsolution 2
  6. Mark board visited by incrementing a symbolic reference using $_.
    ++$$_
    Since $_ needs to be conditionally reversed again, the symbolic reference can be made on the value of the assignment instead:
    ++${$_=R}
    The other part of this subproblem is to not recurse if the board has already been visited. This can be done by comparing the return value of the increment to the final substitution in subsolution 4:
    s/...//<++${$_=R}or...

Mash these ingredients together, and add an exit print@_ to actually do something with the result, and you get the solution shown above.