ナンバーリンクのNP完全性と問題の列挙  [in Japanese] NP-Completeness and Enumeration of Number Link Puzzle  [in Japanese]

    • 古妻 浩一 KOTSUMA Kouichi
    • 電気通信大学電気通信学研究科情報工学専攻 Department of Computer Science, Graduate School of Electro-Communications, The University of Electro-Communications
    • 武永 康彦 TAKENAGA Yasuhiko
    • 電気通信大学電気通信学部情報工学科 Department of Computer Science, Faculty of Electro-Communications, The University of Electro-Communications

Abstract

ナンバーリンクとは、格子状の盤面に同じ数字が2個づつ与えられた問題に対し、同じ数字どうしを交差しない線でつなぎ合わせるパズルである。本稿では、盤面に空白のマスを許さない場合においてもナンバーリンクがNP完全となることを証明する。また、与えられた盤面のサイズに対し、ナンバーリンクの数字と正当な線からなる盤面を逆探索を用いて列挙するアルゴリズムを提案する。

Number Link is a puzzle on a square grid. Some numbers are given in cells so that each number appears in two cells, and the object of the puzzle is to connect the cells with the same number by non-crossing lines drawn on the cells. In this paper, we first prove that Number Link is NP-complete even if an answer that has a cell on which no line is drawn is not admitted. Second, we propose an algorithm to enumerate the problems of Number Link with a given size using reverse-search algorithm.

Journal

IEICE technical report. Theoretical foundations of Computing   [List of Volumes]

IEICE technical report. Theoretical foundations of Computing 109(465), 1-7, 2010-03-05  [Table of Contents]

The Institute of Electronics, Information and Communication Engineers

References:  8

You must have a user ID to see the references.If you already have a user ID, please click "Login" to access the info.New users can click "Sign Up" to register for an user ID.

Preview

Preview

Codes

  • NII Article ID (NAID) :
    110008000705
  • NII NACSIS-CAT ID (NCID) :
    AN10013152
  • Text Lang :
    JPN
  • Article Type :
    ART
  • ISSN :
    09135685
  • NDL Article ID :
    10649148
  • NDL Source Classification :
    ZN33(科学技術--電気工学・電気機械工業--電子工学・電気通信)
  • NDL Call No. :
    Z16-940
  • Databases :
    CJP  NDL  NII-ELS 

Share