著者

加賀谷 光祐 冨澤 眞樹 遠山 宏明

出版者

The Institute of Electronics, Information and Communication Engineers

雑誌

電子情報通信学会論文誌 D (ISSN:18804535)

巻号頁・発行日

vol.J105-D, no.3, pp.144-153, 2022-03-01

---

Lunar Lockoutは解の存在を判定する問題がNP困難であることが知られているスライディングブロックパズルである.また,Generalized Lunar Lockout Variantは動かない駒の使用を認めたLunar Lockoutであり,解の存在を判定する問題はPSPACE完全であることが示されている.本研究では,Generalized Lunar Lockout Variantに対して,各駒の移動回数を高々k回に制限した解が存在するか否かを判定する問題を導入し,k≧ 3のときNP完全であることを証明した.