Journal of Information Processing
Online ISSN : 1882-6652
ISSN-L : 1882-6652
Solving Slitherlink with FPGA and SMT Solver
Tetsuo MiyauchiKiyofumi Tanaka
Author information
Keywords: Slitherlink, FPGA, SMT solver, Z3
JOURNAL FREE ACCESS

2020 Volume 28 Pages 959-969

Details
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.

Content from these authors
© 2020 by the Information Processing Society of Japan
Previous article Next article
feedback
Top
  翻译: