Given a higher dimensional rook or bishop as previously described, compute a path which reaches a given destination in the smallest number of moves.

In 2D on an empty board, a rook or bishop takes at most 2 moves to reach any given (accessible) square, and it is not difficult to describe the positions in which they require only 1.

In N dimensions, I suspect at most N moves are necessary (which is a lot). When can we get there in less, and how?

The movement of both pieces can be described as a integer scalar multiple of a vector whose components are all -1, 0, or 1. For a bishop, the number of nonzero components is even; for a rook, odd. Without loss of generality, assume the piece is at the origin. Find moves which sum to the coordinates of the destination. This seems reminiscent of bin-packing.

One heuristic is, for all possible moves from the current location, choose the one that minimizes the straight-line (Euclidean) distance to the destination: the distance from a point to a line. Repeat for the next move.

Other open problems: computational complexity; the tricky knight; what if there are obstacles?

## No comments :

Post a Comment