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

    • 温井 康介 NUKUI Kosuke
    • 大阪電気通信大学総合情報学部情報工学科 Department of Engineering Informatics, Osaka Electro-Communication University
    • 上嶋 章宏 UEJIMA Akihiro
    • 大阪電気通信大学情報通信工学部情報工学科 Department of Engineering Informatics, Osaka Electro-Communication University

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 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   [List of Volumes]

IPSJ SIG Notes 2007(23), 129-136, 2007-03-09  [Table of Contents]

Information Processing Society of Japan (IPSJ)

References:  15

You must have a user ID to see the references.If you already have a user ID, please click "Login" to access the info.New users can click "Sign Up" to register for an user ID.

Cited by:  1

You must have a user ID to see the cited references.If you already have a user ID, please click "Login" to access the info.New users can click "Sign Up" to register for an user ID.

Preview

Preview

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
  • Databases :
    CJP  CJPref  NDL  NII-ELS 

Share