Computational Complexity of Building Puzzles


IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E99-A   No.6   pp.1145-1148
Publication Date: 2016/06/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E99.A.1145
Type of Manuscript: Special Section LETTER (Special Section on Discrete Mathematics and Its Applications)
building puzzle,  pencil puzzle,  NP-complete,  

Full Text: PDF>>
Buy this Article

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.