著者

Kazuya Haraguchi Ryoya Tanaka

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.58, no.8, 2017-08-15

---

The Building puzzle (a.k.a., the Skyscraper) is a Latin square completion-type puzzle like Sudoku, KenKen and Futoshiki. Recently, Iwamoto and Matsui showed the NP-completeness of the decision problem version of this puzzle, which asks whether a given instance has a solution or not. We provide a stronger result in the present paper; it is still NP-complete to decide whether we can complete a single line of the grid (i.e., a 1 × n or an n × 1 subgrid) without violating the rule.------------------------------This is a preprint of an article intended for publication Journal ofInformation Processing(JIP). This preprint should not be cited. Thisarticle should be cited as: Journal of Information Processing Vol.25(2017) (online)DOI http://dx.doi.org/10.2197/ipsjjip.25.730------------------------------The Building puzzle (a.k.a., the Skyscraper) is a Latin square completion-type puzzle like Sudoku, KenKen and Futoshiki. Recently, Iwamoto and Matsui showed the NP-completeness of the decision problem version of this puzzle, which asks whether a given instance has a solution or not. We provide a stronger result in the present paper; it is still NP-complete to decide whether we can complete a single line of the grid (i.e., a 1 × n or an n × 1 subgrid) without violating the rule.------------------------------This is a preprint of an article intended for publication Journal ofInformation Processing(JIP). This preprint should not be cited. Thisarticle should be cited as: Journal of Information Processing Vol.25(2017) (online)DOI http://dx.doi.org/10.2197/ipsjjip.25.730------------------------------

著者

Kazuya HARAGUCHI Hirotaka ONO

出版者

The Institute of Electronics, Information and Communication Engineers

雑誌

IEICE TRANSACTIONS on Information and Systems (ISSN:09168532)

巻号頁・発行日

vol.E96-D, no.3, pp.481-488, 2013-03-01

---

BLOCKSUM, also known as KEISANBLOCK in Japanese, is a Latin square filling type puzzle, such as Sudoku. In this paper, we prove that the decision problem whether a given instance of BLOCKSUM has a solution or not is NP-complete.