Retrograde Analysis is a genre of chess problems where the legality of the position is a key element. Part of it anyway. This is essentially a matter of logical reasoning, with high appeal for puzzle enthusiasts. In the meantime I have just collected a few examples with high pedagogical value . Hope this will convince you that retro puzzles are fascinating.
Many introductory texts exist.
After this, you can have a taste of the real modern retro-analysis by looking at Fabel's Introduction to RA . Many shorter introductory texts exist. Grasshopper Grid-Chess Imitator Losing Game Madrasi chess Mao, a.k.a. Schwalbe Shakhmatnaya Kompozitsiya Sinfonie Scacchistiche Springaren StrateGems US Problem Bull. Most problems are provided with solutions, however, there are several problems of which I don't have a solution.