@polygenelubricants breadth first search (BFS) implementation works very well. When I tested it with the original 160 Rush Hour layouts I found 2 interesting things - first, Set 2 "intermediate" 1 was solved in 21 moves which is 1 better than the solution on the game card (!), second (unfortunately) it doesn't seem to handle those layouts which have a horizontal blocking car, for example Set 3 "expert" 30.

It's trivial enough to set the blocker as an intermediate goal, solve for that and then remove the blocker from the state and solve for the original goal.

Below are the 2 solutions for layout Set 2 "intermediate" 1:

Game: [D-1, P+3, B+3, Z-1, Q-3, C-3, O+1, Q+1, A+4, O-1, Q-1, C+3, Q+3, Z+1, B-4, Z-1, Q-3, D-3, C-3, O+3, Q+3, Z+6]

BFS: [B+3, Z-1, Q-3, C-3, Q+3, O+3, A+3, Z+3, Q-3, C+1, B-4, C-1, Q+3, Z-3, Q-1, O-1, D-4, P+3, Q+1, O+1, Z+4]

The game suggests D left 1 square, and later D left 3, the BFS produced one move of D left 4.