Knight on an Endless Board

A chess knight moves in an L shape: two squares in one direction along a row or a column, then one square at a right angle. From the square (x, y) it can jump to any of the eight squares (x + 1, y + 2), (x + 2, y + 1), (x + 2, y - 1), (x + 1, y - 2), (x - 1, y - 2), (x - 2, y - 1), (x - 2, y + 1) and (x - 1, y + 2).

The board has no edges in any direction. Write knight_moves(start, target) that returns the fewest jumps the knight needs to get from the square start to the square target, each an (x, y) tuple of integers.

Examples

knight_moves((0, 0), (2, 1))     # returns 1
knight_moves((0, 0), (1, 0))     # returns 3
knight_moves((0, 0), (5, 5))     # returns 4
knight_moves((3, -2), (3, -2))   # returns 0

Even the square next door takes three jumps: (0, 0) to (2, 1) to (3, -1) to (1, 0).

Constraints

• All coordinates are between -200 and 200.
• Far targets are tested: a breadth-first search that spreads out over the endless board in every direction, with no limit, visits millions of squares and is far too slow.