Yosenabe is NP-complete

• Item type: JInfP(1)
• 公開日: 2014-01-15
• タイトル: Yosenabe is NP-complete
• タイトル / 言語: en
• タイトル: Yosenabe is NP-complete
• 言語: eng
• キーワード / 主題Scheme: Other
• キーワード / 主題: [Regular Papers (Technical Note)] NP-complete, computational complexity, one-player game, Yosenabe
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: Hiroshima University, Graduate School of Engineering
• 著者所属(英): en
• 著者所属(英): Hiroshima University, Graduate School of Engineering
• 著者名: Chuzo, Iwamoto
• 著者名(英): Chuzo, Iwamoto
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: Yosenabe is one of Nikoli's pencil puzzles, which is played on a rectangular grid of cells. Some of the cells are colored gray, and two gray cells are considered connected if they are adjacent vertically or horizontally. A set of connected gray cells is called a gray area. Some of the gray areas are labeled by numbers, and some of the non-gray cells contain circles with numbers. The object of the puzzle is to draw arrows, vertically or horizontally, from all circles to gray areas so that (i) the arrows do not bend, and do not cross other circles or lines of other arrows, (ii) the number in a gray area is equal to the total of the numbers of the circles which enter the gray area, and (iii) gray areas with no numbers may have any sum total, but at least one circle must enter each gray area. It is shown that deciding whether a Yosenabe puzzle has a solution is NP-complete.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Yosenabe is one of Nikoli's pencil puzzles, which is played on a rectangular grid of cells. Some of the cells are colored gray, and two gray cells are considered connected if they are adjacent vertically or horizontally. A set of connected gray cells is called a gray area. Some of the gray areas are labeled by numbers, and some of the non-gray cells contain circles with numbers. The object of the puzzle is to draw arrows, vertically or horizontally, from all circles to gray areas so that (i) the arrows do not bend, and do not cross other circles or lines of other arrows, (ii) the number in a gray area is equal to the total of the numbers of the circles which enter the gray area, and (iii) gray areas with no numbers may have any sum total, but at least one circle must enter each gray area. It is shown that deciding whether a Yosenabe puzzle has a solution is NP-complete.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA00700121
• 書誌情報: Journal of information processing; 巻 22, 号 1, p. 40-43, 発行日 2014-01-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-6652
• 出版者 / 言語: ja
• 出版者: 情報処理学会