著者
石濱 友裕 久野 誉人
出版者
一般社団法人情報処理学会
雑誌
情報処理学会論文誌 = IPSJ Journal (ISSN:18827764)
巻号頁・発行日
vol.54, no.8, pp.2103-2108, 2013-08-15

本論文では,人気のあるペンシルパズル"Slitherlink"の解法について議論する.多くのパズルがそうであるように,SlitherlinkはNP完全であり,整数計画法を使って求解が可能である.このパズルが,これまでに知られている方法よりも簡潔に定式化でき,はるかに高速に解けることを紹介する.This paper addresses a solution to "Slitherlink", one of popular pencil puzzles. Like many other puzzles, Slitherlink is NP-complete and can be solved using integer programming. We show that the puzzle can be formulated more concisely and solved much faster than in the existing formulation.