Dosun-Fuwari is NP-complete

• Chuzo, Iwamoto

• Tatsuaki, Ibusuki

抄録

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 ofInformation Processing(JIP). This preprint should not be cited. Thisarticle should be cited as: Journal of Information Processing Vol.26(2018) (online)DOI　http://dx.doi.org/10.2197/ipsjjip.26.358------------------------------

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 ofInformation Processing(JIP). This preprint should not be cited. Thisarticle should be cited as: Journal of Information Processing Vol.26(2018) (online)DOI　http://dx.doi.org/10.2197/ipsjjip.26.358------------------------------

収録刊行物

• 情報処理学会論文誌

  情報処理学会論文誌 59 (4), 2018-04-15

キーワード

• [一般論文（テクニカルノート）] Dosun-Fuwari, pencil puzzle, NP-complete

詳細情報

• CRID: 1050845762839760256
• NII論文ID: 170000149462
• NII書誌ID: AN00116647
• ISSN: 18827764
• Web Site: http://id.nii.ac.jp/1001/00187324/
• 本文言語コード: en
• 資料種別: journal article
• データソース種別:
  • IRDB
  • CiNii Articles