#### 46000OAYosenabe is NP-complete

Chuzo Iwamoto

vol.54, no.12, 2013-12-15

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.------------------------------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.22(2014) No.1 (online)DOI http://dx.doi.org/10.2197/ipsjjip.22.40------------------------------

まじかー
まじかー

### Twitter (45 users, 46 posts, 13 favorites)

まじかー / “情報学広場：情報処理学会電子図書館” http://t.co/ZU1MWWlwtA
Nicoli-Puzzle-completeか（←違）＞"Yosenabe is NP-complete" https://t.co/YMm7WQxrA4
Yosenabe is NP-completeというので、なぜ寄せ鍋がNP完全なのかと一瞬思ったが、ニコリ社のパズルでそういうのがあるのね。逆に考えるんだ。寄せ鍋や闇鍋がNP完全であるということがどういうことなのかを（時間の無駄だ）。https://t.co/R17HmkNjvJ