- 著者
-
Haraguchi Kazuya
Tanaka Ryoya
- 出版者
- 一般社団法人 情報処理学会
- 雑誌
- Journal of Information Processing (ISSN:03876101)
- 巻号頁・発行日
- vol.25, pp.730-734, 2017
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 l×n or an n×l subgrid)without violating the rule.