著者

Demaine Erik D. Okamoto Yoshio Uehara Ryuhei Uno Yushi

出版者

電子情報通信学会

雑誌

IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences (ISSN:09168508)

巻号頁・発行日

vol.E97-A, no.6, pp.1213-1219, 2014-06-01

---

Shakashaka is a pencil-and-paper puzzle proposed by Guten and popularized by the Japanese publisher Nikoli (like Sudoku). We determine the computational complexity by proving that Shakashaka is NP-complete, and furthermore that counting the number of solutions is #P-complete. Next we formulate Shakashaka as an integer-programming (IP) problem, and show that an IP solver can solve every instance from Nikoli's website within a second.