Computational Complexity of Building Puzzles

Chuzo IWAMOTO; Yuta MATSUI

doi:10.1587/transfun.E99.A.1145

Computational Complexity of Building Puzzles

Chuzo IWAMOTO, Yuta MATSUI

Full Text Views

0

Share
Cite this

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

building puzzle, pencil puzzle, NP-complete

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://globals.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 -