Subway Shuffle is PSPACE-complete

Abstract: Subway shuffle is an addicting puzzle game created by Bob Hearn. It is played on a graph with colored edges that represent subway lines; colored tokens that represent subway cars are placed on the nodes of the graph. A token can be moved from its current node to an empty one, but only if the two nodes are connected with an edge of the same color of the token. The aim of the game is to move a special token to its final target position. We prove that deciding if the game has a solution is PSPACE-complete even when the game graph is planar.

Subway Shuffle Level 14

Continue reading

The Crazy Frog Puzzle and Permutation Reconstruction from Differences

The Crazy Frog Puzzle (CFP) is the following: we have a $n \times n$ partially filled board, a crazy frog placed on an empty cell and a sequence of horizontal, vertical, and diagonal jumps; each jump has a fixed length and two possible opposite directions. The crazy frog must follow the sequence of jumps, and at each step it can only choose among the two available directions. Can the frog visit every empty cell of the board exactly once (it cannot jump on a blocked cell and on the same cell two times)?

 Crazy Frog PuzzleFigure 1: an example of the Crazy Frog Puzzle on the left and its solution on the right.

 We prove that the Crazy Frog Puzzle is $\sf{NP}$-complete even if restricted to 1 dimension and even without blocked cells. The 1-D CFP without blocked cells corresponds to the problem of reconstructing a permutation from its differences:

Permutation Reconstruction from Differences problem:
Input: a set of $n-1$ distances $a_1,a_2,…,a_{n-1}$
Question: does exist a permutation $\pi_1,…,\pi_n$ of the integers $[1..n]$ such that $| \pi_{i+1} – \pi_i| = a_i$, $i=1,…,n-1$ ?

For example, given the differences $(2,1,2,1,5,3,1,1)$ a valid permutation of $[1..9]$ is $(5,7,6,8,9,4,1,2,3)$

Update 2013-12-19: a new version of the paper is available.

The Complexity of Crazy Frog Puzzle and Permutation Reconstruction from Differences click here to download a draft of the paper


Complexity of the Hidden Polygon Puzzle

The Hidden Polygon Puzzle (for brevity HPP) decision problem  is:

Input: a set $P$ of $m$ integer points on a $n \times n$ square grid and an integer $k \leq m$;

Question: does exist a simple rectilinear polygon with $k$ or more vertices $(v_1,v_2, …, v_t), \; v_i \in P, t \geq k$?

The following figure shows an example of a HPP puzzle.

Hidden Polygon PuzzleFigure 1: Given the 21 points on the right, can we find
a simple rectilinear polygon with at least 16 vertices?
A possible solution is shown on the right.

The problem is a slight variant of the $\sf{NP}$-complete puzzle game Hiroimono; we prove that the Hidden Polygon Puzzle is  $\sf{NP}$-complete, too using a completely different reduction.

click here to download the paper

Hidato is NP-complete

Hidato (also known as Hidoku) is a logic puzzle game invented by Dr. Gyora Benedek, an Israeli mathematician. The rules are simple: given a grid with $n$ cells some of which are already filled with a number between $1$ and $n$ (the first and the last number are circled), the player must completely fill the board with consecutive numbers that connect horizontally, vertically, or diagonally.


Figure 1: An Hidato game (that fits on a $8 \times 8$ grid) and its solution on the right.

We prove that the corresponding decision problem $\sf{HIDATO}$ : “Given a Hidato game that fits in a $m \times n$ grid, does a valid solution exist?” is $\sf{NP}$-complete.

Continue reading

Binary Puzzle is NP-complete

Net puzzleBinary Puzzle (also known as Binary Sudoku) is an addictive puzzle played on a $n \times n$ grid; intially some of the cells contain a zero or a one; the aim of the game is to fill the empty cells according to the following rules:

  • Each cell should contain a zero or a one and no more than two similar numbers next to or below each other are allowed
  • Each row and each column should contain an equal number of zeros and ones
  • Each row is unique and each column is unique

We prove that the decision version of Binary Puzzle is NP-complete.

click here to download the paper

Three easy deletion games on paths

The node deletion game NODE KAYLES is a two persons perfect information game played on a graph $G$. Players alternate picking a node from the graph $G$; the node and its adjacent nodes are deleted. The first player unable to move loses the game. Deciding the winner of a NODE KAYLES game is $\mathsf{PSPACE}$-complete [1]. Similarly in the EDGE KAYLES [1] game the two players must pick an edge; the edge is deleted along with the two endpoint nodes and the edges incident to its two endpoint nodes. The complexity of finding the winner of a EDGE KAYLES game is unknwon. On the Q&A site I submitted a mix of the two games; I call it the BRIDGES AND ISLANDS game: at each turn each player must pick an edge (a “bridge”) or an isolated node (an “island”); if a player picks a node the node is deleted along with its incident edges, if it picks an edge, the edge is deleted along with its two endpoint nodes and the edges incident to them. Like the other two games, the first player unable to move loses the game. I didn’t succeed in finding the complexity of BRIDGES AND ISLANDS.

However decideng the winner is polynomial time solvable when the three games are played on a path. Here I give a quick proof for EDGE KAYLES; the proof for the other two games is similar. Continue reading

The complexity of the puzzle game Net: rotating wires can drive you crazy

An amateur proof that the puzzle game Net is NP-complete.

Net puzzleAbstract
The puzzle game Net, also known as FreeNet or NetWalk, is played on a grid filled with terminals and wires; each tile of the grid can be rotated and the aim of the game is to connect all the terminals to the central power unit avoiding closed loops and open-ended wires. We prove that Net is NP-complete.

click here to download the paper

Have fun with Boulder Dash

An amateur proof that the popular game is NP-hard.

Boulder Dash is a videogame created by Peter Liepa and Chris Gray in 1983 and released for many personal computers and console systems under license from First Star Software. Its concept is simple: the main character must dig through caves, collect diamonds, avoid falling stones and other nasties, and finally reach the exit within a time limit. In this report we show that the decision problem “Is an $N\times N$ Boulder Dash level solvable?” is NP-hard. The constructive proof is based on a simple gadget that allows us to transform the Hamiltonian cycle problem on a 3-connected cubic planar graph to a Boulder Dash level in polynomial time.

 click here to download the paper

NOTE: the same result has been proved by G. Viglietta in the paper: Gaming Is a Hard Job, But Someone Has to Do It! ; his proof, which is embedded in a more general and powerful framework that can be used to prove complexity of games, doesn’t require the Dirt element.