The search functionality is under construction.

The search functionality is under construction.

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 Σ_{2}^{P}-complete.

- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E102-A No.11 pp.1490-1496

- Publication Date
- 2019/11/01

- Publicized

- Online ISSN
- 1745-1337

- DOI
- 10.1587/transfun.E102.A.1490

- Type of Manuscript
- PAPER

- Category
- Algorithms and Data Structures

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.

Copy

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 Σ_{2}^{P}-complete.

URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E102.A.1490/_p

Copy

@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 Σ_{2}^{P}-complete.},

keywords={},

doi={10.1587/transfun.E102.A.1490},

ISSN={1745-1337},

month={November},}

Copy

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 Σ_{2}^{P}-complete.

ER -