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

この論文にアクセスする

この論文をさがす

著者

    • 古妻 浩一 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

抄録

ナンバーリンクとは、格子状の盤面に同じ数字が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.

収録刊行物

  • 電子情報通信学会技術研究報告. COMP, コンピュテーション   [巻号一覧]

    電子情報通信学会技術研究報告. COMP, コンピュテーション 109(465), 1-7, 2010-03-05  [この号の目次]

    一般社団法人電子情報通信学会

参考文献:  8件

参考文献を見るにはログインが必要です。ユーザIDをお持ちでない方は新規登録してください。

各種コード

  • NII論文ID(NAID)
    110008000705
  • NII書誌ID(NCID)
    AN10013152
  • 本文言語コード
    JPN
  • 資料種別
    ART
  • ISSN
    09135685
  • NDL 記事登録ID
    10649148
  • NDL 雑誌分類
    ZN33(科学技術--電気工学・電気機械工業--電子工学・電気通信)
  • NDL 請求記号
    Z16-940
  • データ提供元
    CJP書誌  NDL  NII-ELS 
ページトップへ