文献

J-GLOBAL ID：201002294386005725   整理番号：10A0444808

ナンバーリンクのNP完全性と問題の列挙

NP-Completeness and Enumeration of Number Link Puzzle

著者 (2件)： 古妻浩一 (電通大) ,  武永康彦 (電通大 電気通信)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 109  号： 465(COMP2009 49-58)  ページ： 1-7  発行年： 2010年03月05日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

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

シソーラス用語： 計算量 ,  問題 ,  *数え上げ理論 ,  *数字 ,  解析 ,  *非決定性 ,  計算理論 ,  *NP完全問題
準シソーラス用語： *パズル ,  *多項式時間 ,  *連鎖解析

分類 (1件)： 数値計算  (JE02000J)

引用文献 (8件)：

• KAYE, Richard. Minesweeper is NP-complete. Mathematical Intelligencer. 2000, 22, 2, 9-15
• CULBERSON, J. Sokoban is pspace-complete. Proc. Int. Conf. on Fun with Algorithms, Elba, June, 1998, Proc. Informatics. 1999, 4, 65-76
• 横田雅也. 一般化詰将棋問題の指数時間完全性. 電子情報通信学会論文誌, DI. 2001, J84, 3, 239-246
• DELAHAYE, Jean-Paul. The Science Behind Sudoku. Scientific American magazine. 2006
• ニコリ公式パズルガイド「ナンバーリンク」. http://www.nikoli.co.jp/ja/puzzles/number_link/

タイトルに関連する用語 (4件)： ナンバー ,  リンク ,  NP完全性 ,  問題