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

On Computational Complexity of Pipe Puzzles Sur la complexité informatique des puzzles de tuyaux

Takumu SHIRAYAMA, Takuto SHIGEMURA, Yota OTACHI, Shuichi MIYAZAKI, Ryuhei UEHARA

  • Vues en texte intégral

    0

  • Citer

Résumé:

Dans cet article, nous étudions la complexité informatique des puzzles de tuyaux. Un puzzle de tuyaux est une sorte de puzzle de carrelage ; l'entrée est un jeu de cartes, et une partie d'un tuyau est dessinée sur chaque carte. Pour un jeu de cartes donné, nous les disposons et connectons les tuyaux. Il faut raccorder toutes les canalisations sans créer de boucle locale. Alors que les puzzles de carrelage ordinaires, comme les puzzles, demandent de disposer les tuiles avec une cohérence locale, les puzzles de tuyaux demandent de joindre tous les tuyaux. Nous montrons d’abord que le puzzle de tuyaux est NP-complet en général même si la forme du but est assez restreinte. Nous étudions également des cas restreints et montrons quelques algorithmes en temps polynomial.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E102-A No.9 pp.1134-1141
Date de publication
2019/09/01
Publicisé
ISSN en ligne
1745-1337
DOI
10.1587/transfun.E102.A.1134
Type de manuscrit
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Catégories
Casse-têtes

Auteurs

Takumu SHIRAYAMA
  appci corporation
Takuto SHIGEMURA
  The University of Tokyo
Yota OTACHI
  Kumamoto University
Shuichi MIYAZAKI
  Kyoto University
Ryuhei UEHARA
  JAIST

Mots-clés

Table des matières