Sure. But
So…
is it a legal position?
Well of course it was for amusement-- That’s the point of puzzles and games to begin with. But the rest of the puzzle is more interesting than that first move. It’s not immediately obvious that you need to underpromote until you look over the details of just how the enemy is locked up, and how you can safely attack that lockup. It’s not immediately obvious that you need to start the pawn with a single move instead of a double, until you look a dozen or so moves into the future and see what it takes to get the queen in the wrong position. Things that aren’t immediately obvious make for good puzzles. But the first move is immediately obvious.
Probably. The black pawns have made 13 captures. The one white piece captured by a non-pawn was White’s a-pawn. When I get home, if I get time, I’ll try to make a possible game leading to that position. (I hope Raymond Smullyan would have been proud of me.)
It’s definitely legal. Here’s a move list that gets you to that position:
1. g4 h5 2. f4 g6 3. f5 hxg4 4. Nf3 gxf5 5. e4 gxf3 6. Rg1 fxe4 7. Qe2 fxe2 8. d3 exd3 9. c4 d5 10. Na3 Bd7 11. Bd2 Ba4 12. Rg6 Bd1 13. Nc2 dxc2 14. Re6 Rh3 15. Rb1 fxe6 16. b4 a5 17. Bg2 axb4 18. Be4 Rd3 19. Bf4 Rd2 20. Rb3 dxc4 21. Bd5 exd5 22. Rd3 c3 23. Rd4 Nf6 24. Rc4 dxc4 25. Bd6 exd6 26. Kf2 c5 27. Kg2 Nd5 28. Kf3 Nf4 29. Kf2 Nd3+ 30. Kg2 Ne1+ 31. Kf2 Rd3 32. Kg1 Bh6 33. Kf2 Bc1 34. Kg1 Bb2 35. Kf2 Kd7 36. Kg1 Kc6 37. Kf2 Kb5 38. Kg1 Ka4 39. Kf2 Ka3 40. Kg1 Kxa2 41. Kf2 Kb1 42. Kg1 Kc1 43. Kf2 Ra3 44. Kg1 Rb3 45. Kf2 Nc6 46. Kg1 Nd4 47. Kf2 Ndf3 48. Kg3 Nd2+ 49. Kf2 Nb1 50. Kg1 Qa5 51. Kf2 Qa6 52. Kg1 Ra3 53. Kf2 b3 54. Kg1 Ra5 55. Kf2 Rb5 56. Kg1 Ba3 57. Kf2 b2 58. Kg1 Qa4 59. Kf2 Qb3 60. Kg1 Qa2 61. Kf2 Rb3 62. Kg1 Rd2 63. Kf2 d5 64. Kg1 d4 65. Kf2 d3 66. Kg1 b5 67. Kf2 b4
I’d guess it’s about 20 or so moves longer than the minimum one would need to recreate the problem.