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