Undecidable puzzles

Typing "undecidable" and "puzzle" into MathSciNet turned up a couple of candidates.

Baumeister, Dorothea and Rothe, Jörg, The three-color and two-color Tantrix rotation puzzle problems are NP-complete via parsimonious reductions, Inform. and Comput. 207 (2009), no. 11, 1119–1139, MR2566946 (2011c:68052). According to the summary, the infinite variants of the 3-color and 2-color Tantrix rotation puzzle problems are undecidable. This follows work by M. Holzer and W. Holzer [Discrete Appl. Math. 144 (2004), no. 3, 345–358; MR2098189 (2005j:94043)] showing the same for the 4-color Tantrix puzzle.

Demaine, Erik D. and Hearn, Robert A., Constraint logic: a uniform framework for modeling computation as games, Twenty-Third Annual IEEE Conference on Computational Complexity, 149–162, IEEE Computer Soc., Los Alamitos, CA, 2008, MR2513497 (2010d:68039). This paper introduces a simple game family and proves "a game with three players and a bounded amount of state can simulate any (infinite) Turing computation, making the game undecidable." There are applications to many existing combinatorial games and puzzles.

This answer is not entirely serious, but it does not fit as a comment.

Numberwang is undecidable.

Numberwang, of course, is a fictional popular game show featured as a running gag in the real sketch comedy show The Mitchell and Webb Look. Here is a sample episode of Numberwang. The rules of the game are never explained, but they seem to follow this format: two players alternate calling out arbitrary numbers, and a computer program decides after each move if the string of numbers so far called constitutes Numberwang or not. The player who called out the last number before Numberwang was announced is the winner. The computer program which decides whether a string of numbers is Numberwang was covered in a fictional documentary special. Furthermore, it appears that the program is not a secret, since a home edition of the game is available, complete a with a multi-volume set of books that allow you to compute for yourself whether a string is Numberwang. So Numberwang is a perfect information game.

Surprisingly, a game very much like Numberwang - except limited to m moves and where only natural numbers may be called - is address in section 14.1 of this review paper. If the Numberwang-deciding function is allowed to be any computable function, then the problem of determining, given the Numberwang-deciding program as input, which player has a winning strategy is undecidable. Other interesting results are also given.

A recent (after the question was posted) arxiv preprint proves that Magic the Gathering is Turing-complete.

The abstract states:

This shows that even recognising who will win a game in which neither player has a non-trivial decision to make for the rest of the game is undecidable.