Don't Get Volunteered!

Created: Dec 16, 2021

Last modified: Jul 07, 2025

TL, DR.

Show challenge description

Picture an 8×8 chessboard with its squares numbered from 0 to 63. You're the knight, you start on one square, and you need to reach another one. The question is simple: what's the smallest number of moves it takes to get there?

If you try to work it out in your head, you'll notice it gets tricky fast: the knight jumps around in that weird "L" shape, so sometimes a square right next to you is actually three moves away. Guessing won't cut it; we need a method.

# Think of the board as a map

Here's the trick: forget it's a chess game for a second. Every square is a node (a dot on a map), and two dots are connected if the knight can jump from one to the other in a single move. Now "fewest moves" just means "shortest route on this map".

And since every jump costs exactly the same (one move), there's a classic algorithm that nails this: Breadth-First Search, or BFS for short. The idea is like dropping a stone in a pond: first you visit every square you can reach in 1 move, then every square you can reach in 2, then 3... The first time you touch the target, you know you got there the shortest way possible.

# Watch it spread

From any square, the knight has (at most) eight possible jumps. In code, we can write them as small (dx, dy) offsets, that's the _neighbors list below. Next to it, you can see BFS in action: each number is how many moves it takes to reach that square from the knight.

Legend:
1 2 3 4 Already visited, with their distance
Next in line (the frontier)
Being explored right now

Go ahead, play with it! Drag the slider to move through the search step by step, or drag the knight somewhere else and watch how the "ripples" change. Notice how BFS always finishes every square at distance 1 before touching any at distance 2. That level-by-level order is exactly what guarantees the shortest path.

# From distances to an actual route

Knowing the distance is great, but it's even nicer to see the route. While BFS explores, it can also write down where it came from for each square. Once it reaches the target, you just follow those notes backwards and you get the path.

Try it below: drag the knight or the pawn anywhere on the board. The highlighted squares show one of the shortest routes (there's often more than one, and they're all equally good).

Right now, the knight needs at least 2 moves to reach the pawn.

# The code

Here's my solution. A quick tour so it's easier to follow:

import Queue

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


class Node:
    def __init__(self, position, came_from, size=8):
        self.position = position
        self.x = position[0]
        self.y = position[1]
        self.cameFrom = came_from
        self.size = size

    def __hash__(self):
        return hash(self.position)

    def neighbors(self):
        moves = []
        for i in range(len(_neighbors)):
            if 0 <= _neighbors[i][0] + self.x < self.size and \
                    0 <= _neighbors[i][1] + self.y < self.size:
                moves.append(Node(
                    (_neighbors[i][0] + self.x, _neighbors[i][1] + self.y),
                    (self.x, self.y), self.size)
                )
        return moves


def calc_distance(goal, start=(0, 0)):
    frontier = Queue.Queue()
    camefrom = dict()
    distance = dict()
    _start = Node(start, None)
    if frontier.empty():
        frontier.put(_start)
    camefrom[_start.position] = None
    distance[_start.position] = 0
    while not frontier.empty():
        current = frontier.get()
        if current.position == goal:
            break
        for n in current.neighbors():
            if n.position not in camefrom:
                frontier.put(n)
                camefrom[n.position] = current.position
                distance[n.position] = distance[n.cameFrom] + 1
    return {"cameFrom": camefrom, "distance": distance}


def solution(src, dest):
    _src = (src // 8, src % 8)
    _dest = (dest // 8, dest % 8)
    result = calc_distance(start=_src, goal=_dest)
    return result["distance"][_dest]

# Wrapping up

The big takeaway: whenever you need the fewest steps and every step costs the same, BFS is your friend. It works for knights, mazes, word puzzles, social networks... Once you learn to see a problem as a map of connected dots, a lot of "hard" puzzles suddenly become familiar.