5
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ xnor got the answer first on this question, but I've answered a more general problem. Similarly on your last puzzle, I got the answer first but Martin answered a more general problem. To settle the debate between me and Martin, are you going to accept my answer there and xnor's here, or Martin's there and mine here? $\endgroup$ – Rand al'Thor Mar 25 '15 at 11:09
  • 4
    $\begingroup$ Spin the board around $\endgroup$ – SaturnsEye Mar 25 '15 at 12:31
17
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ For every piece that vacates a column another piece must move to occupy it. I don't think an odd number of moves is possible. I just got an alert that an answer was edited so hopefully my comment is still relevant. $\endgroup$ – LeppyR64 Mar 25 '15 at 10:30
  • $\begingroup$ @JasonLepack Indeed, I came to a similar realization about the parity. $\endgroup$ – xnor Mar 25 '15 at 10:32
  • 2
    $\begingroup$ Nice one, xnor! I proved 92 was optimal almost simultaneously, but your proof is better and more intuitive. $\endgroup$ – Rand al'Thor Mar 25 '15 at 10:42
3
$\begingroup$

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
$\endgroup$
  • 3
    $\begingroup$ @Martin This is what's called a PARTIAL SOLUTION. I've established upper and lower bounds, and will now proceed to move them closer together until I reach the answer (unless someone else gets there first). This answer does not deserve a downvote. $\endgroup$ – Rand al'Thor Mar 25 '15 at 10:03
  • 2
    $\begingroup$ @Martin What if my solution is optimal? Then by your own comment, it'd be Gamow's puzzle that deserves a downvote and not my answer. How can you be sure my solution isn't optimal? $\endgroup$ – Rand al'Thor Mar 25 '15 at 10:04
  • 2
    $\begingroup$ @Martin Ah, xnor proved 92 is optimal while I was doing my final edit. I've now also proved that 92 is optimal, but xnor got there first, so credit to xnor. I won't bleat that my answer is better than his because it's more general or whatever. BTW why did you delete your earlier comment? Do you no longer think that 'if my solution is optimal, then this does not deserve to be called a "puzzle"'? $\endgroup$ – Rand al'Thor Mar 25 '15 at 10:39
  • 1
    $\begingroup$ @Martin I've now followed your example and posted a generalised answer. Let's see whether Gamow prefers to accept the answer of the person who got there first (me and xnor respectively) or the most general answer (you and me respectively) on his two latest puzzles. $\endgroup$ – Rand al'Thor Mar 25 '15 at 11:14
  • 1
    $\begingroup$ @xnor Because swapping 2 adjacent pawn-pairs takes 26 moves. I'll edit to clarify. (Don't get me wrong - I think your answer should be accepted! Martin and I were debating this on another question where I answered first and he posted a generalised answer.) $\endgroup$ – Rand al'Thor Mar 25 '15 at 11:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.