I'm way behind on reading arXiv postings (and other recent papers, for that matter, other than what I've had to for various program committees), but I've kept pointers to some interesting older ones in hopes of catching up later. The three here don't really go very far towards catching up, but they're at least a start.

The three-color and two-color Tantrix rotation puzzle problems are NP-complete via parsimonious reductions, arXiv:0711.1827, Baumeister and Rothe. Tantrix is a puzzle in which one rotates hexagonal tiles in order to match up the colors on the edges of the tiles. The four-color version was already known to be hard; this paper extends the proof to versions of fewer colors. The part in the title about parsimony means that, if the SAT problem being reduced to a Tantrix puzzle has a unique solution, so does the Tantrix puzzle. Therefore, one can use this sort of reduction to reason about puzzle solvers that make deductions based on the assumption that there is a unique solution: since SAT with unique solutions remains difficult (Valiant and Vazirani 1986), Tantrix problems having a unique solution are difficult too.

Phutball is PSPACE-hard, arXiv:0804.1777, Dereniowski. It's hard to see from the rules of Phutball how either player could make any progress at all, but when I played a stronger player once years ago I lost miserably — there's quite a bit of skill to it. The proper complexity class is EXPTIME-complete, I think, but PSPACE-hard is a lot closer to that than my previous NP-completeness proof for testing whether you have an immediate win.

Best play in Fanorona leads to a draw, DOI:10.1142/9789812709677_0243, Schadd et al. Fanorona is a classical and interesting checkers-like game from Madagascar. Here the authors mean best play from the starting position, but classical match play in this game involves starting with several different opening moves and I don't think they solved them all. As is typical for this sort of result, the authors combine a forward search (from the starting position) with an exhaustive retrograde search of all endgames up to 7 pieces. My Fanorona web applet uses a similar strategy (with a smaller endgame database), and while far from perfect is very hard to beat at the higher levels (be sure to click ok after setting the level).