The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Kami mengkaji kerumitan pengiraan permainan teka-teki Critter Crunch, di mana pemain perlu menyusun semula Critters pada papan untuk menghapuskan kesemuanya. Critters yang lebih kecil boleh diberi makan kepada Critters yang lebih besar, dan Critters akan meletup jika mereka makan terlalu banyak. Makhluk datang dalam beberapa jenis, saiz dan warna yang berbeza. Kami membuktikan NP-kekerasan tahap yang mengandungi Critters Penghalang, serta tahap di mana pemain mesti mengosongkan papan dalam bilangan pergerakan tertentu (iaitu, "mod teka-teki"). Kami juga mencirikan kerumitan permainan, sebagai fungsi bilangan lajur pada papan, dalam dua tetapan: (i) tetapan di mana Critters mungkin mempunyai beberapa warna berbeza, tetapi hanya dua saiz yang mungkin, dan (ii) tetapan di mana Critters datang dalam ketiga-tiga saiz, tetapi tanpa variasi warna. Dalam kedua-dua tetapan, permainan ini adalah NP-hard untuk tahap dengan tepat dua lajur, dan boleh diselesaikan dalam masa linear untuk tahap dengan hanya satu lajur atau lebih daripada dua lajur.
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.
Salinan
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
Salinan
@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},}
Salinan
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 -