Moving around a plane

Question

A small plane went through some heavy turbulence and all its passengers ended up in the wrong seat. Now they need to get back to their assigned seats. The image below shows the map of the plane. The circles are the passengers and the numbers indicate their assigned seat number. For example the left-most passenger needs to get to the right-most seat.

Passengers can move into a neighbouring location provided that it is empty (not another passenger). They can move into, along and out of the corridor, but they cannot jump over seats. Each turn one passenger makes a single move. What is the fewest number of turns needed to get each passenger into their assigned seat?

Answer 1

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}

Answer 2

Here is my first attempt, done by hand. This is probably not optimal.

   0     ....
         4321

   3     2...
         43.1

   6     2...
         431.

   10    2...
         4.13

   12    ....
         4213

   16    ...4
         .213

   20    ...4
         12.3

   22    .4..
         12.3

   25    .4..
         123.

   28    ....
         1234

EDIT:
I ran it through my computer, and it found an optimal solution with

26 moves.

It is essentially the same as RobPratt's solution.

Answer 3

A scheme which I believe might be optimal in the general case

^{...but I cannot prove it.}

Assume there are $N\ge 4$ passengers (less may be considered special cases).

 x   x   ...  x   x
 N   M   ...  2   1

(Labelling $N-1$ as $M$ for convenience)

Passengers $1$ and $N$ must swap seats, but cannot move out of each other's way so we will do this while $2$ and $M$ also swap seats, leaving any other passengers where they are:

• Passenger $2$ moves up and right letting $N$ take that (incorrect) seat.
• Passenger $M$ moves up and left letting $2$ take their seat.
• Passenger $1$ moves up and $2$ left letting $N$ take their seat.
• Passenger $1$ moves $2$ right letting $M$ take their seat.
• Passenger $1$ takes their seat.

This has costs ($\text{Passenger}: \text{moves}$): $$1:N+5$$ $$2:N+1$$ $$M:N+1$$ $$N:N+3$$

The rest of the passengers then proceed to swap seats in pairs of low and high passenger numbers $L$ and $H$, like so:

• Passenger $L$ moves up and right
• Passenger $H$ takes their seat
• Passenger $L$ takes their seat

This has costs ($\text{Passenger}: \text{moves}$): $$L: N-(2L-3)+2$$ $$H: N-(2L-3)$$

Note that when $N$ is odd one passenger does not move at all.

So the total cost for $N\ge4$ passengers is:

$$N(N-(N\mod 2))+10-\sum_{L=3}^{\lfloor\frac{N}{2}\rfloor}(4L-8)$$

This gives the same results as the searches in other answers:

$$4:26$$ $$5:30$$ $$6:42$$ $$7:48$$ $$8:62$$ $$9:70$$ $$10:86$$

---

Here is some Python code that runs the scheme outlined above outputting the state at the start and after each passenger moves, along with the moves taken up to that point.

Answer 4

Since it appears that some people are interested in the code, here is a golang sample for this problem. Playground. Credit to RobPratt for describing the solution.

// https://puzzling.stackexchange.com/q/116014/12376
// This is programmed for ease of understaning not for efficiency
package main

import (
    "fmt"
    "github.com/marselester/alg/digraph/spt"
    "github.com/marselester/alg/digraph/weighted"
)

// Total number of nodes in the arrangements graph
const nodesTotal = 8 * 7 * 6 * 5

// There are many ways to model an arrangement
// We will go with an array of corridor spots and an array of seats
type arrangement struct {
    corridor [4]int
    seats    [4]int
}

// This helper function prints out a single "lane" for output:
// either the corridor lane or seats late
func printLane(lane [4]int) {
    for _, i := range lane {
        if i == 0 {
            fmt.Print(".")
        } else {
            fmt.Print(i)
        }
    }
    fmt.Println()
}

// We will need to output our steps in the result
// this will print out an arrangment
func (p arrangement) print() {
    printLane(p.corridor)
    printLane(p.seats)
}

// Place a single passenger on their designated spot:
// seats are numbered from 0 to 3 left to right,
// and corridor spots are numbered 4 to 7 (place parameter)
// Passengers are 1 to 4
func (p *arrangement) placeOne(passenger int, place int) {
    if place > 3 {
        p.corridor[place-4] = passenger
    } else {
        p.seats[place] = passenger
    }
}

// Given 4 placements for each passenger from 1 to 4
// place them in an arrangement
func (p *arrangement) placeAll(place1 int, place2 int, place3 int, place4 int) {
    p.placeOne(1, place1)
    p.placeOne(2, place2)
    p.placeOne(3, place3)
    p.placeOne(4, place4)
}

// Each passenger can potentially move in four directions
// if they are in a corridor they can move left and right
// and also "down" to a seat
// If they are in a seat they can potentially move up to the corridor
// The next four functions assume that the target space exists
// and is vacant and move the passenger
func (p arrangement) moveLeft(passenger int, place int) (result arrangement) {
    result = p
    result.corridor[place] = 0
    result.corridor[place-1] = passenger
    return
}

func (p arrangement) moveRight(passenger int, place int) (result arrangement) {
    result = p
    result.corridor[place] = 0
    result.corridor[place+1] = passenger
    return
}

func (p arrangement) moveDown(passenger int, place int) (result arrangement) {
    result = p
    result.corridor[place] = 0
    result.seats[place] = passenger
    return
}

func (p arrangement) moveUp(passenger int, place int) (result arrangement) {
    result = p
    result.seats[place] = 0
    result.corridor[place] = passenger
    return
}

// This is used to build the graph, it gets us
// all possible moves from a given arrangement
func (p arrangement) getNeigbours() (result []int) {
    for i, a := range p.corridor {
        if a != 0 { // if corridor space occupied
            if i > 0 && p.corridor[i-1] == 0 { // if vacant on the left
                result = append(result, lookup[p.moveLeft(a, i)])
            }
            if i < len(p.corridor)-1 && p.corridor[i+1] == 0 { // if vacant on the right
                result = append(result, lookup[p.moveRight(a, i)])
            }
            if p.seats[i] == 0 { // if vacant seat "down"
                result = append(result, lookup[p.moveDown(a, i)])
            }
        }
    }
    for i, a := range p.seats {
        if a != 0 { // if seat occupied
            if p.corridor[i] == 0 { // if vacant corridor space "up"
                result = append(result, lookup[p.moveUp(a, i)])
            }
        }
    }
    return
}

// Map each arrangement to an index 0..nodesTotal-1
// the index is required by the path search data structure
var lookup = map[arrangement]int{}

// And map back from index to arrangement
var arrangements [nodesTotal]*arrangement

func main() {
    index := 0
    for a := 0; a < 8; a++ {
        for b := 0; b < 8; b++ {
            for c := 0; c < 8; c++ {
                for d := 0; d < 8; d++ {
                    // One place cannot be occupied by two people
                    // so if this is the case, bail out
                    if a == b || a == c || a == d || b == c || b == d || c == d {
                        continue
                    }
                    // Create a new arrangement for the current loop iteration
                    p := arrangement{}
                    p.placeAll(a, b, c, d)
                    // Fill in both mapping from arrangement to index and back
                    arrangements[index] = &p
                    lookup[p] = index
                    index++
                }
            }
        }
    }

    // Create graph with all the nodes and edges
    graph := weighted.NewAdjacencyList(nodesTotal)
    for p, i := range lookup {
        for _, e := range p.getNeigbours() {
            graph.Add(&weighted.Edge{i, e, 1})
        }
    }

    // Get the start arrangememnt
    start := arrangement{}
    start.placeAll(0, 1, 2, 3)

    // Get the finish arrangememnt
    finish := arrangement{}
    finish.placeAll(3, 2, 1, 0)

    start.print()

    // Find a shortest path
    d := spt.NewDijkstra(graph, lookup[start])
    path := d.PathTo(lookup[finish])

    // Print resutls
    for i, p := range path {
        fmt.Printf("Step %d\n", i+1)
        arrangements[p.W].print()
    }
}

Output:

....
1234
Step 1
1...
.234
Step 2
.1..
.234
Step 3
..1.
.234
Step 4
...1
.234
Step 5
..31
.2.4
Step 6
.231
...4
Step 7
2.31
...4
Step 8
23.1
...4
Step 9
231.
...4
Step 10
2.1.
.3.4
Step 11
21..
.3.4
Step 12
21.4
.3..
Step 13
214.
.3..
Step 14
21..
.34.
Step 15
2.1.
.34.
Step 16
2..1
.34.
Step 17
.2.1
.34.
Step 18
..21
.34.
Step 19
..2.
.341
Step 20
...2
.341
Step 21
..42
.3.1
Step 22
.4.2
.3.1
Step 23
.42.
.3.1
Step 24
4.2.
.3.1
Step 25
4...
.321
Step 26
....
4321