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
Fill-a-Pix est un puzzle de crayon et de papier, populaire dans le monde entier depuis qu'il a été annoncé par Conceptis en 2003. Il fournit une grille rectangulaire de carrés qui doivent être remplis pour créer une image. Plus précisément, on nous donne une grille rectangulaire de carrés dont certains contiennent un nombre entier de 0 à 9, et notre tâche est de peindre certains carrés en noir afin que chaque carré avec un nombre entier ait le même nombre de carrés peints autour de lui, y compris le carré lui-même. Malgré sa popularité, la complexité informatique de Fill-a-Pix n'est pas connue. Dans cet article, nous montrons que le puzzle est NP-complet, ASP-complet et #P-complet via une réduction parcimonieuse du problème de satisfiabilité booléenne. Nous considérons également le problème du moins d'indices de Fill-a-Pix, où le problème du moins d'indices a été récemment introduit par Demaine et al. pour analyser la complexité informatique de la conception de « bons » puzzles. Nous montrons que le problème du moins d’indices de Fill-a-Pix est Σ2P-complet.
Yuta HIGUCHI
Toyohashi University of Technology
Kei KIMURA
Saitama University
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.
Copier
Yuta HIGUCHI, Kei KIMURA, "NP-Completeness of Fill-a-Pix and ΣP2-Completeness of Its Fewest Clues Problem" in IEICE TRANSACTIONS on Fundamentals,
vol. E102-A, no. 11, pp. 1490-1496, November 2019, doi: 10.1587/transfun.E102.A.1490.
Abstract: Fill-a-Pix is a pencil-and-paper puzzle, which is popular worldwide since announced by Conceptis in 2003. It provides a rectangular grid of squares that must be filled in to create a picture. Precisely, we are given a rectangular grid of squares some of which has an integer from 0 to 9 in it, and our task is to paint some squares black so that every square with an integer has the same number of painted squares around it including the square itself. Despite its popularity, computational complexity of Fill-a-Pix has not been known. We in this paper show that the puzzle is NP-complete, ASP-complete, and #P-complete via a parsimonious reduction from the Boolean satisfiability problem. We also consider the fewest clues problem of Fill-a-Pix, where the fewest clues problem is recently introduced by Demaine et al. for analyzing computational complexity of designing “good” puzzles. We show that the fewest clues problem of Fill-a-Pix is Σ2P-complete.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E102.A.1490/_p
Copier
@ARTICLE{e102-a_11_1490,
author={Yuta HIGUCHI, Kei KIMURA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={NP-Completeness of Fill-a-Pix and ΣP2-Completeness of Its Fewest Clues Problem},
year={2019},
volume={E102-A},
number={11},
pages={1490-1496},
abstract={Fill-a-Pix is a pencil-and-paper puzzle, which is popular worldwide since announced by Conceptis in 2003. It provides a rectangular grid of squares that must be filled in to create a picture. Precisely, we are given a rectangular grid of squares some of which has an integer from 0 to 9 in it, and our task is to paint some squares black so that every square with an integer has the same number of painted squares around it including the square itself. Despite its popularity, computational complexity of Fill-a-Pix has not been known. We in this paper show that the puzzle is NP-complete, ASP-complete, and #P-complete via a parsimonious reduction from the Boolean satisfiability problem. We also consider the fewest clues problem of Fill-a-Pix, where the fewest clues problem is recently introduced by Demaine et al. for analyzing computational complexity of designing “good” puzzles. We show that the fewest clues problem of Fill-a-Pix is Σ2P-complete.},
keywords={},
doi={10.1587/transfun.E102.A.1490},
ISSN={1745-1337},
month={November},}
Copier
TY - JOUR
TI - NP-Completeness of Fill-a-Pix and ΣP2-Completeness of Its Fewest Clues Problem
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1490
EP - 1496
AU - Yuta HIGUCHI
AU - Kei KIMURA
PY - 2019
DO - 10.1587/transfun.E102.A.1490
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E102-A
IS - 11
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - November 2019
AB - Fill-a-Pix is a pencil-and-paper puzzle, which is popular worldwide since announced by Conceptis in 2003. It provides a rectangular grid of squares that must be filled in to create a picture. Precisely, we are given a rectangular grid of squares some of which has an integer from 0 to 9 in it, and our task is to paint some squares black so that every square with an integer has the same number of painted squares around it including the square itself. Despite its popularity, computational complexity of Fill-a-Pix has not been known. We in this paper show that the puzzle is NP-complete, ASP-complete, and #P-complete via a parsimonious reduction from the Boolean satisfiability problem. We also consider the fewest clues problem of Fill-a-Pix, where the fewest clues problem is recently introduced by Demaine et al. for analyzing computational complexity of designing “good” puzzles. We show that the fewest clues problem of Fill-a-Pix is Σ2P-complete.
ER -