5
$\begingroup$

Say there's an 8x8 board with the far ends completely occupied by pawns (White: a1 b1 c1 d1 e1 f1 g1 h1, Black: a8 b8 c8 d8 e8 f8 g8 h8). The aim of this game is to capture all but 1 pawn using the regular pawn movement rules. Pawn promotion is not allowed. So, is it possible, and if so how fast (please include move sequence used) can you achieve this 1 pawn left, and yes, each side takes turns moving.

$\endgroup$
  • $\begingroup$ I guess promotion is not an option? $\endgroup$ – Florian F Nov 2 '14 at 1:06
  • $\begingroup$ @Florian, When you think about it, no pawns should get to the point where they can promote. If they get past the other pawns, a pawn can no longer capture him, meaning you'll have 2 pieces left. $\endgroup$ – warspyking Nov 2 '14 at 1:08
  • $\begingroup$ But no, you're not allowed to have any pieces other than pawns. $\endgroup$ – warspyking Nov 2 '14 at 1:08
  • 1
    $\begingroup$ A pawn could have promoted to a queen and got back to where it can be captured. But ok. $\endgroup$ – Florian F Nov 2 '14 at 1:44
  • $\begingroup$ Can I do 2/3 of a capture? :-) $\endgroup$ – Florian F Nov 2 '14 at 2:18
11
$\begingroup$

It is not possible for any number of columns.

Consider the 4 values:
$n_{be}$ : the number of black pawns on an even column,
$n_{bo}$ : the number of black pawns on an odd column,
$n_{we}$ : the number of white pawns on an even column,
$n_{wo}$ : the number of white pawns on an odd column.

And compute the value:
$D = n_{be} - n_{bo} - n_{we} + n_{wo}$

When a black even pawn takes a white odd pawn, the black even pawn becomes odd and a white odd pawn is removed. This decreases $n_{be}$ and $n_{wo}$ by 1 and increases $n_{bo}$ by 1. The effect on D is:
$D' = (n_{be}-1) - (n_{bo}+1) - n_{we} + (n_{wo}-1)$
$D' = D - 3$

The effect on $D$ of the possible moves are:
- black even takes white odd: $D' = D - 3$,
- black odd takes white even: $D' = D + 3$,
- white even takes black odd: $D' = D + 3$,
- white odd takes black even: $D' = D - 3$,
- any non-capture leaves $D$ unchanged.

If you start with a position with black and white pawns facing each other, you have:
$n_{be} = n_{we}$ and $n_{bo} = n_{wo}$
and therefore
$D = n_{be} - n_{bo} - n_{we} + n_{wo} = 0$

Starting with $D=0$, and adding only multiples of 3, you can see that whatever you do, D will remain a multiple of 3.

An end position with a single pawn has $D=\pm1$. It is not a multiple of 3, and therefore the position cannot be reached with any combination of valid pawn moves.

$\endgroup$
  • $\begingroup$ Good job, bonus question: Is it possible if I give you and 8x10 board with 8 pieces on the ends? $\endgroup$ – warspyking Nov 2 '14 at 9:19
  • $\begingroup$ See slightly updated answer. $\endgroup$ – Florian F Nov 2 '14 at 15:40
3
$\begingroup$

It is not possible. I believe Florian's answer is sufficient to prove that it cannot work, but this should give some intuition as to why it doesn't work.

Consider the case of only two columns. Like Florian, we'll only worry about the captures that need to occur. Here are the four pawns (two of each color):

W W
B B

If white captures a black pawn:

_ W
B W

If white then captures the other black pawn we'd be stuck with two white pawns, so we'll let black capture a white pawn:

_ B
_ W

Now we've got pawns of different colors, but they're in the same column. There's no way that one can capture the other. That means a strategy of capturing pawns such that we'll clear columns either from left to right or right to left won't work because we'll end up with two pawns left.

With three columns:

W W W
B B B

If a leftmost pawn captures a piece, we get

_ W W
B W B

If the other leftmost pawn does the next capture, we're down to the two columns which we already know doesn't work. So we know a white pawn has to capture that pawn:

_ W W
W _ B

There's no way forward from here, either - the black pawn will capture the middle white pawn, but then has to choose between the two remaining pawns. Regardless of the choice, there will be a white pawn and a black pawn left with an empty column between them. So let's have the middle white pawn be the one that does the first capture:

W _ W
W B B

If middle black captures next there will be a gap, so white has to capture next. Here are the two options:

W _ _      _ _ W
W W B      W W B

We've seen the second scenario before, so we'll look at the first one. Obviously, black has to capture next:

W _ _
W B _

From here, there are only two possibilities:

_ _ _    B _ _
W W _    W _ _

Either we end up with two white pawns, or a black and a white in the same column.

Based on the results for two and three columns, let's take a look at what happens if we start with the middle of the board:

* W W *
* B B *

Here we can substitute the asterisks with either one piece of each color, or two of one color. Let's start with white capturing a black pawn:

* _ W *
* B W *

If black captures the white there will be a gap (or we're at the edge of the board), so the black pawn must be captured. Suppose the capture comes from the right:

* _ _ *
* W W *

This only lets us know that we don't have to assume we're at the edge of the board if we add two pieces of the same color. So suppose the capture comes from the left. Substituting in for the asterisks gives us these two options:

* W _ W *    * W W _ W *
* B B W *    * _ _ B W *

From there, we get:

* _ _ W *    * W _ _ W *
* B W W *    * _ _ W W *

The second option has a gap, which doesn't work. In the first one, the black pawn cannot be captured from the right. If we have black capture white, we leave an empty column, so it would need to be at the edge of the board (and we're back to the three column version). If we add to the right side:

* _ _ W W *     * _ _ W _ _ *
* B W W B *     * B W W B B *

The next step for each of these is

* _ _ B W *     * _ _ _ _ _ *
* B W W _ *     * B W W W B *

We're stuck in the second case (leaves gaps), and in the first case we get

* _ _ _ W *
* B B W _ *

This is just two groups of two pieces of a single color next to each other, so we've really got nowhere to go.

This doesn't quite fully prove its impossibility as there are some more options that I would need to show fully. Hopefully this should be enough to help give you some intuition as to why it doesn't work.

One interesting thing to note is that many of the dead-ends just have one extra piece. That suggests that if the symmetry was thrown off (start with any one pawn missing) it should be possible, at least from a capturing point of view.

$\endgroup$

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.