A Faster Solution to the Slitherlink Puzzle Using Integer Programming

IR IPSJ HANDLE Open Access

Bibliographic Information

Other Title
  • 整数計画法を用いた高速なSlitherlinkパズルの解法

Search this article

Abstract

本論文では，人気のあるペンシルパズル“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.

Journal

  • IPSJ Journal

    IPSJ Journal 54 (8), 2103-2108, 2013-08-15

    一般社団法人情報処理学会

Keywords

Details 詳細情報について

Report a problem

Back to top