Sort 2D arrays so that cost of reaching new position as described at each iteration is minimized Problem is as following:

We are 8 trumpet players in an orchestra.

There are for example 4 parts so there are always two players on the same part.

Now, there are not always the same two players playing the same part meaning the combination of players that play the same part change from piece to piece.

What is the cheapest way in terms of distance and/or the least amount of switches resulting that the players playing the same parts can sit next to each other on every piece?


Trumpet Players:
 a,b,c,d,e,f,g,h

Parts: 1,2,3,4

Seats are arranged like that: 


1st piece
| a1 | b1 | c2 | d2 |

| e3 | f3 | g4 | h4 |

Next piece the players might play the following parts:
| a2 | b1 | c3 | d1 |

| e3 | f4 | g2 | h4 |

and the next one againt different distribution of the parts:
| a4 | b3 | c1 | d3 |

| e2 | f4 | g2 | h1 |


how do we seat the players so that the least amount has to be traveled in order to reach the desired positions for the players playing the same parts to sit next to each other in the next piece?

additional notes:
i dont care where the pairs are starting and if a1 sits left of b1 or the other way around.
I would suggest using the A* algorithm.  The state is where each player is currently seating and the number of pieces you've played so far.  Each edge represents a way that you can update the seating.  Also, when you're in a state where, for the next piece to be played, everyone is sitting next to their partner on that piece, you can increment the number of pieces played at 0 cost.   The start state has 0 pieces played, and the goal state is any state where you've played all the pieces.   Then, A* will find the lowest-cost sequence of movements to complete the concern.

You'll need an admissible heuristic to estimate the cost to finish the concert, starting from a particular intermediate state.   One very simple heuristic is: count the number of players who will have some future piece to play, where they're not currently sitting next to their partner on that piece, and divide by two.  Perhaps a slightly better heuristic is to count, for each player, the number of future partners (for any piece not yet played) who they are not currently sitting next to, and divide by four.  Assuming each switch costs one and there is no other way to update the seating, this is admissible, as each switch can only decrease this count by at most four.