A Queen and her Pawns

Question

Place a queen and as many pawns as possible on a chessboard so that the queen has just one way of capturing all the pawns in precisely as many moves as there are pawns. Pawns do not move and do not protect each other. (Based on an idea of Maurice Ashley on Twitter.)

This is now in The Guardian:

https://www.theguardian.com/science/2023/apr/02/can-you-solve-it-pawn-pandemonium?CMP=share_btn_fb&fbclid=IwAR2KZDQ5t3zrGDm0hWHPJsw7ZM5GgbY2jfGCtWms003MT3LIOLcpxsxAvkw#comments

Answer 1

UPDATE Here is another

19 pawn solution.

with unique capture sequence

0. h8 1. h6 2. h3 3. g3 4. c3 5. g7 6. f7 7. f8 8. d6 9. d8 10. c8 11. g8 12. g1 13. d1 14. d2 15. a2 16. e6 17. e4 18. c6 19. b5

Explanation:

This was designed by hand and then refined with a computer which found 3 more pawns that could fit in.

General strategy:

1. Place a few very low connected pawns (shown in white in the second diagram). The reason these are super useful is that they can "bind" their peers. The most obvious example is the b5 pawn. It can and therefore must make only one connection. With c6. But c6 also must connect with e4 and therefore cannot accept any other connections. Which brings us to

2. Use their direct neighbours shown as rooks in the diagram as "road blocks"- Unlike the white pawns from (1) which must stay isolated "by definition", these secondary pawns can be in the path of many other pawns without being able to connect. For example, c6 prevents c3 and c8 from connecting and because c6 must be last but one to be captured it will block c3 and c8 for their entire life times.

3. Use these constraints to create funnels or pockets. Pawns there can be placed surprisigly densely without creating ambiguity.

Original post:

16 pawns

with unique sequence of captures:

1. b8 2. b5 3. a6 4. h6 5. g5 6. d8 7. c8 8. c2 9. a4 10. g4 11. g3 12. e1 13. a1 14. a3 15. a7 16. f7

I verified uniqueness with a computer, but the main idea on which this answer is built doesn't involve the computer:

As you can see in this colouring half the pawns (the white ones) cannot be captured in consecutive moves therefore captures must alternate black-white-black-...-black-white. This greatly reduces combinatorial complexity and made handcrafting this solution possible.

Answer 2

I have a solution with

14 pawns

As seen here:

Concerning the path:

The h2 pawn must be the last pawn captured. The path around the edge is forced so that the d3 pawn cannot be the first pawn captured.

Answer 3

My initial solution had a flaw, now fixed:

A solution for 17 pawns (main idea taken from loopy walt)

Proof:

The white pawns cannot be taken consecutively, nor first or second. This means the order must be bbw bw bw bw bw bw bw bw.
e1 must be last (from g1) That mean only one option for h6 (b6h6a6), only one for a3 (a6a3a7), and only one for c2(c7c2c8).
Thus, a7 cannot be taken first. In addition, c7 and d2 may not block a7f7 so must be taken before b6. This means the only opening move is a8b8c7c2c8. and b6h6a6a3a7f7(followed by g8g4g1e1) is a mandatory subsequence.
From c8 we can now only move to b6 with c8c7b5b6.

Original flawed solution:

Flawed proof:

The white pawns cannot be taken consecutively, nor first or second. This means the order must be bbw bw bw bw bw bw bw bw.
g4 must be last and taken from c3. That mean only one option for h6 (b6h6a6) and only one for a3 (a6a3a7).
Thus, a7 cannot be taken first. In addition, c7 may not block a7f7 so must be taken before b6. This means the only opening move is a8b8c7. and b6h6a6a3a7f7(followed by e8) is a mandatory subsequence.
From c7 we can then only move to c2 and then b2and d8 will force the end as e8d8c8g4.
We need to pick up e1 and e5 before connection with the rest at b6. Which gives us the only solution: a8b8c7 c2b1e1 e5b5b6 h6a6a3 a7f7e8 d8c8g4.

Answer 4

Here is the answer with

19 pawns

I am not sure this is optimal:

Here is the solution.

0. h1 1. b1 2. f5 3. h7 4. g7 5. f7 6. f6 7. d6 8. h6 9. g5 10. d8 11. h8 12. c3 13. c8 14. b7 15. a7 16. d7 17. a4 18. a6 19. e2

To approach these types of problems, it may be helpful to first consider a smaller board size, such as a 3x3, 4x4, or 5x5, and then determine the corresponding solutions.

3x3

4x4

I have manually constructed both of them using the methodology described below;

To begin creating the pawn board, it's best to first determine the end pawn - where the queen will ultimately end up. This end pawn should only be accessible from one other pawn on the board. To achieve this, we need to carefully consider the placement of the other pawns in relation to the white pawns on the board.

I have chosen (2,2) one for the pawn to the end pawn. Moving forward, it's important to avoid placing any other pawns in the locations currently occupied by the white pawns. (see above) While there may be solutions that involve placing the Queen among the white pawns, for the purposes of clarity, I will refrain from considering such scenarios at this time. We should place black pawns in the remaining empty spaces and position the queen at the top right:

The process becomes more complex when dealing with a 5x5 or larger board, but the underlying principle remains the same - identifying an end pawn location that can only be reached by a single pawn via the queen. For example, for my solution above for 8x8, the end pawn is e2 and the pawn before that is a6. there is no other pawn can reach to e2 by queen. Every solution has to have such two pawns to start with.

I will try to explain how to apply this with 5x5 or more later hopefully :)

Answer 5

Solved the 19 pawn puzzle flipping the ending pawn to the queen and working backwards. Original position by @Oray

Starts at e2: a6,a4,d7,c8,c3,f6,g7,f7,b7,a7,h7,h8,h6,d6,d8,g5,f5,b1,h1