2012.01.26

Speaker: Jonas Kolker.

Title: The NP-hardness of selected puzzles

Abstract:

Solving puzzles is a popular pastime. There's a vast literature on
the complexity of finding solutions to puzzles. Most interesting
puzzles are NP-complete, yet lend themselves well to human intuition.

A few well-known examples of puzzles for which finding solutions is
NP-complete are Sudoku, Minesweeper and Lemmings. Also, finding
shortest solutions for generalized 15-puzzles as well as staying alive
in Tetris (with the block sequence known in advance) is NP-complete.

Along with Sudoku, several other pen-and-paper puzzles are known to be
NP-complete as well. In this talk, we add to this family of results,
by analyzing the hardness of three such puzzles: Magnets, Kurodoko and
Slither Link (on several grid types). All three can be played at
www.chiark.greenend.org.uk/~sgtatham/puzzles/, under the names
Magnets, Range and Loopy.

In Magnets, the player is to place magnetic or non-magnetic blocks in
a domino-tiled rectangle, subject to the non-adjacency of magnetic
poles and the presence of a given number of positive and negative
poles in each row and column.

In Slither Link, the player is to select a subset of edges in a plane
graph that forms a simple cycle, subject to that cycle having $n_f$
edges adjacent to each face $f$ that contains a clue $n_f$, and any
number of edges adjacent to faces not containing clues.

In Kurodoko, the player is to divide a rectangular grid into black and
white squares such that the black squares are non-adjacent, the white
squares are connected, and the black squares have distances to numeric
clues specified by those clues.

We show all three puzles to be NP-complete; Slither Link we show to be
NP-complete on particular classes of graphs.