# 六角格子，三角格子上でのスリザーリンクのASP完全性について  [in Japanese] ASP-Completeness of the Slither Link Puzzle on Several Grids  [in Japanese]

## Abstract

パズルやゲームの面白さの源は，それらの持つ根源的な難しさにあり，これまで数多くのパズルやゲームの計算複雑さが解析されている．本稿では，ペンシルパズルの一種であるスリザーリンクの盤面を正k角格子状に一般化した，k‐スリザーリンクを提案し，k‐スリザーリンクの解の存在判定を問う問題のNP完全性を，制限付きハミルトン閉路問題からの多項式時間還元を用いて証明する．また，別解問題（ASP，Another Solution Problem，問題例とその1つの解が与えられたとき，他の解の有無を判定する問題）についても考察し，k‐スリザーリンクの別解問題について，そのNP完全性を示す．A fundamental difficulty to solve games and puzzles seems to become the basis for interest factors of them, and the computational complexity of puzzle games have been investigated. This paper proposes k-Slither Link Puzzle, which is a generalization of the traditional Slither Link Puzzle concerning the grids. The puzzle is one of many popular pencil-and-paper puzzles on rectangular grids k = 4, we deal with the puzzles on all the rest of regular tessellations of the plane, i.e. triangular k = 3 and hexagonal grids k = 6. This paper presents the NP-completeness of k-Slither Link Puzzle for k = 3, 6.Moreover, the NP-completeness of ANOTHER SOLUTION PROBLEMS (ASP), which are problems to decide if there is some solution other than a given solution, of the puzzles is proved in this paper.

A fundamental difficulty to solve games and puzzles seems to become the basis for interest factors of them, and the computational complexity of puzzle games have been investigated. This paper proposes the k-Slither Link Puzzle, which is a generalization of the traditional Slither Link Puzzle concerning the grids. The puzzle is one of many popular pencil-and-paper puzzles on rectangular grids (k=4), we deal with the puzzles on all the rest of regular tessellations of the plane, i.e. triangular (k=3) and hexagonal grids (k=6). This paper presents the NP-completeness of the k-Slither Link Puzzle for k=3, 6. Moreover, the NP-completeness of ANOTHER SOLUTION PROBLEMS (ASP), which are problems to decide if there is some solution other than a given solution, of the puzzles is proved in this paper.

## Journal

• IPSJ SIG Notes

IPSJ SIG Notes 2007(23(2007-AL-111)), 129-136, 2007-03-09

Information Processing Society of Japan (IPSJ)

## Codes

• NII Article ID (NAID)
110006249219
• NII NACSIS-CAT ID (NCID)
AN1009593X
• Text Lang
JPN
• Article Type
Journal Article
• ISSN
09196072
• NDL Article ID
8704773
• NDL Source Classification
ZM13(科学技術--科学技術一般--データ処理・計算機)
• NDL Call No.
Z14-1121
• Data Source
CJP  CJPref  NDL  NII-ELS  IPSJ

Page Top