Sliding retrieval

Question

Thanks, Uncle (the story)

My slightly mad uncle recently left for the space colonies, and passed his pallet goods business to me. The rectangular warehouse is full of pallets of goods except for the one square by the door, and I've just received the first list of pallets ordered by customers to be sent out today.

Fortunately I have a carefully written map of where each pallet is, and my mad uncle engineered several mini robots which can move a pallet into an adjacent space, much like a sliding 15-puzzle. I don't care where the pallets end up, though, I just want the pallets on the list to arrive in order by the door.

The question is, what series of commands must I give the robots in order to retrieve the required pallets?

The challenge

Given

• the size of the grid (rows, cols)
• a list of pallets (by their current location) to retrieve in order

You must output a list of grid positions corresponding to which position is to be moved, and which direction. If there is only 1 direction available you may optionally omit that. The pallets will be removed immediately upon arrival by the door (at one corner, index N in the examples).

Worked example

01 02   label the contents  A B
03 04                       C D
05[  ]                      E _

Request: 03 (contents is C)

Command 0: 04
D moves into the (only) adjacent space at index 06
Result: A B
        C _
        E D

Command 1: 03
C moves into the (only) adjacent space at index 04
Result: A B
        _ C
        E D

Command 2: 05
        A B
        E C
        _ D
Command 3: 06  
        A B
        E C
        D _
Command 4: 04
        A B
        E _
        D[C]
(C removed having arrived by the door)

Limits and freedoms

• Maximum grid size is 100x100
• Challenge is code-golf
• Solution must execute within 2 minutes on some real-world machine
• You can choose your indexing, command syntax, input structures and so on, as long as it's consistent.
• I've chosen to use the grid locations for the commands, but conceivably you could emit the value in the element instead (plus a direction) as they are unique.
• If you wanted to make an animation of the state (especially for a large grid), I'm sure that would be entertaining!

Examples

A: 3x2, 1 pallet

01  02
03  04
05 [__]

Request: pallet at 03

Valid solution: 05,03,04,06,05

This leaves the following state:

01  02
04  05
__ [03]

B: 15-puzzle, 1 box

01 02 03 04 05
06 07 08 09 10
11 12 13 14[  ]

Request: box 01

Valid solution: 14,13,12,11,06,01,02,07,12,11,06,07,12,11,06,07,08,13,12,11,06,07,08,09,14,13,08,09,10,15,14

02 07 03 04 05
08 12 13 10 14
06 11 09 __[01]

C: 3x2, 4 boxes

01 02
03 04
05[  ]

Request: 02,04,01,05

Valid solution: 04,02,01,03,05,06,04,05,02,06,03S,05E
Pallet taken at:                    ^  ^     ^       ^

Indicating directions with NSEW

Final state:

03 __
__ __
__ __

D: 10x10, 2 boxes

10x10, request boxes at 13,12 (row 1, cols 2 & 1 with 0-index)

Valid solution: (90,80..20, 19,18..12, 22,32..92, 93,94..100) x 15, 90.

E: 4x1, all

4x1: 01 02 03 [ ]
Req: 03,02,01 (only valid order)
Optimal solution: 03,02,03E,01,02E,03E

F: 100x100, 3 near the door

100x100
Req: 9900,9899,9898
Result: 9000,9989,9000S,9898,9898E,9000S

Sandbox link

Answer 1

JavaScript (Node.js) - 425 424 420 395

(n,m,L)=>(s=Math.sign,G=[...Array(n*m).keys()],i=k=n*m-1,G[k]=-1,R=[],M=j=>{-G[j]-1&&R.push([j,i]);[G[i],G[j]]=[G[j],G[i]];i=j},X=j=>{while(i%n-j%n)M(i+s(j%n-i%n))},Y=j=>{while(y(i)-y(j))M(i+n*s(y(j)-y(i)))},y=i=>(i-i%n)/n,L.map(e=>{J=()=>j=G.indexOf(e);while(J()%n-n+1){m>1&&y(j)-y(i)||M(y(i)?i-n:i+n);X(j+1);Y(j);M(j);m<2?i=k:0}while(J()+1-n*m){X(n-2);Y(j+n);X(n-1);M(j);n<2?i=k:0}G[k]=-1}),R)

Try it online!

Takes n,m and an array of pallets, returns a list of commands where each command is a 2-element array of the location of the pallet to move and the location of the space to move it to.

There's probably a better strategy than what I used, but posting as is for now.