Implicit graphs, state-space search and 0-1 BFS

Many search problems have a graph that nobody writes down. In implicit graphs the vertices are states, such as a knight’s square or a puzzle’s tray, and a rule generates the edges from each state only when they are needed. State-space search runs an ordinary graph search over those states. Breadth-first search from the start finds the fewest moves when every move costs the same, and it reaches each state once. 0-1 BFS finds the cheapest route when moves cost either 0 or 1, with a double-ended queue in place of a heap. In every case, the number of states decides the cost. Below is a problem of this kind, the fewest knight moves, with its brute force and the signal to notice.

The problem: the fewest knight moves between two squares

1. n = 8, from (0, 0) to (7, 7): 6 moves, corner to corner.
2. n = 8, from (0, 0) to (1, 1): 4 moves. Two would do on an unbounded board, but both such routes leave this one.
3. n = 3, from (0, 0) to (1, 1): −1, because no move ever lands on the centre of a 3 × 3 board.

The brute force: try every sequence of moves

Try every sequence of one move, then of two, and so on, until one ends on the target. That is right, but it never remembers a square, so it reaches the same squares again and again by different sequences:

# The brute force: try every sequence of knight moves, shortest sequences first (iterative deepening), and count the
# sequences it tries. It keeps no record of squares already reached, so it explores the same squares again and again.

MOVES = [(1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1), (-2, 1), (-1, 2)]


def fewest_by_trying(n, start, target):
    """Fewest moves, or -1; also the number of move sequences tried."""
    tried = 0

    def reaches(square, moves_left):
        nonlocal tried
        tried += 1
        if square == target:
            return True
        if moves_left == 0:
            return False
        r, c = square
        return any(reaches((r + dr, c + dc), moves_left - 1)
                   for dr, dc in MOVES if 0 <= r + dr < n and 0 <= c + dc < n)

    for limit in range(n * n):              # a shortest route never repeats a square: at most n*n - 1 moves
        if reaches(start, limit):
            return limit, tried
    return -1, tried


import math

for n, start, target in [(8, (0, 0), (7, 7)), (8, (0, 0), (1, 1)), (3, (0, 0), (1, 1))]:
    moves, tried = fewest_by_trying(n, start, target)
    print(f"n = {n}, {start} -> {target}: answer {moves} after {tried:,} move sequences")
counts = []
for k in (3, 6, 9, 11):
    moves, tried = fewest_by_trying(16, (0, 0), (k, k))
    counts.append(tried)
    print(f"n = 16, (0, 0) -> {(k, k)}: {moves} moves after {tried:,} move sequences")
rate = (counts[-1] / counts[-2]) ** 0.5         # the last two targets are 2 moves apart
print(f"each extra move multiplies the sequences by about {rate:.1f}")
print(f"n = 1,000, corner to corner, 666 moves: about 10^{round(666 * math.log10(rate))} sequences")

n = 8, (0, 0) -> (7, 7): answer 6 after 3,427 move sequences
n = 8, (0, 0) -> (1, 1): answer 4 after 133 move sequences
n = 3, (0, 0) -> (1, 1): answer -1 after 1,013 move sequences
n = 16, (0, 0) -> (3, 3): 2 moves after 8 move sequences
n = 16, (0, 0) -> (6, 6): 4 moves after 113 move sequences
n = 16, (0, 0) -> (9, 9): 6 moves after 3,870 move sequences
n = 16, (0, 0) -> (11, 11): 8 moves after 174,991 move sequences
each extra move multiplies the sequences by about 6.7
n = 1,000, corner to corner, 666 moves: about 10^551 sequences

Each extra move multiplies the work by about 6.7, so 8 moves already cost 174,991 sequences, and the 666 moves from corner to corner of a 1,000 × 1,000 board would need about 10⁵⁵¹. An answer of −1 is worse: the search must try every sequence of up to n² − 1 moves before it can give up.

What to notice

The future of the knight depends only on its square, never on the route that brought it there. So each square is a state: a vertex of a graph with at most n² = 10⁶ vertices and 8 edges each, made on the fly. Implicit graphs of this size are small for a search that reaches every state at most once. Every move costs one and the question asks for the fewest moves, which is exactly what breadth-first search answers. This is state-space search in its simplest form, with a square as the whole state. Bidirectional BFS runs one search from the start and one from the target and stops where they meet. If some moves cost nothing and others cost one, 0-1 BFS keeps the same linear cost.

BFS over the squares, step by step Pro: opens with a Pro, Premium or Ultimate pass