Consider an undirected graph where each node corresponds to one possible arrangement of passengers and two nodes are linked if you can get from one node to the other by a single passenger moving one step. This graph has $8!/4!=8\cdot7\cdot6\cdot5=1680$ nodes, and we are looking for a shortest path between two specific nodes. Running a shortest path algorithm on this graph gives the following solution with the minimum number of moves:
26:
....
4321
..2.
43.1
4.2.
.3.1
.42.
.3.1
.4.2
.3.1
..42
.3.1
...2
.341
..2.
.341
.2..
.341
2...
.341
2..1
.34.
2.1.
.34.
21..
.34.
214.
.3..
21.4
.3..
2.14
.3..
2314
....
231.
...4
23.1
...4
2.31
...4
.231
...4
.2.1
..34
...1
.234
..1.
.234
.1..
.234
1...
.234
....
1234
By request, here is SAS code:
proc optmodel;
num n = 4;
set PEOPLE = 1..n;
set SLOTS = 1..2*n; /* 1..n is top row, n+1..2*n is bottom row */
/* use constraint programming solver to enumerate all (2n)!/n! assignments of people to slots */
var X {PEOPLE} >= 1 <= 2*n integer;
con Alldiff: alldiff(X);
solve with clp / findallsolns;
put (fact(2*n)/fact(n))=;
/* construct nodes from solutions */
set NODES;
NODES = 1.._NSOL_;
set <str> SOLS init {};
num slot {NODES, PEOPLE};
str solStr {NODES};
str solStrThis;
num isAssigned;
num nodeId {SOLS};
num sloti, slotj, isEdge, diff, countDiffs;
for {node in NODES} do;
solStrThis = '';
for {s in SLOTS} do;
isAssigned = 0;
for {p in PEOPLE: X[p].sol[node] = s} do;
slot[node,p] = s;
solStrThis = solStrThis||p;
isAssigned = 1;
leave;
end;
if isAssigned = 0 then solStrThis = solStrThis||'.';
end;
SOLS = SOLS union {solStrThis};
nodeId[solStrThis] = node;
solStr[node] = solStrThis;
end;
/* construct edges */
set <num,num> EDGES init {};
str solStrNext;
num nodeNext;
for {i in NODES} do;
solStrThis = solstr[i];
for {p in PEOPLE} do;
/* current slot occupied by person p */
sloti = slot[i,p];
/* person p moves up */
if sloti - n in SLOTS and substr(solStrThis,sloti-n,1) = '.' then do;
solStrNext =
(if sloti-n-1 in SLOTS then substr(solStrThis,1,sloti-n-1) else '')
||p
||substr(solStrThis,sloti-n+1,n-1)
||'.'
||(if sloti+1 in SLOTS then substr(solStrThis,sloti+1) else '');
nodeNext = nodeId[solStrNext];
if i < nodeNext then EDGES = EDGES union {<i,nodeNext>};
end;
/* person p moves down */
if sloti + n in SLOTS and substr(solStrThis,sloti+n,1) = '.' then do;
solStrNext =
(if sloti-1 in SLOTS then substr(solStrThis,1,sloti-1) else '')
||'.'
||substr(solStrThis,sloti+1,n-1)
||p
||(if sloti+n+1 in SLOTS then substr(solStrThis,sloti+n+1) else '');
nodeNext = nodeId[solStrNext];
if i < nodeNext then EDGES = EDGES union {<i,nodeNext>};
end;
/* person p moves left */
if sloti in 2..n and substr(solStrThis,sloti-1,1) = '.' then do;
solStrNext =
(if sloti-2 in SLOTS then substr(solStrThis,1,sloti-2) else '')
||p
||'.'
||(if sloti+1 in SLOTS then substr(solStrThis,sloti+1) else '');
nodeNext = nodeId[solStrNext];
if i < nodeNext then EDGES = EDGES union {<i,nodeNext>};
end;
/* person p moves right */
if sloti in 1..n-1 and substr(solStrThis,sloti+1,1) = '.' then do;
solStrNext =
(if sloti-1 in SLOTS then substr(solStrThis,1,sloti-1) else '')
||'.'
||p
||(if sloti+2 in SLOTS then substr(solStrThis,sloti+2) else '');
nodeNext = nodeId[solStrNext];
if i < nodeNext then EDGES = EDGES union {<i,nodeNext>};
end;
end;
end;
/* use network solver to find shortest path from source to sink */
num sourceArray {i in SLOTS} = (if i <= n then . else 2*n+1-i);
str sourceStr = cat(of sourceArray[*]);
num sinkArray {i in SLOTS} = (if i <= n then . else i-n);
str sinkStr = cat(of sinkArray[*]);
set SOURCE = {nodeId[sourceStr]};
set SINK = {nodeId[sinkStr]};
set <num,num,num,num,num> PATHSNODES; /* source, sink, path, order, node */
solve with network / shortpath=(source=SOURCE sink=SINK) links=(include=EDGES) out=(pathsnodes=PATHSNODES);
for {<s,t,p,o,i> in PATHSNODES} do;
put 'Move ' (o-1);
put (substr(solStr[i],1,n));
put (substr(solStr[i],n+1,n));
put;
end;
quit;
Here are shortest path lengths:
\begin{matrix}
n & \text{nodes} & \text{edges} & \text{length} \\
\hline
1 & 1 & 0 & 0 \\
2 & 12 & 12 & \text{infeasible} \\
3 & 120 & 180 & 22 \\
4 & 1680 & 3360 & 26 \\
5 & 30240 & 75600 & 30 \\
6 & 665280 & 1995840 & 42 \\
7 & 17297280 & 60540480 & 48 \\
8 & & & 62 \\
9 & & & 70 \\
\end{matrix}