1. Introduction
1.1. History of the 15-puzzle and its generalizations
The well known intellectual game with 15 numbered square counters has a ancient and remarkable history. The game was created by Noyes Chapman and it was first appeared in the 1870s. It spread quickly and soon it became extremely popular in the United States and Europe. This is W. Arens’s comments on the influence of 15-puzzle:“Here you could even see the passengers in horse trams with the game in their hands. In offices and shops bosses were horrified by their employees being completely absorbed by the game during office and class hours. Owners of entertainment establishments were quick to latch onto the rage and organized large contests. The game had even made its way into solemn halls of the German Reichstag."In the 1900’s, many people worked tirelessly to solve the problems related to the 15-puzzle, but actually some of them can be seen to be unsolvable due to the power of mathematics. Of course, the most famous issue must be the problem proposed by the impish puzzle maker Sam Loyd. He offered a prize of 1000 dollars for the first correct solution to the problem however it has never been claimed.This is because it is impossible to solve this challenge. People first proved it at the end of 19th century by permutation parity. In the solved state, the permutation is even but swapping only 14 and 15 create an odd permutation.Since then, many extensions of the 15-puzzle have been proposed and studied. [1] studied puzzles with more than 1 empty space, [2] studied puzzles with tiles that are rotatable, and puzzles that allowed rotation without an empty space were discussed in [3].A well-known generalization of the 15-puzzle is that of R. M. Wilson in 1974, where numbered tiles are slid across edges in a graph. Formally, vertices are labeled with numbers, with one vertex labeled the empty space, and we are allowed to swap a numbered label and an adjacent empty label.In his paper [4], he found the group of permutations for non-separable simple graphs. His theorem is sometimes called Wilson’s theorem.
1.2. Contents and paper structure
Building on the generalization of the 15-puzzle onto sliding graph puzzles, we find the group of permutations of labels on sliding graph puzzles that are simple and non-separable using similar ideas as [4], by first finding the group on theta graphs and then inducting on the cyclomatic number. We use a more direct approach in the proof, explicitly finding sequences of moves that carries out certain permutations or generates certain groups. This aids the process of following this proof to create a manual algorithm to solving any sliding graph puzzle. Following this manual algorithm, one can theoretically carry out a sequence of moves to solve any scrambled state of any non-separable sliding graph puzzle. The algorithm is recursive, reducing the cyclomatic number of the unsolved portion of the graph until the problem is reduced to solving a theta graph, which is done directly.
We extend Wilson’s result on the permutation group for a non-separable graph to one that applies to any finite simple graph, and present a new brief proof of the 1-connected and disconnected cases by discussing the movement of tiles across articulation vertices. We also propose a generalization of the manhattan distance metric to any sliding graph, and explore the performance of the A* and suitably weighted A* algorithms in graphs with different cyclomatic numbers.
In section 2, we present an overview of the group theory and permutation groups needed in later discussions. In section 3, we represent states of the 15-puzzle with a permutation and use group theory to show that only states with even permutations can be achieved. In section 4, we show Wilson’s generalization of the 15-puzzle and present our proof of Wilson’s theorem. In section 5, we extend Wilson’s theorem to 1-connected, disconnected, polygon, and non-simple graphs. In section 6, we present a manual algorithm for solving any non-separable graph puzzle. In section 7, we attempt to generalize A* algorithms on the 15-puzzle to solve any sliding graph puzzle. In section 8, we end the paper with suggestions for future work.
2. A review of group theory and permutation groups
In this section, we introduce group theory and permutation groups to aid the discussion in later sections. We see in section 3 and 4 that states on the 15-puzzle and sliding graph puzzles in general can be represented as permutation, and group theory tools are useful for generating and constructing certain permutation groups, such as that of
2.1. Groups and relevant theorems
Definition 2.1. A subset
Definition 2.2. A homomorphism is a function between two groups
Definition 2.3. The image of a homomorphism
Theorem (Lagrange theorem). For a finite group
Definition 2.4. A Sylow p-subgroup is a subgroup with order
Theorem (Second Sylow theorem). If
Theorem (First isomorphism theorem). Let
2.2. Permutations and permutation groups
Definition 2.5. A permutation of a finite set is a rearrangement of its elements, defined as a bijective function (a one-to-one and onto mapping) from the set to itself. A transposition is a permutation that swaps two elements in a set while leaving all other elements unchanged.
Definition 2.6. A permutation is even if it can be expressed as a product of an even number of transpositions. A permutation is odd if it can be expressed as a product of an odd number of transpositions.
Definition 2.7. The symmetric group
Permutations can be expressed using cycle notation, where the elements in the brackets are in one cycle. Each element maps to the next in the cycle, and the last element maps to the first. Every permutation can also be written as a product of transpositions. Below is an example:
In this paper, we use the convention that permutations are evaluated from left to right, or in other words, that the group action of
Proposition 2.8. The alternating groups
Proof. By definition, every even permutation can be written as a product of an even number of transpositions. Separating this product into pairs of transpositions, the following three cases arise, where a,b,c,d are distinct elements:
1.
2.
3.
Since the product of every two transpositions can be expressed as a product of 3-cycles, it follows that the alternating group
Proposition 2.9. The alternating group can be generated by
Proof. Since all alternating group can be generated by 3-cycles, we only need to prove
Case 2: If
Case |
Expression |
Case3: Two elements equal to a and b
If two elements of {x,y,z} are equal to a and b,we have:
Case |
Expression |
|
|
|
|
|
|
|
|
|
|
|
In all cases, any 3-cycle
3. The permutation group of 15-puzzle
In this section, we represent states of the 15-puzzle as permutations, and demonstrate that the set of all legal permutations in the puzzle is isomorphic to A15 .
According to definition 2.7, the set of all states of the 15-puzzle is a subgroup of Sn . Here is an example:

We can represent this state of the 15-puzzle using cycle notation:
When we consider that the position of the blank space remains unchanged between the initial and goal states, the number of moves the blank space makes upward should be equal to the number it makes downward, and the number of moves it makes left should be equal to the number it makes right. Therefore, only when the initial state of 15-Puzzle that is an even permutation can be solved. Therefore, the state where tiles 14 and 15 are swapped cannot be solved because it is an odd permutation.
Using this logic, we only prove that the 15-puzzle is a subgroup of the alternating group, and we still need to determine whether all even permutations can be solved. To prove that all even permutations can be solved, we largely follow the process in [5] and we use Propositions 2.8 and 2.9 from the previous section.
Firstly, we construct a 3-cycle

The next step is constructing "the long cycle", ρ = (1, 2, 6, 7, 3, 4, 8, 15, 10, 14, 13, 9, 5). This cycle is constructed by temporarily displacing tiles 11 and 12 from their original slots and do a sequence of moves. we first change the position of the right bottom corner to that of Fig. 3.3 and move all the tiles except 11 and 12 through the path shown in Fig. 4, and the 15-puzzle will look like Fig. 5.



Finally, we restore the positions of 11 and 12 and this is the entire long cycle ρ .
The purpose of ρ is to move a random tile k to the bottom right corner where the previous three cycle (11,12,15) can act on them. For example, if we want to generate the cycle (3,11,12), we need to apply ρ10 to move the tile 3 to slot 15. Then we can apply the previous 3 cycle (11,12,15) , but tile 3 is at slot 15 so the cycle actually swaps tile 11 12 and 3, shown in Fig. 3.6. Finally, we only need to apply ρ−10 to restore all other tiles to their original positions and we can generate the cycle (3,11,12)$ , shown in Fig. 3.7.


Through this example, we can see that by conjugating the fixed 3-cycle
4. Puzzle group of generalized sliding graph puzzles
In this section, we will generalize the permutation group of the 15-puzzle following the discussion in [4], and provide a variation of a proof of Wilson’s theorem so as to aid the discussion in section 6.
4.1. Generalizing the 15-puzzle
We introduce the following graph theoretic terms to generalize the 15-puzzle.
Definition 4.1. A graph is a collection of vertices (also called nodes) connected by edges. An edge connects 2 vertices. An undirected graph is a graph where no edge has an associated direction. The set of vertices of a graph
Assume from now on that every graph considered is undirected.
Definition 4.2. A simple graph is an undirected graph without loops (edges connecting from a vertex to itself), and any two edges must not have the same end vertices.
Definition 4.3. A path is a sequence of vertices
Definition 4.4. A connected graph is a graph where there exists a path between any pair of vertices. A disconnected graph is a graph that is not connected. An articulation vertex (also cut vertex) of a connected graph is a vertex that, when removed, yields a disconnected graph. A non-separable (also biconnected, 2-connected) graph is a connected graph with no articulation vertices, or a graph with 1 vertex.
Definition 4.5. A bipartite graph is a graph such that each element can be labeled with ’a’ or ’b’ with every edge connecting between a vertex labeled ’a’ and a vertex labeled ’b’. Equivalently, every path from a vertex to itself must have even length (pass through an even number of edges). A non-bipartite graph is a graph that is not bipartite.
Let

Formally define a labeling on the graph
We first prove the following useful proposition:
Proposition 4.6. Let
Proof. Let
1. Moving the blank space to
2. Carrying out
3. Moving the blank space to
4. Moving the blank space to
5. Carrying out
6. Moving the blank space to
and
1. Moving the blank space to
2. Carrying out
3. Moving the blank space to
hence
The puzzle group for any non-separable graph can be determined by the following theorem. Wilson’s theorem is applied to puzzle groups as follows:
Theorem 4.7 Let


Remark. When
4.2. Wilson’s theorem on theta graphs
To prove Theorem 4.7, we largely follow Wilson’s proof in [2]. It is sufficient to prove a weaker result on theta-graphs, which are obtained by subdivisions of the graph shown in Fig. 4.4 that are simple. Start with some arbitrary theta-graph, and attempt to generate the alternating group or symmetric group from a sequence of moves. Denote a theta graph using the length of the simple paths from x to y. For example, consider the (2,2,3) theta graph in Fig. 4.5, with


Since the puzzle group stays unchanged when the solved state is changed, choose a solved state such that
Lemma 4.8. Let
Proof. Instead of using the doubly transitive property of
We can deduce by symmetry and show that
Consider the following permutations:
When
The permutation group of any theta graph contains such elements
Proposition 4.9. The puzzle group of a simple finite connected bipartite graph
Proof. Consider any sequence of moves from the solved state to a labeling
So,
4.3. Considerations for exceptional theta graphs
For the special cases excluded from the above discussion, we discuss each of them individually.



Let
Proposition 4.10. The subgroup
[4]constructed this group by considering the action of the group of linear fractional transformations
Proof. Consider all the subgroups of
These are all the Sylow 5-subgroups of
We show that
So,
4.4. Inducting on the cyclomatic number
We complete the proof of Theorem 4.7 by inducting on the cyclomatic number
Theorem 4.11. Let
Proof. Take any subgraph

Since
We now begin the induction, constructing explicitly the permutations required to generate the puzzle group, without relying on the doubly transitive property of
H=θ0. The below consideration is omitted in [4] and partially omitted in [8]:

Assume that Theorem 4.7 is true for non-bipartite non-separable graphs with cyclomatic number
5. Extensions of Wilson’s theorem
In this section, we extend Theorem 4.7 to 1-connected, disconnected graphs, and polygon graphs. This consideration has already been made by [7] on another theorem in [2], and [10] considered the one-connected case without proof. We give a new brief proof of Theorem 5.1 in this section, an extension of Theorem 4.7:
Theorem 5.1. Let
Proof. If
We can also extend further and consider puzzle groups of undirected, non-simple graphs. However, loops and extra edges do not affect the puzzle group of the graph, so the puzzle group of some finite undirected graph is the puzzle group of the simple graph obtained from removing loops and extra edges. This has also been considered in [2].
6. A manual algorithmic solution to sliding graph puzzles
In this section, we provide a method to solve any sliding graph puzzle with a non-separable graph, using ideas from the proof of Theorem 4.7, and adopting a recursive approach.The objective is to algorithmically carry out a sequence of moves that returns a scrambled state
6.1. The non-bipartite case
Assume that
1. Find a cyclic path
2. Transpose
3. Move the blank label to
4. Conjugate the transposition
5. Move the blank label back to
6. Transpose
After

6.2. The bipartite case
For a bipartite, non-separable graph
1. Find a cyclic path
• If we could find
• If
• If
2. Move the blank label to
3. Conjugate the 3-cycle
4. Revert all other permutations and moves carried out
After
6.3. Solving theta graphs
We need to generate any transposition on a non-bipartite theta graph
7. Generalizations on existing algorithms to sliding graph puzzles
In this section, we attempt to generalize computer algorithms to solve any sliding graph puzzle. The 15-puzzle is a popular test bed for path finding algorithms, and many efficient and optimized algorithms for solving the 15-puzzle have emerged over the years. Usually, such solvers use the A* algorithm or Iterative deepening A* (IDA*) algorithms, with common heuristic function for best first search algorithms being manhattan distance, linear conflict, and walking distance. However, many techniques being used in 15-puzzle solvers are difficult to generalize.Letting
Graph |
Cyclomatic number |
Expanded nodes (A* w/ manhattan |
Expanded nodes (BFS) |
Percentage Decrease |
(2,2,3) theta graph |
2 |
48152.3 |
185222 |
74.003% |
8-puzzle |
4 |
2017.29 |
84869.2 |
97.623% |
8-puzzle, diagonal movements allowed |
12 |
1492.69 |
162282 |
99.080% |
Given the additional time required in computing the manhattan distance metric for each expanded node, the A* algorithm using the manhattan distance heuristics can sometimes be worse than the BFS algorithm time-wise. A possible reason why the manhattan distance heuristic performs so badly for low complexity graphs is because it severely underestimates the remaining number of moves, and the relative error of the heuristic
Graph |
Expanded nodes (A*) |
Expanded nodes (WA*) |
% decrease (nodes) |
% increase (solution moves) |
Weight W |
(2,2,3) theta graph |
48152.3 |
27540.3 |
42.806% |
16.82% |
4.0 |
Fig. 6.1 |
31332.7 |
9691.50 |
69.069% |
6.96% |
2.0 |
|
67138.1 |
3336.26 |
95.031% |
4.80% |
1.4 |
8. Conclusion and further prospects
We end this paper with several suggestions for future work.In section 5, we presented some straightforward extensions of Wilson’s theorem, deducing the group of permutations for 1-connected, disconnected, cyclic, and non-simple graphs. A possible point of interest is to extend further and find this puzzle group for directed graphs.In section 6, a manual algorithm was developed, capable of solving any sliding graph puzzle with a non-separable graph. It could be interesting to develop similar manual algorithms for other generalizations of the 15-puzzle and sliding graph puzzles, such as the sliding graph puzzle with where tiles can rotate. Another possible focus is on a specific family of graphs, such as theta graphs.The algorithm presented in section 6 has numerous inefficiencies and has considerable room for improvement. Due to the heavy reliance on performing 3-cycles and transpositions, which often take hundreds of moves on graphs with a low cyclomatic number, solutions to scrambled states developed using this algorithm are often unnecessarily long. A topic of interest is to develop an efficient algorithm that can solve any sliding graph puzzle, while staying human-solvable.The heuristic used in the A* algorithm implementation in section 7 can possibly be improved upon. It is evident that using only manhattan distance as a heuristic leaves the A* search algorithm lost, especially on graphs with lower complexity. Furthermore, with a heuristic that does not correspond well with the actual number of remaining moves, even the weighted algorithm has a tendency to waste moves. This was especially observed for low-complexity graphs such as the (2,2,3) theta graph. We wonder if there exists a more suitable heuristic for general sliding graph puzzles.
References
[1]. F. Brunck and M. Kwan, “Books, Hallways and social butterflies: A note on sliding block puzzles, " Math Intelligencer 47, 2025, pp. 52–65.
[2]. P. Garcia, A. Hanson, D. Jensen, and N. Owen, “Sliding block puzzles with a twist: On Segerman’s 15 + 4 puzzle”, arXiv preprint, arXiv: 2210.16930, 2022
[3]. C. Yang, “Sliding puzzles and rotating puzzles on graphs, ” Discrete Mathematics, vol. 311, no. 14, pp. 1290–1294, 2011.
[4]. R. M. Wilson, “Graph puzzles, homotopy, and the alternating group, " Journal of Combinatorial Theory, Series B, vol. 16, no. 1, 1974, pp. 86-96.
[5]. Robert A. Beeler, “The Fifteen Puzzle and Related Puzzles (Supplemental Material for Intro to Modern Algebra), " June 28, 2022
[6]. J. Gerald and J. Rotman, “Outer Automorphisms of S6, ” The American Mathematical Monthly, vol. 89, no. 6, 1982, pp. 407–410.
[7]. H. Whitney, “Non-Separable and Planar Graphs, ” Transactions of the American Mathematical Society, vol. 34, no. 2, 1932, pp. 339-362.
[8]. T. Howe, “Two Approaches to Analyzing the Permutations of the 15 Puzzle, ” 2017.
[9]. A. F. Archer, “A Modern Treatment of the 15 Puzzle, ” The American Mathematical Monthly, vol. 106, pp. 793-799, 1999.
[10]. S. J. Russell and P. Norvig, Artificial Intelligence: A Modern Approach, 3rd ed., Prentice Hall, 2010, pp. 98-103.
Cite this article
Wong,C.C.;Li,L.;Chen,R. (2025). Sliding Graph Puzzles: Permutation Groups, Wilson’s Theorem, and New Algorithms. Applied and Computational Engineering,164,117-135.
Data availability
The datasets used and/or analyzed during the current study will be available from the authors upon reasonable request.
Disclaimer/Publisher's Note
The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of EWA Publishing and/or the editor(s). EWA Publishing and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.
About volume
Volume title: Proceedings of CONF-CDS 2025 Symposium: Data Visualization Methods for Evaluation
© 2024 by the author(s). Licensee EWA Publishing, Oxford, UK. This article is an open access article distributed under the terms and
conditions of the Creative Commons Attribution (CC BY) license. Authors who
publish this series agree to the following terms:
1. Authors retain copyright and grant the series right of first publication with the work simultaneously licensed under a Creative Commons
Attribution License that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this
series.
2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the series's published
version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial
publication in this series.
3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and
during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See
Open access policy for details).
References
[1]. F. Brunck and M. Kwan, “Books, Hallways and social butterflies: A note on sliding block puzzles, " Math Intelligencer 47, 2025, pp. 52–65.
[2]. P. Garcia, A. Hanson, D. Jensen, and N. Owen, “Sliding block puzzles with a twist: On Segerman’s 15 + 4 puzzle”, arXiv preprint, arXiv: 2210.16930, 2022
[3]. C. Yang, “Sliding puzzles and rotating puzzles on graphs, ” Discrete Mathematics, vol. 311, no. 14, pp. 1290–1294, 2011.
[4]. R. M. Wilson, “Graph puzzles, homotopy, and the alternating group, " Journal of Combinatorial Theory, Series B, vol. 16, no. 1, 1974, pp. 86-96.
[5]. Robert A. Beeler, “The Fifteen Puzzle and Related Puzzles (Supplemental Material for Intro to Modern Algebra), " June 28, 2022
[6]. J. Gerald and J. Rotman, “Outer Automorphisms of S6, ” The American Mathematical Monthly, vol. 89, no. 6, 1982, pp. 407–410.
[7]. H. Whitney, “Non-Separable and Planar Graphs, ” Transactions of the American Mathematical Society, vol. 34, no. 2, 1932, pp. 339-362.
[8]. T. Howe, “Two Approaches to Analyzing the Permutations of the 15 Puzzle, ” 2017.
[9]. A. F. Archer, “A Modern Treatment of the 15 Puzzle, ” The American Mathematical Monthly, vol. 106, pp. 793-799, 1999.
[10]. S. J. Russell and P. Norvig, Artificial Intelligence: A Modern Approach, 3rd ed., Prentice Hall, 2010, pp. 98-103.