There are plenty of popular NP-hard puzzles,
for example, generalized Sudoku ($n^2 \times n^2$-board), [Flow](http://html5games.com/2012/07/flow-free/) (I cannot give a source for this), Minesweeper, etc.


Recently, I read a bit about aperiodic tilings of the plane, and it is undecidable 
whether a set of tiles can tile the plane or not, since there might be aperiodic tilings. I do not really consider this problem a popular game you would find in a newspaper.


*So, my question is this: what puzzles/games are there that are undecidable in general?*


[The Post correspondence Problem](https://en.wikipedia.org/wiki/Post_correspondence_problem), (PCP), is undecidable and this has a very "puzzle"-feel to it, so I would say this game could qualify.


Perhaps some generalization of the board game [Roborally](https://en.wikipedia.org/wiki/RoboRally) on an infinite board,
would lead to some type of undecidability, that is, there is no algorithm that given a RoboRally configuration produces the resulting configuration after all rules have been applied?


As a funny note, the sand-box game Minecraft allows the user to make circuits, making the game (in theory) Turing complete. 



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](https://mathscinet.ams.org/mathscinet-getitem?mr=2566946) (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](https://mathscinet.ams.org/mathscinet-getitem?mr=2098189) (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](https://mathscinet.ams.org/mathscinet-getitem?mr=2513497) (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. 


