Pawns, puzzles, and proofs

Dimitrios Roxanas tells us why playing chess backwards is the new black (and white).

post

I am sure you will agree that problem solving is an integral part of learning and creating new mathematics, but for many mathematicians recreational problem solving is also a favourite pastime. I am no exception to this; I have a fondness for riddles and brainteasers, an interest which later expanded to include chess problem solving. The amount one could write about chess problems could fill a book (in fact, many books have been written on the topic!). For today though, I want to introduce you to the world of one particular type of chess problem, namely retrograde problems. I am going to start by letting you in on a secret: retrograde chess problems are essentially logic puzzles set on a chessboard. And what’s more, they can be approached in the same way as typical maths problems and puzzles. Now I’ve really got your attention, haven’t I?

Back to square one

In retrograde problems one is typically given a chess position, possibly with some additional rules imposed by the composer. What do I mean by rules? They could tell you, for example, that the white king has not moved more than twice, or that pieces only moved to squares of the same colour they started. The composer then asks a question, like, what was Black’s last move? The answer needs to be inferred from the position, the additional stipulations, if any, and the rules of the game of chess. In other words, every position has to be legal, which means that it was reached by a sequence of legal moves. We have to accept the conditions imposed in the same way that we accept mathematical axioms.

The term retrograde is quite appropriate because to find the answer to the posed question, you always have to investigate the history of the position. That is to say, you must determine which moves were played to reach the given position, even if the question does not explicitly ask you to. I want to emphasise that there should be no guessing in deducing the solutions; they will follow logically and deterministically from the position and the stipulation(s), and without violating the rules of the game. It is therefore no surprise that retrograde analysis is truly mathematical or that one of the champions of the genre was logician Raymond Smullyan (whose retrograde puzzles and books served as my own introduction to retrograde analysis).

Three maths problems in a trenchcoat!

In the puzzles that follow, we will see examples of retrograde chess problems, and what’s more, we will approach them as typical mathematical problems. From the positions and the axioms, we will make observations, observe patterns, make claims, formulate conjectures, and prove true statements the same way you would prove a lemma or a theorem. This approach to solving retrograde problems shares a lot in common with the daily work of a researcher in mathematics! Of course, this article is merely an introduction to this exciting area, and there are many interesting ways to see true mathematical thinking. But still, even in this short introduction we will be able to use problem solving approaches, such as exploiting invariants, and use counting and contradiction.

I will assume that you are familiar with how chess pieces move, and that you understand the basic rules of the game. Don’t be discouraged if you are not a ‘strong’ chess player: to solve retrograde problems one does not need to know chess well enough to win a game—the only thing that matters is the legality of the moves up to the current position.

Notation: written in black and white

Before we move to the problems, a quick word about notation. In chess, there is a standardised way of recording the moves that take place on the chessboard. This is called algebraic notation. The name may sound scary but it’s quite simple really: the chessboard is an $8 \times 8$ grid, so, very much like a matrix, each square can be uniquely identified by two coordinates. The $x$-coordinate takes values from the letter a to the letter h (from left to right), and the $y$-coordinate ranges from 1 to 8 (from bottom to top). White’s 16 pieces are originally arranged in rows 1 and 2 (called the 1st and 2nd rank), while Black’s occupy rows 7 and 8 (called the 7th and 8th rank). For example, below, the white queen is resting on c3 and the black king on b6.

The naming convention for the pieces is:

♔ king K, ♕ queen Q, ♗ bishop B, ♖ rook R, ♘ knight N,

and ♙ pawns are simply denoted by their position (no letter). To avoid explaining every time whether a piece is white or black, the first move recorded is always White’s and the next one is Black’s.

We don’t record the square from which the piece moved unless there is ambiguity. For example, the next move recorded in this game is

1… Rg$\times$e8$+$

We must specify that it is the rook on g8 that moves to e8, and not the one on a8 which was also an admissible move. The $+$ symbol denotes that the white king is placed in check with this move, and the ellipsis (…) is used to say that we didn’t care about White’s previous move and the first move of interest was Black’s. Finally the $\times$ symbol signifies that the rook captures the white piece currently residing at e8.

Hardworking pawns deserve a promotion

Problem 1: Has there been a promotion?

Now that we know how to read a recorded sequence of chess moves, we are ready to discuss and enjoy retrograde problems! To make the most of these problems, I recommend that you cover the explanations and solutions and first try to solve each problem on your own.

Our first problem asks that you look at the position on the right, and determine whether a promotion has taken place.

For those not already familiar with the promotion rule, it states that when a pawn reaches the 8th rank, it is replaced by the player’s choice of piece, called a promoted piece. You can’t promote to a pawn or a king (and it has to be a piece of your own colour), but other than that, anything goes!

What’s immediately striking in this problem is the rather awkward placement of the white Bh8. The white bishop has somehow managed to trap itself behind the black g7 pawn. Notice that the g7 pawn has never moved, which makes the position of the bishop a real conundrum. Shouldn’t the bishop pass through g7 to get to h8?

Well, there is another possibility here, the bishop on h8 must be a promoted piece! How did that happen? We can’t tell exactly when or in what order, but a white pawn must have reached g6, captured a black piece on h7 and promoted to a bishop. The captured piece could have been a queen, a rook, a bishop, or a knight, but it couldn’t have been a pawn. (I’ll leave it to you to work out why!)

Remember: in retrograde problems, the moves don’t have to be good, they just have to be legal. I am reiterating this now because it’s unlikely that promoting a pawn to a trapped bishop was the best move from the viewpoint of the chess player, but it matters not for the chess detective!

Let’s get this parity started

In the next problem, we are presented with an almost full board, except the white rook on h1 is missing. We are told that it is now Black’s turn to move. The problem setter here asks us to find a move that Black must have played in this game.

Problem 2: Black to move. Indicate a move Black must have played.

While we are not able to completely reconstruct the game prior to this point, we can still deduce (with proof!) a move that was played by Black, by arguing in a logical manner.

We immediately notice that since every pawn is still sitting at its original square, the only pieces that could have moved in this scenario are the knights and the rooks. What’s more, the rooks can only have moved when their adjacent knight was not on its original square. This is true for both sides. Evidently the white rook was captured by a knight on either h1 or g1.

OK, so the rook was captured by a black knight on either g1 or h1 which means that a black knight must have reached one of the squares f3/g3/h3, captured the rook and gone back to its original square. We are narrowing possibilities down but we haven’t yet found a specific move that must have been played.

How to make progress? We certainly don’t want to try to list all possible paths that each of the black knights took, and even if we did, we still couldn’t prove which one of them actually appeared on the board. Nevertheless, looking at possible knight itineraries will prove to be useful.

A preliminary observation is that if a knight has returned to its original square after a number of moves by tracing its original path backwards, it must have completed an even number of moves. Right? It jumped $k$ times to go from $A$ to $B$, so it needs to jump $k$ times to return from $B$ to $A$ if it stays on the same path. In total $2k$ moves. Hmm, that’s interesting. Parity (whether a number is odd or even), and invariants (things that never change) are, in general, extremely useful problem solving tools.

This is not an invariant just yet, but perhaps we can show that a knight always needs an even number of moves to return to its original square. We’ve seen that this is true in the case when the knight retraces its steps, but what if it decides to come back through a different path? For this we will exploit another invariant:

When a knight jumps, it always lands on a square of a different colour.

(This is what I would call a lemma!)

Let’s prove this! The knight moves two steps either vertically or horizontally, which by the checkerboard pattern on the chessboard means that before it takes its last step (right/left or up/down) it was on a square with the same colour as the original. Hence it lands on a square of a different colour. QED!

In view of this observation, a light-squared knight will visit dark squares on every odd move and light squares on even ones. A similar result follows for a dark-squared one. The final destination is the original square. Crucially, this means that we start and end on the same colour, so the knight took an even number of moves to return. Let’s summarise our findings:

A knight always needs an even number of moves to return to its original square.

That is a universal truth, proved by rules of logic within the accepted set of axioms. If that’s not a theorem, I don’t know what it is.

OK! We got ourselves an invariant! How can we use it? Both of the black knights are now resting on their original squares. By our theorem above they must have made an even number of moves each, so an even number of moves for Black in total.

Every Black move follows a White move, and since White was the last to move (remember, they tell us it’s Black’s move) White has moved an odd number of times! We’ve already established that White’s moves were completed by its knight(s) and the rook on h1. The white knights have moved an even number of times, which means that the rook made an odd number of moves. This implies that the rook was captured on g1! Parity again: this rook can only travel between g1 and h1, it’s on h1 on every even move it makes and on g1 on odd ones. So a black knight captured the rook on g1.

Almost there! We have now narrowed the possibilities to just two moves, one of which must have been played: …Nh3$\times$g1 or …Nf3$\times$g1. If the black knight were to ever get to the f3 square, it would have put the white king in check. Only a capture can make the check go away because clearly the king can’t move. The black knight is obviously not captured, ergo, it never made it to f3. Therefore the move Nh3$\times$g1 must have been played by Black.

Defeated. Next!

Whose turn is it anyway?

Problem 3: Mate in one.

The question for our final problem is one you would expect from mainstream chess puzzles. Mate in one.

A quick look at the diagram on the right explains why this is a retrograde problem: White can mate in one with N$\times$f7, but Black can also mate with N$\times$c2. Which one is it? In other words, this is a creative way of asking us to determine which side is to move next. We have acquired enough experience to suspect that this is going to be another counting problem.

We can immediately see that no pawn or bishop has moved in this game. It’s therefore not hard to deduce that the queens were also captured on their original squares. So the only pieces that have moved are the knights, at least one rook from either side, and at least one of the kings (the black one has certainly moved). What about the rooks? Each side has made an odd number of moves with their rooks: odd for the wRb1 and the bRg8, and even (possibly 0) for the wRh1 and the bRa8. The black king has made an odd number of moves while his White counterpart has made an even number of moves: this is because the kings here can only move between the d and e squares of their corresponding rows.

Let’s summarise our observations so far: excluding knight moves, White has made an odd number of moves (rooks: odd, king: even), while the Black side has moved an even number of times (king: odd, rook: odd). Let’s now take a closer look at the knights. If the wNd1 originally started on b1,  then by the same arguments we used in the previous problem, it must have made an even number of moves, since b1 and d1 are the same colour. OK, but if that was the case, then the wNh8 must have started on g1 and, by the same argument, it has made an even number of moves as well. The other possibility is that the wNd1 started off at g1, in which case it has made an odd number of moves. The wNh8 must also have made an odd number of moves, for the same reason. No matter what, the white knights have in total made an even number of moves. Arguing in exactly the same way we can prove that the black knights, combined, have made an even number of jumps.

Put it all together: White has made $\text{odd}+\text{even}=\text{odd}$ number of moves, while Black has made $\text{even}+\text{even}=\text{even}$ number of moves. Since a White move always precedes a Black move, and the total number of moves made by both sides is always even after the last Black move, it is Black’s move to play and deliver mate in 1 with N$\times$c2! Solved and done.

From rookie to king

Hopefully this introduction has whetted your appetite for solving retrograde problems. A good place to start are R Smullyan’s books. Before you check out more problems, I suggest looking up the rather special move en passant and the rules of castling as they are frequently employed by composers and give rise to some fascinating puzzles. Perhaps you will be also interested in proof games, a special type of retrograde problem where a final position is given and the goal is to reconstruct the game from the starting position (in a specified number of moves).

Before you go, I want to gift your two final problems to try your hand at. I promise that both are correct and solvable, but they are definitely on the challenging side! No solutions this time but I shall leave you with the words of Sherlock Holmes: “once you eliminate the impossible, whatever remains, no matter how improbable, must be the truth.”

Problem 4: What was the last move? Problem 5: The white king is invisible, where is he?

Dimitrios is a mathematician at the University of Sheffield, where he teaches courses in analysis and financial mathematics. His mathematical interests are in analysis (pure and applied) and inverse problems. When he is not teaching or researching maths, he enjoys recreational maths and problem solving. Ah, and chess problems.
+ More articles by Dimitrios

More from Chalkdust