Undecidable puzzles

Question

There are plenty of popular NP-hard puzzles, for example, generalized Sudoku ($n^2 \times n^2$-board), Flow (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, (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 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.

A related question: http://mathoverflow.net/questions/27967/decidability-of-chess-on-an-infinite-board — Sam Hopkins, Aug 04 '14 at 16:38
Read here http://mathoverflow.net/questions/11540/what-are-the-most-attractive-turing-undecidable-problems-in-mathematics — TROLLHUNTER, Aug 04 '14 at 18:19
The link to flow seems to be dead, some small screenshot is visible in the Wayback Machine. However, there is a Wikipedia article describing the game and plenty of pictures showing the game can be found online. — Martin Sleziak, Jan 30 '20 at 16:37
BTW searching for "flow free" np returns the paper: "Zig-Zag Numberlink is NP-Complete" (arXiv:1410.5845". End of the abstract says: "The latter restriction is a common form of the famous Nikoli puzzle Numberlink; our problem is another common form of Numberlink, sometimes called Zig-Zag Numberlink and popularized by the smartphone app Flow Free." — Martin Sleziak, Jan 30 '20 at 16:42

score 9 · Answer 1 · edited Jan 30 '20 at 16:53

9

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.

edited Jan 30 '20 at 16:53

Martin Sleziak

4,608

answered Aug 04 '14 at 19:18

Yoav Kallus

5,926

But seems like it is not a simple function; in the sample episode, the players say "1" several times before it is "numberwang". But it is a good candidate. – Per Alexandersson Aug 04 '14 at 20:39
Unless you are using "simple" in any technical sense, then no, part of the gag is definitely that the program is inscrutable. – Yoav Kallus Aug 04 '14 at 20:42
2

Mornington Crescent! – Yemon Choi Aug 05 '14 at 03:19
2

@YemonChoi Given an arbitrary underground map as an input Mornington Crescent is probably also undecidable. The proof is trivial if going around the circle line more than once is not allowed. That should not arise in normal play, but I'm not sure how to prove it. – Yoav Kallus Aug 05 '14 at 03:58
@Yoav Kallus in the new version of the paper, that section is 14.1, not 13.1 – alexey May 25 '16 at 20:47
@alexey Thanks, updated the reference and changed the link to a fixed version. – Yoav Kallus May 25 '16 at 23:42

score 8 · Accepted Answer · edited Jan 30 '20 at 16:34

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.

+1 for the tantrix reference. I have actually played tantrix with my family, and the puzzle described in the paper is quite natural. — Per Alexandersson, Aug 05 '14 at 10:24

score 5 · Answer 3 · answered Jan 19 '20 at 20:20

5

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.

answered Jan 19 '20 at 20:20

Per Alexandersson

15,598

1

The preprint postdates the question, but Alex Churchill had earlier versions going back to before the question - certainly to 2012, and I think possibly to 2010. – Peter Taylor Mar 09 '23 at 11:02

score 1 · Answer 4 · answered Mar 09 '23 at 10:43

1

A fairly recent puzzle game (Baba is you) is undecidable (allowing for an infinite level), see this preprint.

answered Mar 09 '23 at 10:43

Per Alexandersson

15,598

Undecidable puzzles

4 Answers4

Numberwang is undecidable.