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 × XR

(where R is the set of real numbers). For all x, y, z ∈ X,

  1. d(x, y) ≥ 0
  2. d(x, y) = 0 iff x = y
  3. d(x, y) = d(y, x)
  4. 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 (quarter-turn metric which treats 180o turn as two moves) and FTM (face-turn metric which treats 180o 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 right-angled sliding block puzzles, there are the following possible definitions of a move along with proposed short names for corresponding move metrics:

  1. 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.
  2. OMM (Orthogonal Move Metric): slide one tile only in any one direction. When the tile moves around a corner this counts as two moves.
  3. GMM (Group Move Metic): slide any number of tiles together in any one direction.
  4. 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 (single-tile metric).
  5. PMM (Push Move Metric): slide any number of tiles together in any one direction as in 3rd 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 (multi-tile metric).