Solving Slitherlink with FPGA and SMT Solver

• Miyauchi Tetsuo

  Japan Advanced Institute of Science and Technology

• Tanaka Kiyofumi

  Japan Advanced Institute of Science and Technology

Abstract

“Slitherlink” is one of popular pencil puzzles. The purpose of the puzzle is to make a link according to the digits written in cells. While determining the existence of a solution to a given puzzle is proved to be an NP-complete class of problems, which means it is difficult to find an effective algorithm to solve the puzzle, solving the puzzle has been studied and there are several previous researches for the puzzle. In this paper, we show two new methods to solve the puzzle. One is with hardware acceleration on an FPGA and the other is based on an SMT solver. We focus on determining inside or outside for each cell instead of making a link and propose a new formulation. With hardware acceleration, it takes 0.1578 seconds on average for solving 10 × 10 puzzles, and with an SMT solver, our solution is faster than previous researches in most cases.

Journal

• Journal of Information Processing

  Journal of Information Processing 28 (0), 959-969, 2020

  Information Processing Society of Japan

Keywords

• Slitherlink
• FPGA
• SMT solver
• Z3

Details

• CRID: 1390286981359958144
• NII Article ID: 130007956359
• DOI: 10.2197/ipsjjip.28.959
• ISSN: 18826652
• Web Site: https://www.jstage.jst.go.jp/article/ipsjjip/28/0/28_959/_pdf
• Text Lang: en
• Data Source:
  • JaLC
  • Crossref
  • CiNii Articles
  • KAKEN
• Abstract License Flag: Disallowed