Complexity and Completeness of Finding Another Solution and Its Application to Puzzles

By Takayuki Yato, Takahiro Seta. IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences, 2003

355 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Hanabi is NP-complete, Even for Cheaters who Look at Their Cards (2016, background): “Some concrete examples include classic games, like Hex [12], Sudoku [24], Tetris [10], Go [18], and Chess [14], as well as more recent ones such as Pandemic [19] and Candy Crush [15, 22].”
From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz (2017, background): “While some of our mapppings, e.g., H-QAOA mappings of graph coloring, graph partitioning, and not-all-equal 3-SAT, are close to those in References [6,7], other mappings we describe, including for these problems, are quite different and take advantage of the more general families of mixers supported”