Andrew Schultz recently release Fivebyfiveia Delenda Est, a fun small game with chess puzzles that was one of his higher-rated games.
This is a larger game with chess puzzles that have a bit more complexity. There are a bunch of mini-kingdoms to invade and each has two 'tiers' to conquer. The game itself has 2 difficulty settings. I beat it on the first, and started the second, only to realize that it was very similar.
The puzzles involve setting up 2-3 pieces on the chessboard to trap the enemy king. Interestingly, sometimes you have to set up enemy pieces as well.
The storyline is fairly thin but understandable. The game sometimes holds your hand a bit more than I would have wanted. Specifically, beating one area sometimes automatically beats neighboring areas, even before you know what they do. If I had more idea before I left what each area was like, or was given the option to grey out such areas, I'd prefer that.