# Identify this type of graph puzzle

There are $$V-1$$ pieces, each with an identifying symbol. The board is a graph with $$V$$ vertices and some number of edges $$E$$. The idea is to move around the pieces so that each piece's symbol matches the underlying vertex's symbol. You can only move a piece if it is connected to the empty vertex by an edge. One of the vertices is blank (no symbol) since there is one more vertex than pieces. Is there a name for this type of puzzle?

Since you put the question into a graph theory context, the most appropriate name for these games might be "(Labeled) Pebble Motion Problems", those being the generalisation of the 15 puzzle onto arbitrary graph and piece configurations.

• Thank you as well! That is a very specific name and I am happy to see a Wikipedia article about it. Thus I am making this the accepted answer. – Mixolydian Feb 7 at 17:01
• @Bass neat, I didn't know that these had a "name"! Good to know. – Hugh Feb 7 at 18:04

I posted a comment about this, but I think I'll change it into an answer.

I don't actually think there is a "name" to this type of puzzle, but I'll show one specific example of this puzzle where the community has adopted a name for the puzzle.

That game specifically being the Nancy Drew game Labyrinth Of Lies. In the game, a slightly different version is used, with $$V - 3$$ tokens instead of $$V - 1$$ — but I believe that my answer should still hold. In many of the 'walkthroughs' of this game, the puzzle is referred to as "The Token Puzzle" or "The Sliding Token Puzzle".

I'm sure that there are many other games that use this type of puzzle, but this is the one I could think of off the top of my head.

• Thank you! I think this is pretty much the same type of puzzle. I saw your comment before you changed it to an answer and you linked to an image of that puzzle - which I think was this one - i.ytimg.com/vi/o9LmrrX62Ho/maxresdefault.jpg - including it here for reference. – Mixolydian Feb 7 at 15:56
• @Mixolydian You're welcome! I'm glad I could help. – Hugh Feb 7 at 16:03