Solution to the question as stated
It can be done in 92 moves. Here's how (using standard chessboard notation, rows numbered from a to g and columns from 1 to 7):
- move the white pawn on a1 to a5 (4 moves)
- move the white pawn on b1 to b3 (2 moves)
- move the black pawn on b7 to b4, then a4, then a1 (3+1+3=7 moves)
- move the white pawn on b3 to b7 (4 moves)
- move the black pawn on a7 to a6, then b6, then b1 (1+1+5=7 moves)
- move the white pawn on a5 to a7 (2 moves)
In 4+2+7+4+7+2=26 moves we've switched the pawns on a1 and b1 with those on a7 and b7. Do the same with the pawns on g1 and h1, g7 and h7. For the final three columns, proceed as follows:
- move the white pawns on c1, d1, e1 to c3, d5, e3 (2+4+2=8 moves)
- move the black pawn on c7 to c4, then d4, then d1 (3+1+3=7 moves)
- move the white pawn on c3 to c7 (4 moves)
- move the black pawn on d7 to d6, then c6, then c1 (1+1+5=7 moves)
- move the white pawn on d5 to d7 (2 moves)
- move the black pawn on e7 to e4, then d4, then d2, then e2, then e1 (3+1+2+1+1=8 moves)
- move the white pawn on e3 to e7 (4 moves)
All this gives a total of 2*26+(8+7+4+7+2+8+4)=52+40=92 moves.
As xnor states
, it can't
be done in less than 91 moves, because each pair of pawns need to 'pass' each other, necessitating an extra move to the side for one of them. In fact it can't be done in exactly 91 moves either, because not all of these shifts to the side can be done in the same direction (the board being finite) and where two shifts in opposite directions 'meet', two pawns would end up in the same square, so one of them needs to shift again
(since 7 is odd).
So the final answer is 92
Let's replace 7 pawns of each colour on a 7x7 board with $n$ pawns of each colour on an $n\times n$ board! What's the answer then?
The method I've used above for swapping a1 and b1 with a7 and b7 can be used for all pairs of columns, giving $4(n-1)+2=4n-2$ moves for each pair of columns (e.g. $4*7+2=26$ when $n=7$). The method for swapping c1, d1, e1 with c7, d7, e7 works for any triple, giving $6(n-1)+3+1=6n-2$ moves for a triple (e.g. $6*7-2=40$ when $n=7$). So the whole operation can be done in $k*(4n-2)=n(2n-1)$ moves if $n=2k$ is even, and $(k-1)(4n-2)+(6n-2)=n(2n-1)+1$ moves if $n=2k+1$ is odd.
The argument used by xnor to prove 91 is a lower bound when $n=7$ also shows that $n(2n-1)$ is a lower bound for all $n$. When $n$ is odd, xnor's parity argument shows that since the total number of moves must be even, $n(2n-1)+1$ is a lower bound.
So the optimal number of moves required to swap $n$ white pawns with $n$ black pawns on an $n\times n$ board is:
- $n(2n-1)$ if n is even
- $n(2n-1)+1$ if n is odd