IEICE TRANSACTIONS on Information
Complexity of Critter Crunch
Summary :
We study the computational complexity of the puzzle game Critter Crunch, where the player has to rearrange Critters on a board in order to eliminate them all. Smaller Critters can be fed to larger Critters, and Critters will explode if they eat too much. Critters come in several different types, sizes, and colors. We prove the NP-hardness of levels that contain Blocker Critters, as well as levels where the player must clear the board in a given number of moves (i.e., “puzzle mode”). We also characterize the complexity of the game, as a function of the number of columns on the board, in two settings: (i) the setting where Critters may have several different colors, but only two possible sizes, and (ii) the setting where Critters come in all three sizes, but with no color variations. In both settings, the game is NP-hard for levels with exactly two columns, and solvable in linear time for levels with only one column or more than two columns.
- Publication
- IEICE TRANSACTIONS on Information Vol.E105-D No.3 pp.517-531
- Publication Date
- 2022/03/01
- Publicized
- 2021/12/22
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.2021FCP0008
- Type of Manuscript
- Special Section PAPER (Special Section on Foundations of Computer Science - New Trends of Theory of Computation and Algorithm -)
- Category
Authors
Tianfeng FENG
Japan Advanced Institute of Science and Technology (JAIST)
Leonie RYVKIN
Ruhr University Bochum
Jérôme URHAUSEN
Utrecht University
Giovanni VIGLIETTA
Japan Advanced Institute of Science and Technology (JAIST)
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
Tianfeng FENG, Leonie RYVKIN, Jérôme URHAUSEN, Giovanni VIGLIETTA, "Complexity of Critter Crunch" in IEICE TRANSACTIONS on Information,
vol. E105-D, no. 3, pp. 517-531, March 2022, doi: 10.1587/transinf.2021FCP0008.
Abstract: We study the computational complexity of the puzzle game Critter Crunch, where the player has to rearrange Critters on a board in order to eliminate them all. Smaller Critters can be fed to larger Critters, and Critters will explode if they eat too much. Critters come in several different types, sizes, and colors. We prove the NP-hardness of levels that contain Blocker Critters, as well as levels where the player must clear the board in a given number of moves (i.e., “puzzle mode”). We also characterize the complexity of the game, as a function of the number of columns on the board, in two settings: (i) the setting where Critters may have several different colors, but only two possible sizes, and (ii) the setting where Critters come in all three sizes, but with no color variations. In both settings, the game is NP-hard for levels with exactly two columns, and solvable in linear time for levels with only one column or more than two columns.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2021FCP0008/_p
Copy
@ARTICLE{e105-d_3_517,
author={Tianfeng FENG, Leonie RYVKIN, Jérôme URHAUSEN, Giovanni VIGLIETTA, },
journal={IEICE TRANSACTIONS on Information},
title={Complexity of Critter Crunch},
year={2022},
volume={E105-D},
number={3},
pages={517-531},
abstract={We study the computational complexity of the puzzle game Critter Crunch, where the player has to rearrange Critters on a board in order to eliminate them all. Smaller Critters can be fed to larger Critters, and Critters will explode if they eat too much. Critters come in several different types, sizes, and colors. We prove the NP-hardness of levels that contain Blocker Critters, as well as levels where the player must clear the board in a given number of moves (i.e., “puzzle mode”). We also characterize the complexity of the game, as a function of the number of columns on the board, in two settings: (i) the setting where Critters may have several different colors, but only two possible sizes, and (ii) the setting where Critters come in all three sizes, but with no color variations. In both settings, the game is NP-hard for levels with exactly two columns, and solvable in linear time for levels with only one column or more than two columns.},
keywords={},
doi={10.1587/transinf.2021FCP0008},
ISSN={1745-1361},
month={March},}
Copy
TY - JOUR
TI - Complexity of Critter Crunch
T2 - IEICE TRANSACTIONS on Information
SP - 517
EP - 531
AU - Tianfeng FENG
AU - Leonie RYVKIN
AU - Jérôme URHAUSEN
AU - Giovanni VIGLIETTA
PY - 2022
DO - 10.1587/transinf.2021FCP0008
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E105-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2022
AB - We study the computational complexity of the puzzle game Critter Crunch, where the player has to rearrange Critters on a board in order to eliminate them all. Smaller Critters can be fed to larger Critters, and Critters will explode if they eat too much. Critters come in several different types, sizes, and colors. We prove the NP-hardness of levels that contain Blocker Critters, as well as levels where the player must clear the board in a given number of moves (i.e., “puzzle mode”). We also characterize the complexity of the game, as a function of the number of columns on the board, in two settings: (i) the setting where Critters may have several different colors, but only two possible sizes, and (ii) the setting where Critters come in all three sizes, but with no color variations. In both settings, the game is NP-hard for levels with exactly two columns, and solvable in linear time for levels with only one column or more than two columns.
ER -
English
