Pearl Puzzles are NP-complete
Erich Friedman · 2002
Introduction Pearl puzzles are pencil and paper puzzles which originated in Japan [11]. Each puzzle consists of a grid of squares, some of which contain white or black pearls. The goal is to find a closed, non-intersecting path passing through every pearl so that a) the path turns at every black pearl, but does not turn immediately before or after, and b) the path does not turn at any white pearl, but does turn immediately before or after. An example of a Pearl puzzle and its solution are shown in Figure 1. Figure 1. A Pearl puzzle (left) and its solution (right) We will show that the question of whether or not a given Pearl puzzle has a solution is NP-complete. To do so, we construct Pearl puzzles which correspond to arbitrary cubic planar graphs. The Pearl puzzle we construct will have a solution if and only if the corresponding graph has a Hamiltonian circuit. Since the problem of determining whether or not a cubic planar graph has a Hamiltonian circuit is known to be NP- complete