The search functionality is under construction.
The search functionality is under construction.

Solvability of Peg Solitaire on Graphs is NP-Complete

Kazushi ITO, Yasuhiko TAKENAGA

  • Full Text Views

    0

  • Cite this

Summary :

Peg solitaire is a single-player board game. The goal of the game is to remove all but one peg from the game board. Peg solitaire on graphs is a peg solitaire played on arbitrary graphs. A graph is called solvable if there exists some vertex s such that it is possible to remove all but one peg starting with s as the initial hole. In this paper, we prove that it is NP-complete to decide if a graph is solvable or not.

Publication
IEICE TRANSACTIONS on Information Vol.E106-D No.6 pp.1111-1116
Publication Date
2023/06/01
Publicized
2023/03/09
Online ISSN
1745-1361
DOI
10.1587/transinf.2022EDP7092
Type of Manuscript
PAPER
Category
Fundamentals of Information Systems

Authors

Kazushi ITO
  The University of Electro-Communications
Yasuhiko TAKENAGA
  The University of Electro-Communications

Keyword