Generalized Hi-Q is NP-complete
Ryuhei Uehara, Shigeki Iwata · Institutional Repositories DataBase (IRDB) · 1990
This paper deals with a popular puzzle known as Hi-Q. The puzzle is generalized: the board is extended to the size n × n, an initial position of the puzzle is given, and a place is given on which only one token is finally placed. The complexity of the generalized Hi-Q is proved NP-complete.