If you wanted to solve the easy subproblem separately, probably the most simple strategy was white’s all out offense: make all white pawns reach the last row and promote them all into queens.
Here’s a rather short game that does exactly that:
1. a4 a5 2. b4 b5 3. c4 c5 4. d4 d5 5. e4 e5 6. f4 f5 7. g4 g5 8. h4 h5 9. axb5 Kf7 10.
bxa5 Kg7 11. cxd5 Kh7 12. dxc5 Nf6 13. fxe5 Rg8 14. exf5 Kh8 15. hxg5 Nh7 16. gxh5 Be7
17. a6 Bf6 18. gxf6 Qe8 19. b6 Qg6 20. hxg6 Nd7 21. b7 Rb8 22. e6 Ne5 23. e7 Nf7 24.
gxf7 Ra8 25. f8=Q Bd7 26. e8=Q Ra7 27. b8=Q Rb7 28. a7 Rc7 29. a8=Q Rb7 30. c6 Ra7 31.
c7 Rb7 32. c8=Q Bc6 33. d6 Bb5 34. d7 Bc6 35. d8=Q Bd7 36. Qfc5 Bc6 37. Qe4 Be8 38. f7
Rc7 39. fxe8=Q Rb7 40. f6 Rc7 41. f7 Rd7 42. f8=QNote that 40 moves are necessary just to be able to get all white pawns to the last row. As you can see, our solution uses 42. Here’s a bonus challenge for you: is that optimal, or can you solve it in 41, or even in 40 moves?
Update: Samuel Huang has e-mailed us to point out that 35 moves could be enough – if you promote just seven pawns into other pieces. And indeed, the easy subproblem can be solved in 35 moves and that is the minimum.
Of course, another approach was to realize that any game that solves the hard subproblem also solves the easy one. You could start solving the hard subproblem and then submit its log twice to solve both subproblems. You could even optimize: halfway through solving the hard subproblem, once you have 9 pieces of the same type, submit the log of the game so far, and then continue solving.
What is some theoretical upper bound on the number of rooks? Initially there are four, and there are sixteen pawns that can be promoted, so that would give us a total of twenty rooks. Of course, that’s assuming that no pawn gets ever taken. At the first glance, that seems impossible. I mean, how do you even get the white pawns past the black ones and vice versa without some of them taking the others?
And figuring out how to do that was indeed the main challenge in this subproblem. The picture below tells the whole story. It a configuration our solution reaches at some point. From this configuration it should be fairly obvious both how we reached it and how the game will now proceed.
