Obviously the last white move was 16. Nf3g1+.
I note that black needs at least 15 moves to place the pieces as they are:
- 4 moves to swap queen with rook as they are (various movements possible),
- 2 moves for the bishop (Bf8g7, Bg7h8),
- 2 moves for the knight (Ng8f6, Nf6g4 or Ng8h6, Nh6g4)
- 1 move each for the two pawns (g7g6 and h7h5)
- 5 moves for the king (any direct route)
Together with the information that it is black's 16th move, this means that all of black's pieces must have taken a direct route to their destination.
Note that black did not capture any white pieces, because white still has 16 pieces on the board. This means in particular that the pawns on g6 and h5 are the pawns from g7 and h7 respectively.
White has promoted the g pawn for a knight. Since black has still the original g pawn, and all pieces except for two pawns, this is only possible, if the white g pawn moved to g6, captured the black pawn on f7 and promoted on f8 for a knight.
The white pawn could only be promoted after the square on f8 was emptied, i.e. the order of moves is roughly: 1) white pawn moves to g6, 2) white pawn captures black pawn on f7, 3) black plays g7g6, and Bf8g7
Before white captured g6xf7, the black e pawn must have been gone as otherwise (with e7, Qd8, Bf8 and Ke8 present), black would have been forced to recapture the white pawn on f7 since it is check (and the black king would have no squares to escape).
Counting the minimum number of white moves now until the position after blacks's 15th move (i.e. with white knights on f3 and g2)
- white's g pawn: 5 moves (g2g4, g4g5, g5g6, g6xf7 f7f8N)
- return the promoted knight from f8 to either f3 or g2: 3 moves
- capturing the e7 pawn and returning the piece:
If this was done by the rook, it would take at least 8 moves. This would make the total (5+3+8>15), so is not possible. So e7 was captured by a white knight, which returned. Both options (a) white knight from g1 capturing e7 and returning to g2 or f3 or (b) white knight from b1 capturing e7 and returning to b1 plus the move Ng1f3; would take 7 moves.
5+3+7=15, meaning that also white moved its pieces on shortest possible routes without any time for waiting moves.
As for the rest, basically it comes down to check how to achieve the main plans in order, i.e.:
- capture the pawn on e7 with a knight and return the knight at least partially (so that the black king is able to get to e7); as mentioned this needs to be done before white captures gxf7
- capture gxf7 and promote the pawn
- return all white pieces to their final destination
During phase "1." black is very limited in moves since the g pawn cannot move yet (has to wait for the white pawn to play gxf7). This leaves as the only possible first moves for black 1....h5 2...Rh6 ... 3...Rf6 4....Nh6.
These four moves are just enough time for white to capture the e7 pawn with the knight on b1 and to return the knight to c3 (making space for the king on e7, i.e. giving black additional "waiting" moves (waiting for white to push the pawn to g6 and play gxf7). Note that white has to capture the e7 pawn with the knight on b1, because trying to capture it with the knight on g1 would take one move longer and black would run out of waiting moves. So the first four moves are: 1. Nc3 h5 2. Nd5 Rh6 3. Nxe7 Rf6 4. Nd5 Nh6 5. Nc3 Ke7.
Phase two starts and white has to push the g pawn forward, because playing for instance 6. Nb1 black would run out of "waiting" moves and would not manage to regroup queen/rook/bishop in time. So, the next three and a half moves (6. g4 Ke6 7. g5 Kf5 8. g6 Kg4 9. gxf7 ) are basically black pushing the king on the shortest available route towards h3 and white pushing the g pawn forward. As mentioned black has to wait with playing g6 until white captures gxf7, so black can only push the king during this phase.
The final phase (9....g6 10. Nf3 Bg7 11. f8=N Bh8 12. Ne6 Qg8 13. Nf4 Rf8 14. Ng2 Kh3 15. Nb1 Ng4 16. Ng1#) is basically just moving the pieces to their final squares. There are no alternative move orders possible. For instance white cannot play Nb1 earlier, because with 14. Ng2 he is just in time to block the bishop from attacking h3, allowing 14. ... Kh3.