Corner the Queen

What’s going on

A queen stands somewhere on a big board. Two players take turns moving her, and every move must bring her closer to the bottom-left corner: any number of squares left, down, or diagonally down-left. Whoever puts the queen on the corner wins.

Play a few games against the computer in the scene above. It is hard to beat. That is not because it looks far ahead: it simply knows which squares are safe to leave you on.

Working backwards

Call a square losing if the player who has to move from it will lose against perfect play, and winning otherwise. We can sort the squares out starting from the end:

• The corner (0, 0) is losing: if the queen is there when it’s your turn, your opponent has just won.
• Every square in the bottom row, in the left column, or on the main diagonal is winning: from there you reach the corner in one move.
• Square (1, 2), one across and two up, is losing. Its moves go to (0, 2), (1, 1), (1, 0) and (0, 1), and from each of those your opponent finishes in one move. The same goes for (2, 1).
• Every square that can reach (1, 2) or (2, 1) in one move is now winning. Among the squares left, the next losing ones are (3, 5) and (5, 3).

The two rules behind all this: a square is winning if some move from it leads to a losing square; it is losing if every move from it leads to a winning square. The strategy follows at once. If you stand on a winning square, always move to a losing one. Your opponent then has to give you a winning square back, and so on, until you take the corner.

Press Show losing cells to see the whole map.

The pattern

Here are the losing squares, listing the smaller coordinate first:

(0, 0), (1, 2), (3, 5), (4, 7), (6, 10), (8, 13), (9, 15), (11, 18), (12, 20) …

Two things stand out. The gap between the two numbers grows by one each time: 0, 1, 2, 3, 4… And every whole number turns up exactly once. The first number of each pair is always the smallest number not used so far. That is no coincidence: two losing squares can never share a row, a column or a diagonal, because then one could reach the other in one move.

Now the surprise. Multiply k by the golden ratio φ = 1.618… and round down: you get the first number of the k-th pair. Multiply by φ² = 2.618… and round down: you get the second. For k = 10: 10 × 1.618… = 16.18…, and 10 × 2.618… = 26.18…, so the tenth losing pair is (16, 26).

The same game with stones

Press Show piles. The queen’s position (x, y) is the same thing as two piles of x and y stones. Moving left takes stones from the first pile, moving down takes them from the second, and a diagonal move takes the same number from both. Whoever takes the last stone wins. In China this game is called jianshizi, “picking up stones”. Mathematicians call it Wythoff’s game.

Try it yourself

1. Find the winning move

The queen is on (9, 12) and it’s your move. Where should you put her?

Answer

Diagonally to (4, 7), five squares down-left. This is the only winning move: no losing square lies in row 12 or column 9 below or left of the queen. The difference 12 − 9 = 3 belongs to the pair (4, 7), which is on the same diagonal.

2. Sixteen and twenty-six

You play the stones version with piles of 16 and 26, and you must move first. Is that good news?

Answer

No. (16, 26) is the tenth losing pair, so whatever you take, your opponent can answer with a move back to a losing position. All you can do is make small moves and hope your opponent slips.

3. One per line

Explain why no two losing squares lie in the same row, the same column or on the same diagonal.

Answer

If two losing squares were on one line, the queen could move from the farther one to the nearer one. But from a losing square every move leads to a winning square, so that is impossible. So the losing squares are like queens that cannot attack each other, and because the gaps 0, 1, 2, 3… are all different, each diagonal gets exactly one pair.

Go deeper

• The Dutch mathematician Willem Abraham Wythoff described the game and its golden-ratio solution in 1907.
• The two sequences 1, 3, 4, 6, 8… and 2, 5, 7, 10, 13… split all positive whole numbers between them with nothing left over. This works because 1/φ + 1/φ² = 1, and it’s a special case of Beatty’s theorem.