Sort 2D arrays so that cost of reaching new position as described at each iteration is minimized
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.