Pedro's pawn game

Question

Yesterday, my good friend Pedro told me about Pedro's pawn game which is played with $7$ white and $7$ black pawns on a $7\times7$ checkerboard.

• In the starting situation, there is a white pawn on each of the seven squares in the bottom row, and a black pawn on each of the seven squares in the top row.
• In the goal situation, white and black pawns have switched positions: there is a black pawn on each square in the bottom row and a white pawn on each square in the top row.
• The only allowed pawn moves are from the current square to a horizontally or vertically adjacent empty square.

Pedro asked me: What is the smallest number of allowed moves that turn the starting situation into the goal situation?

Answer 1

I give a construction of 92 moves and prove it optimal.

As rand al'thor notes, 84 moves forward are inevitable. So, we'll only count "excess moves" that do not move a pawn forward.

Each white pawn is in a column opposed against a black pawn that blocks its way. The two cannot pass each other, so each column requires an excess move to unblock it by moving one of its pawns sideways. This gives a minimum of 7 excess moves, so an overall 91 move minimum.

Note that we can resolve two adjacent columns in two excess moves by moving out a white piece, moving the black pawn from the other column into its place, and then making the natural moves:

OO        OO       |O        XO       X|        XX 
                   |         ^        --         ^
           X       |X        |X       |X         |
           ^       --        |        |           
           |        |        |        |
           |        v        |        v
XX        X|       XO        |O       OO        OO

A single column can also be resolved with two excess moves by moving a pawn sideways, letting the other pass, and moving it back. This lets us resolve the 7 columns in 8 excess moves for a 92-move solution.

Can we cut down the solution to 91? No, by a parity argument. On a checkered board, each move changes the parity of the number of pieces on black squares. Since that parity is the same in the start and end configurations, the total number of moves must be even. So, the minimum is 92, which the solution achieves.

Answer 2

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.

A generalisation

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