Skip to Main content Skip to Navigation
Master Thesis

A coin-moving game on graphs

Abstract : 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.
Complete list of metadata
Contributor : Florian Galliot <>
Submitted on : Friday, March 5, 2021 - 4:20:37 PM
Last modification on : Wednesday, September 8, 2021 - 1:50:31 PM


A coin-moving game on graphs.p...
Files produced by the author(s)


  • HAL Id : dumas-03160998, version 1



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



Record views


Files downloads