Related to: Rubik's cube Type: heuristic function
Description: A 3D extension of the Mahnhattan distance.
Compute the linear distance between 2 points in R3 by computing the sum of the distances of the point in each dimension.

For instance in Rubik's cube: for each cubie, compute the minimum number of moves required to correctly position and orient it, and sum these values over all cubies.

Formula: md3d(p1, p2) = |x1−x2|+|y1−y2|+|z1−z2| is the 3D Manhattan-distance between points p1 and p2.

The Manhattan-distance can be computed in linear time.
external image Uss-akron-manhattan.jpg