A coin-moving game on graphs - DUMAS - Dépôt Universitaire de Mémoires Après Soutenance Access content directly
Master Thesis Year : 2019

A coin-moving game on graphs


We study a one-player game that is played on an undirected simple graph G=(V,E). Throughout the game, there will be coins sitting on some of the vertices of G (at most one per vertex). There are two versions of this game, unlabelled or labelled, depending on whether the coins are undistinguishable or not. A legal move consists of moving a single coin to a free vertex such that the moved coin has at least two other coins adjacent to it after it is moved. This is called the 2-adjacency restriction. Given two configurations $A$ and $B$, we want to know whether it is possible to go from A to B using only legal moves. In the positive case, we would like an explicit winning sequence of moves. We are also interested in complexity aspects of this problem. This game falls into the category of reconfiguration problems on graphs. The study of this game has been initiated in 2002 by Demaine et. al. in an article which serves as foundation for this Master's thesis. Their work had not been developed since. We start by regrouping the (few) results we know that hold for general graphs. We then go over the triangular grid, where the game is entirely solved, using alternative methods compared to that of Demaine et. al.. Finally, the major part addresses the square grid, where Demaine et. al. obtained a strong result about a large family of puzzles but also left numerous areas to inspect: we complete a few of their results and we introduce new tools to study some previously unexplored cases.
Fichier principal
Vignette du fichier
A coin-moving game on graphs.pdf (2.5 Mo) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

dumas-03160998 , version 1 (05-03-2021)


  • HAL Id : dumas-03160998 , version 1


Florian Galliot. A coin-moving game on graphs. Discrete Mathematics [cs.DM]. 2019. ⟨dumas-03160998⟩
116 View
145 Download


Gmail Facebook X LinkedIn More