WEKO3
-
RootNode
アイテム
Dosun-Fuwari is NP-complete
https://ipsj.ixsq.nii.ac.jp/records/187412
https://ipsj.ixsq.nii.ac.jp/records/187412f51e170c-22e6-4afd-ae3a-5c045ee0b6fc
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-JNL5904016.pdf (309.3 kB)
|
Copyright (c) 2018 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | Journal(1) | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2018-04-15 | |||||||||
| タイトル | ||||||||||
| タイトル | Dosun-Fuwari is NP-complete | |||||||||
| タイトル | ||||||||||
| 言語 | en | |||||||||
| タイトル | Dosun-Fuwari is NP-complete | |||||||||
| 言語 | ||||||||||
| 言語 | eng | |||||||||
| キーワード | ||||||||||
| 主題Scheme | Other | |||||||||
| 主題 | [一般論文（テクニカルノート）] Dosun-Fuwari, pencil puzzle, NP-complete | |||||||||
| 資源タイプ | ||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||||
| 資源タイプ | journal article | |||||||||
| 著者所属 | ||||||||||
| Graduate School of Engineering, Hiroshima University | ||||||||||
| 著者所属 | ||||||||||
| School of Integrated Arts and Sciences, Hiroshima University | ||||||||||
| 著者所属(英) | ||||||||||
| en | ||||||||||
| Graduate School of Engineering, Hiroshima University | ||||||||||
| 著者所属(英) | ||||||||||
| en | ||||||||||
| School of Integrated Arts and Sciences, Hiroshima University | ||||||||||
| 著者名 |
Chuzo, Iwamoto
× Chuzo, Iwamoto
× Tatsuaki, Ibusuki
|
|||||||||
| 著者名(英) |
Chuzo, Iwamoto
× Chuzo, Iwamoto
× Tatsuaki, Ibusuki
|
|||||||||
| 論文抄録 | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | Dosun-Fuwari is one of Nikoli's pencil puzzles, which is played on a rectangular grid of cells. Some of the cells are colored black, and the remaining cells are divided into rooms. The purpose of the puzzle is to place balloons and iron balls according to the following rules: Place one balloon and one iron ball in each room. Balloons (resp. iron balls) are light and float (heavy and sink), so they must be placed in the top (bottom) row of the grid of cells, or in a cell right under (over) a black cell or right under other balloons (over other iron balls). It is shown that deciding whether a Dosun-Fuwari puzzle has a solution is NP-complete. ------------------------------ This is a preprint of an article intended for publication Journal of Information Processing(JIP). This preprint should not be cited. This article should be cited as: Journal of Information Processing Vol.26(2018) (online) DOI http://dx.doi.org/10.2197/ipsjjip.26.358 ------------------------------ |
|||||||||
| 論文抄録(英) | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | Dosun-Fuwari is one of Nikoli's pencil puzzles, which is played on a rectangular grid of cells. Some of the cells are colored black, and the remaining cells are divided into rooms. The purpose of the puzzle is to place balloons and iron balls according to the following rules: Place one balloon and one iron ball in each room. Balloons (resp. iron balls) are light and float (heavy and sink), so they must be placed in the top (bottom) row of the grid of cells, or in a cell right under (over) a black cell or right under other balloons (over other iron balls). It is shown that deciding whether a Dosun-Fuwari puzzle has a solution is NP-complete. ------------------------------ This is a preprint of an article intended for publication Journal of Information Processing(JIP). This preprint should not be cited. This article should be cited as: Journal of Information Processing Vol.26(2018) (online) DOI http://dx.doi.org/10.2197/ipsjjip.26.358 ------------------------------ |
|||||||||
| 書誌レコードID | ||||||||||
| 収録物識別子タイプ | NCID | |||||||||
| 収録物識別子 | AN00116647 | |||||||||
| 書誌情報 |
情報処理学会論文誌 巻 59, 号 4, 発行日 2018-04-15 |
|||||||||
| ISSN | ||||||||||
| 収録物識別子タイプ | ISSN | |||||||||
| 収録物識別子 | 1882-7764 | |||||||||
