Move metrics
02 / 12 / 2012
Distance
See also: Jaap's Puzzle Page (Metrics).
In mathematics, a metric on a set X is a function
d : X × X → R
(where R is the set of real numbers). For all x, y, z ∈ X,
 d(x, y) ≥ 0
 d(x, y) = 0 iff x = y
 d(x, y) = d(y, x)
 d(x, z) ≤ d(x, y) + d(y, z)
Function d is also called distance function.
Let X be set of all reachable configurations of the puzzle. Then distance between two puzzle configurations is the minimum number of moves required to go from one to another. In other words, distance is the length of the shortest path connecting these configurations. It is assumed that such path exists, otherwise distance is positive infinity.
Move metrics
To find distance between two configurations, you need to count moves in optimal solution. To count the moves, you need to know exactly what is a move. Move metric on a puzzle is such definition.
On standard 3 × 3 × 3 Rubik's cube, there are two move metrics, namely QTM (quarterturn metric which treats 180^{o} turn as two moves) and FTM (faceturn metric which treats 180^{o} turn as one move).
On integer puzzle with 1 × 1 tiles, there are at least two natural metrics. First, we can assume that each move affects just one tile. Such metric is called STM (single tile metric). STM metric is mainly used in researches.
Some people are more convenient to move tiles intact lines rather than one by one. For example, on classic Fifteen Puzzle, it is possible to move up to three tiles at once. The move metric that counts this as single move is called MTM (multi tile metric).
On the integer rightangled sliding block puzzles, there are the following possible definitions of a move along with proposed short names for corresponding move metrics:
 NMM (Natural Move Metric): slide one tile only in any direction or combination of directions. Edward Hordern argued in his book "Sliding Piece Puzzles" that this definition of move is most natural.
 OMM (Orthogonal Move Metric): slide one tile only in any one direction. When the tile moves around a corner this counts as two moves.
 GMM (Group Move Metic): slide any number of tiles together in any one direction.
 SMM (Short Move Metric): slide one tile in any orthogonal direction one unit. Then successive sliding the same tile in the same direction twice counts as two moves. This metric is generalization of STM (singletile metric).
 PMM (Push Move Metric): slide any number of tiles together in any one direction as in 3^{rd} definition; however, only one tile can be physically touched at move. This tile is used to push other tiles. The PMM metric is generalization if MTM (multitile metric).
