Solvability of Peg Solitaire on Graphs is NP-Complete

被引：0

作者：

Ito, Kazushi ^{[1
]}

Takenaga, Yasuhiko ^{[1
]}

机构：

[1] Univ Electrocommun, Dept Comp & Net Engn, Chofu 1828585, Japan

来源：

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS | 2023年 / E106D卷 / 06期

关键词：

key words; peg solitaire; puzzle; NP-completeness; graph;

D O I：

10.1587/transinf.2022EDP7092

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

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 sas the initial hole. In this paper, we prove that it is NP-complete to decide if a graph is solvable or not.

引用

页码：1111 / 1116

页数：6

共 11 条

[1] Beeler R.A., 2016, B I COMBIN APPL, V77, P30
[2] Beeler R.A., 2017, INTEGERS, V17, pG1
[3] Beeler RA, 2012, AUSTRALAS J COMB, V53, P127
[4] Beeler RA, 2015, AUSTRALAS J COMB, V63, P321
[5] Peg solitaire on graphs
Beeler, Robert A.
Hoilman, D. Paul
[J]. DISCRETE MATHEMATICS, 2011, 311 (20) : 2198 - 2202
[6] Beeler RobertA., 2012, Involve, V5, P473
[7] Reversible peg solitaire on graphs
Engbers, John
Stocker, Christopher
[J]. DISCRETE MATHEMATICS, 2015, 338 (11) : 2014 - 2019
[8] Peg Solitaire on Cartesian Products of Graphs
Kreh, Martin
de Wiljes, Jan-Hendrik
[J]. GRAPHS AND COMBINATORICS, 2021, 37 (03) : 907 - 917
[9] Fool's solitaire on joins and Cartesian products of graphs
Loeb, Sarah
Wise, Jennifer
[J]. DISCRETE MATHEMATICS, 2015, 338 (03) : 66 - 71
[10] NP-COMPLETENESS OF THE HAMILTONIAN CYCLE PROBLEM IN PLANAR DIGRAPHS WITH DEGREE BOUND 2
PLESNIK, J
[J]. INFORMATION PROCESSING LETTERS, 1979, 8 (04) : 199 - 201

← 1 2 →