The search functionality is under construction.

The search functionality is under construction.

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

Kazushi ITO

The University of Electro-Communications

Yasuhiko TAKENAGA

The University of Electro-Communications

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Kazushi ITO, Yasuhiko TAKENAGA, "Solvability of Peg Solitaire on Graphs is NP-Complete" in IEICE TRANSACTIONS on Information,
vol. E106-D, no. 6, pp. 1111-1116, June 2023, doi: 10.1587/transinf.2022EDP7092.

Abstract: 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.

URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2022EDP7092/_p

Copy

@ARTICLE{e106-d_6_1111,

author={Kazushi ITO, Yasuhiko TAKENAGA, },

journal={IEICE TRANSACTIONS on Information},

title={Solvability of Peg Solitaire on Graphs is NP-Complete},

year={2023},

volume={E106-D},

number={6},

pages={1111-1116},

abstract={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.},

keywords={},

doi={10.1587/transinf.2022EDP7092},

ISSN={1745-1361},

month={June},}

Copy

TY - JOUR

TI - Solvability of Peg Solitaire on Graphs is NP-Complete

T2 - IEICE TRANSACTIONS on Information

SP - 1111

EP - 1116

AU - Kazushi ITO

AU - Yasuhiko TAKENAGA

PY - 2023

DO - 10.1587/transinf.2022EDP7092

JO - IEICE TRANSACTIONS on Information

SN - 1745-1361

VL - E106-D

IS - 6

JA - IEICE TRANSACTIONS on Information

Y1 - June 2023

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

ER -