著者

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------------------------------