The search functionality is under construction.

The search functionality is under construction.

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

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)

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.

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 -