13
$\begingroup$

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.

Improve this question
$\endgroup$
4

4 Answers 4

Reset to default
8
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ +1 for the tantrix reference. I have actually played tantrix with my family, and the puzzle described in the paper is quite natural. $\endgroup$
    – Per Alexandersson
    Commented Aug 5, 2014 at 10:24
9
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – Per Alexandersson
    Commented Aug 4, 2014 at 20:39
  • $\begingroup$ Unless you are using "simple" in any technical sense, then no, part of the gag is definitely that the program is inscrutable. $\endgroup$
    – Yoav Kallus
    Commented Aug 4, 2014 at 20:42
  • 2
    $\begingroup$ Mornington Crescent! $\endgroup$
    – Yemon Choi
    Commented Aug 5, 2014 at 3:19
  • 2
    $\begingroup$ @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. $\endgroup$
    – Yoav Kallus
    Commented Aug 5, 2014 at 3:58
  • $\begingroup$ @Yoav Kallus in the new version of the paper, that section is 14.1, not 13.1 $\endgroup$
    – alexey
    Commented May 25, 2016 at 20:47
5
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – Peter Taylor
    Commented Mar 9, 2023 at 11:02
1
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .