A bit generic hint tho :P
Is there some other special rule\move involved?
Maybe I don't know it?

Yes.

I read the solution.

That is pretty sweet. I never would have even considered it, but then again, it exploits a very specific loophole that only exists in chess problem etiquette, which is not really broadly known. I wasn't aware of that particular rule.

Ok, I'll never guess a thing like that.
I'll check the solution too.

Nerds! =P

Solved it. :)

.
.
.
.
.
Trying not to say much to avoid spoilers: had black's last move been different, the first move to solve this would not be legal and black would have lost castling privilege.

Oh god, I barely understood the solution with all that eng chess notation.. and that move.
WTF, I didn't even know about such rule O_o

It seems indeed clever tho. Kinda what a.. chess lawyer would think maybe XD

Wait, is "eat" the word for capture in Italian?
It's like that in Arabic and sometimes I forget and accidentally use it when talking about chess in English or another language. So Italian too?

I think I got it. Didn't look at the solution, but I think I'm right for both scenarios.

*edit* Looked at the solution and it seems I got it right. Woohoo!

I don't know if it's the official italian term for it, but I always used "eat" a piece, instead of "capture" XD
Funny that it's the same in arabic hehe.

I don't know if it's official either, but it's commonly used in the vernacular language.

f3 e5
g4??

Solve for checkmate.

Sorry to bump this, but I found out this type of chess problem is called retrograde puzzle in case you you're interested in more similar ones. There are some extremely clever ones out there.

Wikipedia has a page on retrograde analysis that includes the problem from OP.
https://en.wikipedia.org/wiki/Retrograde_analysis

The first one is pretty neat. Deduce the only possible last move made by white that could have lead to this position.
https://en.wikipedia.org/wiki/Retrograde_analysis#Example

Hmm definitely an interesting question. I would suspect most game states that are impossible would be easier to see and those remaining would be possible as long as you allow a limitless number of non-competitive moves. What I mean is if I have 9 queens on the board and my opponents pieces are all in their original position that is an impossible game state because I could never promote a pawn through the opposing pawns. But just a random game state could be achieved by moving each piece one square (in lieu of their full allotment). The previous sentences make much more sense in my head but hopefully you know what I meant.

I think the key to identifying an impossible board state lies with analyzing the pawns. If the pawns can legally be moved to such a state then it is viable because all of the other pieces can move back and forth between two squares as needed. The pawns though can only move forward (or diagonal when capturing).

It gets a little tricky if you start adding qualifications: one or both players have never been in check, certain pieces cannot move, specific number of moves, etc. Qualifications like these may make a particular board impossible and make it very hard to determine. But if you just want to know if within the rules of the game the pieces can be arranged in a particular way I think it can be done.