For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Computational Complexity of Building Puzzles
Chuzo IWAMOTO Yuta MATSUI
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2016/06/01
Online ISSN: 1745-1337
Type of Manuscript: Special Section LETTER (Special Section on Discrete Mathematics and Its Applications)
building puzzle, pencil puzzle, NP-complete,
Full Text: PDF>>
The Building puzzle is played on an N×N grid of cells. Initially, some numbers are given around the border of the grid. The object of the puzzle is to fill out blank cells such that every row and column contains the numbers 1 through N. The number written in each cell represents the height of the building. The numbers around the border indicate the number of buildings which a person can see from that direction. A shorter building behind a taller one cannot be seen by him. It is shown that deciding whether the Building puzzle has a solution is NP-complete.