Puzzles on graphs

The morbid infatuation with Sam Loyd's Fifteen that followed its introduction in the late 1870's ended with an article in the American Journal of Mathematics [Ref 2]. However, interest in what's known as Combinatorial Games continues to this day. [Ref 1] offers a compendium of known results. This is where I have discovered a reference to R.M.Wilson's paper in which by abstracting the 15 puzzle as a puzzle on graphs he, in one blow, classified a whole family of puzzles. I shall not be able to go into the details of the proof but shall provide a background information that may make the formulation of the main result in the paper more intuitive. The paper serves as a fine example of the power and utility of generalization in Mathematics. But first I need a few definitions.

Definition

A graph is called simple if no two edges are equal as sets. In other words, a graph is simple if at most one edge connects any two nodes.
A graph is called bipartite if the set of its vertices can be represented as a union of two disjoint sets such that no two nodes of the same set are connected by an edge. I.e., edges only go from the nodes of one set to the nodes of another.
A subgraph of a graph is a graph whose vertices and edges form subsets of the sets of vertices and edges, respectively, of the given graph that may be called a supergraph.
A connected component of a node is the biggest subgraph of a graph that consists of all the nodes that serve as endpoints of walks starting at the given node. A connected component of one node is a connected component of all its nodes.
A graph that consists of a single connected component is said to be connected. It's disconnected, otherwise.
A node of a graph is called an articulation if its removal renders the graph disconnected.
A connected graph with no articulation nodes is called nonseparable.

Remark

The graph of the Konigsberg Bridges is not simple.
Obviously, a graph is connected if and only if it consists of a single connected component.
Bipartite graphs often appear as a Description of mapping (or matches) between two sets. If the definition seems to you a little contrived consider representation of the following real world matches: resumes and job openings, boys and girls in a dance class, seats and passengers.

This is more or less obvious that the board of the 15 puzzle might be abstracted to a 4x4 graph every counter position corresponding to a node. Edges indicate possible puzzle moves, i.e. moves of the empty square. Less obvious is that the graph is bipartite. There is nothing to prepare you for this fact. Even as I write this I feel a tinge of surprise. How could one think of separating a solid puzzle into two parts without damaging the board? Do you feel the power of abstraction? Power may be a wrong word or be wasted fruitlessly unless a benefit is gained by looking at the puzzle as a game on a graph. And a benefit there is as I plan to demonstrate shortly. But abstracting the board is obviously not enough. We still have to shift the counters as stipulated by the rules.

Definition

The set of vertices of a graph G is denoted as V(G).
The set of edges of a graph G is denoted as E(G).
|A| stands for the number of elements in a set A.
For a graph G with |G|=n a labeling is a 1-1 correspondence from V(G) onto the set {0,1,2,...,n-1}.
The vertex v corresponding to 0 is said to be unoccupied.

Labeling a graph means placing a unique number at every node. Let's agree that 0 (quite appropriately) corresponds to the empty square. Instead of physically sliding the counters we shall just modify a labeling - clean and simple. What I enjoy about this example is that, as you may have rightly noticed, so far there was not much discussion and nothing was proven either. Bear a little longer (there is going to be another definition) and you'll see the power of finding the right language to describe a problem. As is well known, a problem well described is a problem half solved.

Definition

For a given graph G, puz(G) is a graph whose nodes are all the labelings of G: V(puz(G))={f: f is a labeling of G}.
Two nodes of puz(G) are connected by an edge iff there is a legal move that transforms one labeling into the other.

First of all, since any legal move changes labelings, a labeling can't be transformed into itself by a legal move. Therefore, puz(G) is a simple graph. Secondly, a connected component of puz(G) consists of those labelings that can be transformed into one another by a sequence of legal moves. If puz(G) is proven to be connected then the puzzle on G can be solved from any starting configuration. Otherwise, moving from one labeling to another one is bound to stay inside a connected component of puz(G). Following is a theorem from [Ref 4].

Theorem

Let G be a simple nonseparable graph other than a polygon or the graph shown at right. Then puz(G) is connected unless G is bipartite, in which case puz(G) has exactly two components. In the latter case, labelings f and g on G having unoccupied vertices at even (respectively, odd) distance in G are in the same component of puz(G) iff fg^-1 is an even (respectively, odd) permutation of V(G). For the exceptional case of the graph on the right, puz(G) has exactly 6 components.

The proof gets quite technical but the formulation itself has a very intuitive appeal. The distance between two nodes is of course the length of the shortest walk from one node to another. So that, except for the notion of permutation which I am going to define on the next page, we are all set up to interpret the result. But note right away that the theorem completely resolves the problem for the 15 puzzle and its generalizations to the nxn board with n≠4. The board's graph is always bipartite. Hence puz(G) has two components. Swapping two adjacent counters makes the labelings incompatible - belonging to different connected components of puz(G). The same applies to the Lucky 7 puzzle with n = 7, 11, 15, etc.

Swapping two counters means applying a transposition to a labeling. Moving the empty square is equivalent to applying a sequence of transpositions, the number of transpositions being equal to the number of moves or to the distance between the starting and final locations of the empty square. The theorem then states that if two labelings have the same parity they belong to the same component of puz(G) iff the distance between empty squares in the two labelings is even. If two labelings have different parities they belong to the same component of puz(G) iff the distance between empty squares in the two labelings is odd.

Reference

E.R.Berlekamp, J.H.Conway, R.K.Guy, Winning Ways for Your Mathematical Plays, Academic Press, 1982.
W.E.Story, Note on the '15' puzzle, Amer. J. Math., 2 (1879), 399-404.
R.J.Wilson, Graphs And Their Uses, MAA, New Math Library, 1990.
R.M.Wilson, Graph Puzzles, Homotopy, and the Alternating Group, J. of Combinatorial Theory, Ser B 16, 86-96 (1974).

71547089