ARTICLES

Sci. Rep. Kanazawa Univ.
Vol. 65, pp. 11–15, 2021

The 8 puzzle with Neighbors Swap Motion is solvable
Prihardono A RIYANTO and Kenichi K AWAGOE*
Bukalapak, Metropolitan Tower Lantai 22 JI. R. A. Kartini Kav. 14 Cilandak Barat Kec. Cilandak, Kota
Jakarta Selatan, Daerah Khusus Ibukota Jakarta 12430
Institute of Liberal Arts and Science, Kanazawa University
Kanazawa, 920-1192, Japan(Received August 17, 2021 and accepted in revised form November 4, 2021)

Abstract From the movements of “M13 ” on PG(2, 3), we introduce a notion of Neighbors
Swap Motions on the square. By applying Neighbors Swap Motions, the 8 puzzle turns outto be solvable.
Keywords.

1Neighbors Swap Motion, permutation.

Introduction

In [1], Conway constructed a groupoid of certain permutations of 13 letters on the projective plane
PG(2, 3), called “M13 ”. Inspired by this construction, Egner and Beth made a program to play
M13 , which is one of the sliding puzzles [3]. Here we demonstrate M13 . The projective plane
PG(2, 3) has 13 points and 13 lines. One line contains 4 points, and one point is an intersection of4 lines. Any two points are on one line. In Figure 1, we give PG(2, 3) as a graph:Figure 1: The projective plane PG(2, 3) as a graph* Corresponding author

Email: kawagoe@se.kanazawa-u.ac.jp

12The 8 puzzle with Neighbors Swap Motion is solvable

The red vertices of the graph stand for points of PG(2, 3). The black vertices of the graph standfor lines of PG(2, 3). Each edge stands for incidence relations. We put integers 1, . . . , 12 on thered points. The last red point is free, called a hole. A movement of M13 is deﬁned by
1. Select one red point except for the hole. Then there exists only one line which contains theselected point and the hole. Exchange the selected point and the hole.
2. The line contains exactly two points except for the selected point and the hole. Exchange
the two points.
We demonstrate one of the movements of M13 . We start with the initial state of M13 shown inFigure 2. For example, we select the target point labeled with 8. Then there exists only one linecontaining the hole and the point labeled with 8, which lies between points labeled with 8 and 9(Figure 3).

Figure 2: The initial state of M13

Figure 3: The selection of the target pointFirst, we exchange the point labeled with 8 and the hole (Figure 4). Next, we exchange the pointlabeled with 6 and 9 (Figure 5).

Figure 4: The ﬁrst exchange

Figure 5: The second exchange

In M13 , for any labeling of the red points, it is known that we can transform the state into the initialstate by a ﬁnite sequence of these movements.

Prihardono A RIYANTO and Kenichi K AWAGOE

213The 8 puzzle with Neighbors Swap Motion

M13 seems to be some kind of sliding puzzle on the circle. As for the sliding puzzle, the 15puzzle is known as one of the most famous sliding puzzles, which is demonstrated on the square4 × 4. Furthermore, we know that it has two types, solvable or not solvable. Solvable means thata labeling of 15 letters can be transformed into the standard labeling of 1, . . . , 15 from top left tobottom right. It is well known that the labeling of 15 letters is an even permutation if and only if
it is solvable. Similarly, the 8 puzzle is known as a sliding puzzle on the square 3 × 3, which has
also two types, solvable or not solvable. Here, we consider another kind of permutations on thesquare 3 × 3. We call 9 small squares on the 3 × 3 square a cell, and we label 9 cells with 1, . . . , 8and the hole.
Deﬁnition 2.1. Select a target cell that has a side in common with the hole. Then we deﬁne amovement by exchanging the cell and hole, and furthermore
1. if the number of the cell each of which has a side in common with the target cell is 2, theextra movement is deﬁned by swapping between the two cells.
2. if the number of the cell each of which has a side in common with the target cell is 3, theextra movement is deﬁned by swapping between the two cells, where the two swapped cells
are in the same row or in the same column with the target cell.
We call this movement a Neighbors Swap Motion.
We give examples of the Neighbors Swap Motions in the following ﬁgures. The yellow cellstands for the hole.
Example 2.1.
1. Select the target cell labeled with 1. Then cells labeled with 4 and 7 have aside in common with the hole. Hence we exchange between the cell labeled with 1 and thehole, and between two cells labeled with 4 and 7.

2. Select the target cell labeled with 1. Then cells labeled with 2, 6, 8 have a side in commonwith the hole. Since the cell labeled with 6 (the red cell) is in the same row with the target
and the hole, we exchange between the cell labeled with 1 and the hole, and between twocells labeled with 2 and 8.

There are 4 kinds of movements, and we deﬁne them as follows:
Deﬁnition 2.2.

1. u := move the hole up (the target cell down)

2. d := move the hole down (the target cell up)

14

The 8 puzzle with Neighbors Swap Motion is solvable

3. l := move the hole left (the target cell right)
4. r := move the hole right (the target cell left)
Theorem 2.1. Every two cells that have a side in common are exchangeable by a ﬁnite sequenceof Neighbors Swap Motions.
Proof. We consider a graph G8 represented by vertices that are states of permutations of the1, 2, 3, 4, 5, 6, 7, 8 on the 3 × 3 square, where we put the hole 0 at the lower right. The numberof vertices of G8 is 8! = 40320. Edges are deﬁned if one state is obtained from the other state bya Neighbors Swap Motion. We may assume that the hole is at the lower right because we consider
all permutations of 1, . . . , 8. With a breadth-ﬁrst search for G8 , we can show that the graph G8
is connected. In fact, we ﬁnd transpositions of two cells that have a side in a common. All suchtranspositions are given in the following table.

Figure 6: Transpositions by Neighbors Swap Motions

From this theorem, we have the following corollary.
Corollary 2.1. The 8-puzzle with Neighbors Swap Motion is solvable.

3

Comments

Since the Neighbors Swap Motions behave differently at the corner and the side and the inside,
permutations induced by the Neighbors Swap Motions are very complicated. Hence, we ﬁrst
use computer calculations to determine whether G8 is connected or not. In fact, by ﬁnding alltranspositions, we can show that G8 is connected. For the 4 × 4 square, the corresponding graphis so big that we cannot determine whether the graph is connected or not.

Prihardono A RIYANTO and Kenichi K AWAGOE

15Acknowledgements
The authors would like to thank the reviewers for their useful comments.

References[1] J.H. Conway, M13 , Surveys in Combinatorics, London Math. Soc. Lect. Note Series, 241 (1997).
[2] R. Diestel, Graph Theory, Graduate Texts in Mathematics, vol. 173, Springer-Verlag (2018).
[3] S. Egner and T. Beth, How to Play M13 ?, Designs, Codes and Cryptography, 16 (1999), 243–247.
[4] E. Hordern, Sliding Piece Puzzles. Oxford University Press (1987).
[5] S. Saha Ray, Graph Theory with Algorithms and its Applications-In Applied Science and Technology: In Applied
Science and Technology, Springer (2012).