9
$\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.

$\endgroup$
5
$\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.

$\endgroup$
  • $\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 Aug 5 '14 at 10:24
4
$\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.

$\endgroup$
  • $\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 Aug 4 '14 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 Aug 4 '14 at 20:42
  • 1
    $\begingroup$ Mornington Crescent! $\endgroup$ – Yemon Choi Aug 5 '14 at 3:19
  • 1
    $\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 Aug 5 '14 at 3:58
  • $\begingroup$ @Yoav Kallus in the new version of the paper, that section is 14.1, not 13.1 $\endgroup$ – alexey May 25 '16 at 20:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.