Yosenabe is NP-complete (Preprint)

概要

論文の詳細を見る
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)------------------------------
2013-12-15