La fonctionnalité de recherche est en construction.
La fonctionnalité de recherche est en construction.

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

NP-Completeness of Fill-a-Pix and ΣP2-Completeness of Its Fewest Clues Problem NP-Exhaustivité de Fill-a-Pix et ΣP2-L'intégralité de ses moindres indices

Yuta HIGUCHI, Kei KIMURA

  • Vues en texte intégral

    0

  • Citer

Résumé:

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.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E102-A No.11 pp.1490-1496
Date de publication
2019/11/01
Publicisé
ISSN en ligne
1745-1337
DOI
10.1587/transfun.E102.A.1490
Type de manuscrit
PAPER
Catégories
Algorithmes et Structures de Données

Auteurs

Yuta HIGUCHI
  Toyohashi University of Technology
Kei KIMURA
  Saitama University

Mots-clés

Table des matières