IEICE TRANSACTIONS on Fundamentals
Computational Complexity of Building Puzzles
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E99-A No.6 pp.1145-1148
- Publication Date
- 2016/06/01
- Publicized
- 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)
- Category
Authors
Chuzo IWAMOTO
Hiroshima University
Yuta MATSUI
Hiroshima University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Chuzo IWAMOTO, Yuta MATSUI, "Computational Complexity of Building Puzzles" in IEICE TRANSACTIONS on Fundamentals,
vol. E99-A, no. 6, pp. 1145-1148, June 2016, doi: 10.1587/transfun.E99.A.1145.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E99.A.1145/_p
Copy
@ARTICLE{e99-a_6_1145,
author={Chuzo IWAMOTO, Yuta MATSUI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Computational Complexity of Building Puzzles},
year={2016},
volume={E99-A},
number={6},
pages={1145-1148},
abstract={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.},
keywords={},
doi={10.1587/transfun.E99.A.1145},
ISSN={1745-1337},
month={June},}
Copy
TY - JOUR
TI - Computational Complexity of Building Puzzles
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1145
EP - 1148
AU - Chuzo IWAMOTO
AU - Yuta MATSUI
PY - 2016
DO - 10.1587/transfun.E99.A.1145
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E99-A
IS - 6
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - June 2016
AB - 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.
ER -
English
