The Another Solution Problem (ASP) of a problem Π is the following problem: for a given instance x of Π and a solution s to it, find a solution to x other than s. (The notion of ASP as a new class of problems was first introduced by Ueda and Nagao.) In this paper we consider n-ASP, the problem to find another solution when n solutions are given. In particular we consider ASP-completeness, the completeness with respect to the parsimonious reductions which allow polynomial-time transformation of solutions. As an application, we prove the ASP-completeness (which implies NP-completeness) of three popular puzzles: Slither Link, Cross Sum, and Number Place.
(Based on a paper by Takayuki Yato and Takahiro Seta in IEICE transactions on fundamentals of electronics, communications and computer sciences)