One of the solutions (maybe non optimal)
With black king on g5, h5, a5, or b5 (the game was played within PyChess GUI - without the help of any engines, of course):
1. b4 a5 2. g4 h5 3. d4 Ra6 4. e4 Rhh6 5. d5 Rac6 6. e5 Rhf6
7. dxc6 b6 8. exf6 g6 9. bxa5 d5 10. gxh5 e5 11. c4 Bd6 12. f4 Ne7 13. c5
Kf8 14. cxd6 Be6 15. f5 Nd7 16. fxe6 Kg8 17. fxe7 d4 18. cxd7 e4 19. h4 Kg7
20. Bf4 Kf6 21. Bh2 Kg7 22. Nc3 Kf6 23. Qd2 Kg7 24. O-O-O Kf6 25. Nf3 Kg7
26. Bg2 Kf6 27. Rhf1 Kg7 28. Ne1 Kg8 29. Nd3 Kh8 30. Rf3 Kg8 31. Kb1 Kh8
32. Rc1 Kg8 33. Nd1 Kh8 34. Rc3 ( 34. Nf4 Kg7 35. Ne3 Kf6 36. Nd1 Ke5 37.
Nd3+ Kd5 38. Nc3+ Kc6 39. Nd1+ Kb5 40. Ne3 Ka4 41. Rc3 Kb5 42. a6 Ka4 43.
Nc1 Kb4 44. a4 Qe8 45. a5 Kb5 46. Nd3 Ka4 47. a7 Kb5 48. a6 Ka5 49. a8=Q
Kb5 50. a7 Ka5 51. h6 Ka4 52. h5 Kb5 53. h7 Ka4 54. h6 Kb5 55. h8=Q Ka4 56.
h7 Kb5 57. Qg8 Ka4 58. h8=Q Kb5 59. d8=Q Ka4 60. Qdc8 Kb5 61. Qab8 Ka4 62.
d7 Kb5 63. d8=Q Qc6 64. e8=Q Ka4 65. Qef8 Qd7 66. e7 Qh3 67. Qhh7 Qh6 68.
Qhxh6 Kb5 69. Qhh8 Ka4 70. a8=Q+ ( 70. e8=Q+ Ka5 71. a8=Q# ) 70... Kb5 71.
e8=Q+ ) 34... Kg8 35. Ne3 Kh8 36. a4 Kg8 37. h6 Kh8 38. h7 Kg7 39. h5 Kh6
40. a6 Kg5 41. a7 Kh6 42. a8=Q Kg5 43. e8=Q Kh6 44. Qg8 Kg5 45. h6 Kh5 46.
h8=Q Qb8 47. d8=Q Qc8 48. e7 Qb8 49. h7 Kg5 50. Qgf8 Qc8 51. Qhg8 Qb8 52.
a5 Qc8 53. a6 Qb8 54. a7 Qc8 55. Qb8 Kh5 56. d7 Qb7 57. e8=Q Qa6 58. a8=Q
Qb7 59. Qdc8 Kg5 60. Qaxb7 Kh4 61. Q7a8 Kg5 62. Qaa6 Kh4 63. Qaa7 Kg5 64.
Qaa8 Kh4 65. h8=Q+ ( 65. d8=Q+ Kh5 66. h8=Q# ) 65... Kg5 66. d8=Q+
Update: Some explanation
At first, it's clear that all empty squares are attacked by White, so it must be Black's turn (the black king must be in check). But the most squares are attacked twice or more, so placing the king on one of them would be illegal (double check is virtually impossible here). The only squares which are attacked by a single white piece are a5, b5, g5, h5, b3, e2 and g1. But the last 3 are completely surrounded by doubly-attacked squares, so the black king would have no square to come from. So, we end up with 4 options to consider. The last 2 moves can be, for example, h7-h8=Q+ Kh4(h5)-g5 d7-d8=Q+, or (vice versa) d7-d8=Q+ Kh4(g5)-h5 h7-h8=Q+ (or symmetrical positions on the queenside).
Secondly, let's think about the 18 moves which led to the displayed pawn structure. One of the most economical way (in terms of the number of moves) to make all White's pawns passed requires 8 captures (let's indicate them by files like it's done in Russian-style SAN): ba, gh, dc, ef, cd (x2) and fe (x2). So, Black must finish with 16-8=8 pieces (6 pawn, 1 king and 1 other non-king piece). Now it's clear that Black should make at least 16 moves to prepare the position: 6 pawn moves (b7-b6, d7-d5, d5-d4, e7-e5, e5-e4 and g7-g6) and 8 moves to develop the 6 pieces which were sacrificed (since the only pieces captured on the rook files are the pawns, so the rooks cannot be captured there, thus requiring 2 moves per rook), and 2 moves to free the rooks (a7-a5 and h7-h5).
Again, let's consider one of the most economical ways to develop the pieces on the needed positions: Ra8-a6-c6, Rh8-h6-f6, Bc8-e6, Bf8-d6, Nb8-d7, Ng8-e7 (the pieces are developed onto the needed files to be captured with white pawns). Now it becomes clear that the remaining 2 moves for Black should be king moves, since the 4 white pawns occupying the d6, d7, e6, e7 squares (with the black king on e8 or d8) would either checkmate the black king or force Black to capture one of the pawns, and either option is no good. But even if the king moves to f8 (for example), one of the pawn capture (f6xe7+) will check the black king, and he has to move one more time. So, one of the probable scenarios is Ke8-f8-g8(g7) (it's shown in the example proof game).
Now the task becomes much more trivial: at first, arrange the original white pieces to the needed position, then start pushing and promoting the pawns (for example, take the king to f6 - a relatively safe place - to let the h-pawns pass the h5 square without check, then move him to the final destination - g5-h5-h4 squares, promote some queens which do not bother the black king, using the black queen - only non-sacrificed piece - to do the waiting moves if needed, keeping her on the board as long as possible, and finally do some rearrangements - this way is shown in the example 66- and 71-move games)