The Knight's Tour and Maze Problems

In n-queens, the search space could be read directly off the board: one queen per row, n choices per queen. The size of the space followed from the problem’s definition, with nothing to argue about. This lesson removes that comfort. The knight’s tour and the maze are both defined on the same grid, but what decides what object gets scanned is not the problem but the model, and the gap between two models can reach a factor of thousands.

The maze problem is this: get from a grid’s top-left cell to its bottom-right cell, moving between adjacent cells. The knight’s tour problem is this: starting from a knight on a five-by-five board, visit every square exactly once. Both are search problems, and in both the first question to ask is not “which algorithm” but “what is being searched for.”

• CP40. Two models are compared for the maze. In the first model, the candidate solution is a path; what is scanned is every simple path from top-left to bottom-right. In the second model, the candidate solution is a cell; every cell is opened at most once.
• CP41. The second model is breadth-first search, built in the Data Structures course’s Graphs topic. The procedure is not rebuilt; it is used directly.
• CP42. The oracle is the first model: it scans every simple path and finds the shortest. The length the second model gives is compared against this.
• CP43. The grid has no obstacles. Adding obstacles changes the path count but does not change the ratio between the two models; what is measured is the ratio’s order of magnitude. This lesson’s input does not come from the generator either: grid size and board size are the only inputs, and every number is exhaustive enumeration. The second-pool rule is replaced by a size sweep, and no value depends on a seed.
• CP44. The measure is steps. In the first model, a step is a partial-path node; in the second, a cell being opened.
• CP45. In the knight’s tour, two orderings are compared: trying squares in natural order, and trying the square that leaves the fewest options first. The second ordering is not pruning; no branch is cut, only the order of trials changes.
• CP46. The second ordering is a heuristic, and its correctness is not assumed. Every tour it finds is verified against the oracle: was every square visited once, is every step a legal knight move.
• CP47. Four starting squares are measured on the five-by-five board. Measuring every square would require scanning the entire search space on squares where no tour exists, and would exceed the run budget.
• CP48. The no-tour case is measured on a four-by-four board; there, no square has a tour, and the entire search space can be scanned.
• CP49. The limit of the cheap model is tested by changing the question. The same count yields both the shortest path and the count of paths visiting every cell; a model’s adequacy is never written independently of the question.

The Same Grid, Two Models

The first model sets up the question like this: generate every path from top-left to bottom-right, pick the shortest. The second sets it up like this: starting from top-left, open cells in order of distance, and stop at the first arrival at bottom-right. Both give the correct answer; what is measured is what it costs.

from collections import deque


class Counter:
    def __init__(self):
        self.steps = 0

    def count(self):
        self.steps += 1


def neighbors(h, r, c):
    for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        i, j = h[0] + dr, h[1] + dc
        if 0 <= i < r and 0 <= j < c:
            yield (i, j)


def oracle_all_paths(r, c, s):
    """Model 1: the candidate solution is a PATH. Every simple path is scanned."""
    target, count, shortest = (r - 1, c - 1), 0, None

    def walk(h, seen):
        nonlocal count, shortest
        s.count()
        if h == target:
            count += 1
            if shortest is None or len(seen) < shortest:
                shortest = len(seen)
            return
        for k in neighbors(h, r, c):
            if k not in seen:
                walk(k, seen | {k})
    walk((0, 0), {(0, 0)})
    return count, shortest


def pattern_bfs(r, c, s):
    """Model 2: the candidate solution is a CELL. Every cell is opened at most once."""
    target = (r - 1, c - 1)
    queue, seen = deque([((0, 0), 1)]), {(0, 0)}
    while queue:
        h, u = queue.popleft()
        s.count()
        if h == target:
            return u
        for k in neighbors(h, r, c):
            if k not in seen:
                seen.add(k)
                queue.append((k, u + 1))
    return None


print(" grid | simple path count | oracle steps | bfs steps | ratio | shortest")
for n in (3, 4, 5):
    s1, s2 = Counter(), Counter()
    count, shortest = oracle_all_paths(n, n, s1)
    u = pattern_bfs(n, n, s2)
    print(f" {n}x{n:2d} | {count:16d} | {s1.steps:10d} | {s2.steps:10d} |"
          f" {s1.steps // s2.steps:5d} | {shortest} and {u}")

 grid | simple path count | oracle steps | bfs steps | ratio | shortest
 3x 3 |               12 |         51 |          9 |     5 | 5 and 5
 4x 4 |              184 |       1271 |         16 |    79 | 7 and 7
 5x 5 |             8512 |      90111 |         25 |  3604 | 9 and 9

What Determines the Space Is the Model

The last column shows the two models give the same answer: shortest length is the same on all three grids, split count 0. The second model is not an approximate solution; it is a solution that agrees exactly with the oracle.

But their costs are not the same. On the five-by-five grid, the first model spends 90,111 steps to produce 8512 simple paths; the second spends 25 steps, one per cell. The ratio is 3604. On the three-by-three grid the ratio is 5, on four-by-four it is 79, on five-by-five it is 3604. The ratio widens rapidly as the grid grows.

The source of the difference is not the algorithm but the object being counted. In the first model, the candidate is a path, and the path count grows exponentially with cell count. In the second model, the candidate is a cell, and the cell count equals the grid’s area. The second model finds the shortest of the 8512 paths the first model produces without producing them, because it uses the fact that arriving at the same cell by different paths does not change what comes after.

This gives a sentence that ties back to the course’s reading of measurement: the size of the search space is a property of the model, not the problem. Saying “the search space is too large” for a problem carries meaning only once it is said which model is meant. The same maze has 8512 candidates in one model and 25 in another.

The Question the Cheap Model Cannot Answer

The cheap model has a cost, and it has not shown up yet. Breadth-first search used the fact that arriving at the same cell by different paths does not change what comes after. This assumption is true for the shortest-path question, but it is not true for every question. The block below performs the same count and sorts the paths by their length.

from collections import Counter as Tally


class Counter:
    def __init__(self):
        self.steps = 0

    def count(self):
        self.steps += 1


def paths(n, s):
    """Every simple path; tallied by length."""
    target, tally = (n - 1, n - 1), Tally()

    def walk(h, seen):
        s.count()
        if h == target:
            tally[len(seen)] += 1
            return
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            k = (h[0] + dr, h[1] + dc)
            if 0 <= k[0] < n and 0 <= k[1] < n and k not in seen:
                walk(k, seen | {k})
    walk((0, 0), {(0, 0)})
    return tally


for n in (4, 5):
    s = Counter()
    tally = paths(n, s)
    full = tally[n * n]
    print(f"{n}x{n} | paths {sum(tally.values()):5d} | steps {s.steps:6d}"
          f" | shortest {min(tally)} long, {tally[min(tally)]:3d} paths"
          f" | visiting every cell {full:3d} paths")
    print("      by length:", dict(sorted(tally.items())))

4x4 | paths   184 | steps   1271 | shortest 7 long,  20 paths | visiting every cell   0 paths
      by length: {7: 20, 9: 36, 11: 48, 13: 48, 15: 32}
5x5 | paths  8512 | steps  90111 | shortest 9 long,  70 paths | visiting every cell 104 paths
      by length: {9: 70, 11: 224, 13: 510, 15: 956, 17: 1586, 19: 2224, 21: 2106, 23: 732, 25: 104}

On the five-by-five grid, 70 of the 8512 paths are of the shortest length, and 104 pass through all 25 cells. Breadth-first search gives the first number in 25 steps. It can say nothing about the second: since it keeps only a single value per cell, it forgets which cells were used to arrive at a cell, and the question “is there a path that visits every cell” asks for exactly that information. Once the question changes, the 25-step model falls away, leaving only the 90,111-step count.

The four-by-four row shows the same question’s no answer: none of the 184 paths pass through all 16 cells, the longest reaching 15. This no answer also cannot be obtained without spending all 1271 steps. Seeing one question of the search become cheap while the other does not is proof that the model is chosen together with the question.

What Ordering Contributes in the Knight’s Tour

In the knight’s tour, the second model cannot be built directly. Which path arrives at a square matters, because which squares have been used determines what comes next. The candidate is not a cell but a partial tour, and the search space is exponential. The only tool left is the order in which branches are tried.

The intuition is this: if the square with the fewest options is not visited early, it can become unreachable later, and the search wanders in vain. The block below compares this ordering against natural order and verifies every tour found against the oracle.

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


class Counter:
    def __init__(self):
        self.steps = 0

    def count(self):
        self.steps += 1


def candidates(h, visited, n):
    r, c = h
    return [(r + a, c + b) for a, b in MOVES
            if 0 <= r + a < n and 0 <= c + b < n and (r + a, c + b) not in visited]


def tour(start, n, ordered, s):
    """Halts at the first complete tour. ordered=True: least-option square first."""
    def walk(h, visited):
        s.count()
        if len(visited) == n * n:
            return [h]
        options = candidates(h, visited, n)
        if ordered:
            options.sort(key=lambda k: len(candidates(k, visited | {k}, n)))
        for k in options:
            y = walk(k, visited | {k})
            if y:
                return [h] + y
        return None
    return walk(start, {start})


def verify(path, n):
    """Oracle: is every square visited once, is every step a legal knight move."""
    if path is None or len(set(path)) != n * n:
        return False
    return all((abs(a[0] - b[0]), abs(a[1] - b[1])) in ((1, 2), (2, 1))
               for a, b in zip(path, path[1:]))


print("5x5 | start | natural order nodes | least-option nodes | verified tour")
for start in ((0, 0), (0, 2), (2, 2), (4, 0)):
    s1, s2 = Counter(), Counter()
    y1, y2 = tour(start, 5, False, s1), tour(start, 5, True, s2)
    print(f"    | {str(start):9s} | {s1.steps:16d} | {s2.steps:19d} |"
          f" {verify(y1, 5)} and {verify(y2, 5)}")
t1 = t2 = found = 0
for i in range(4):
    for j in range(4):
        s1, s2 = Counter(), Counter()
        y1, y2 = tour((i, j), 4, False, s1), tour((i, j), 4, True, s2)
        t1, t2 = t1 + s1.steps, t2 + s2.steps
        found += 1 if verify(y1, 4) else 0
print(f"4x4 | 16 squares | {t1:16d} | {t2:19d} | tours found {found}")

5x5 | start | natural order nodes | least-option nodes | verified tour
    | (0, 0)    |            70716 |                  25 | True and True
    | (0, 2)    |           101718 |                  25 | True and True
    | (2, 2)    |            25542 |                  25 | True and True
    | (4, 0)    |              182 |                  25 | True and True
4x4 | 16 squares |            29976 |               29976 | tours found 0

Cheap on Yes, Not on No

On the five-by-five board, the least-option order finds the tour in 25 nodes on all four starting squares. Twenty-five is the number of squares on the board: the search never backtracks, choosing the right move on the first try at every square. Natural order finds the same tours between 182 and 101,718 nodes. Because the starting squares differ, the rows must be compared within themselves, not against each other; the ratio in each row ranges from at least 7 to as much as 4068.

The verification column is True on every one of these rows. The tours the heuristic finds are genuinely tours: all twenty-five squares are visited once, and every step is a legal knight move. It is not enough to say the heuristic speeds things up — it also does not go wrong, and this has been measured separately.

The last row is the lesson’s harshest number. On the four-by-four board, no square has a tour. Both orderings visit exactly 29,976 nodes to find this out. The numbers are equal, the difference zero. The move-ordering heuristic buys nothing here, because what it bought was finding the right branch early; when there is no right branch, every branch is tried, and the order of trying does not change the total.

This is the measured form of the difference between move-ordering heuristics and pruning. Pruning removes pieces from the search space, so it pays off whether the answer is yes or no. Ordering removes nothing from the space; it only changes the direction of traversal, so it pays off only on a yes answer. A heuristic’s number cannot be read without saying which answer it was measured on.

Summary

• The same maze produces two different search spaces in two models: with the candidate solution counted as a path, 8512 candidates and 90,111 steps on the five-by-five grid; counted as a cell, 25 steps; a ratio of 3604.
• The two models give the same shortest length on all three grids; split count 0, meaning the cheap model is an exact solution, not an approximation.
• The size of the search space is a property of the model, not the problem; the sentence “the space is too large” carries no meaning without saying which model is meant.
• The cheap model’s limit is set by the question: 104 of the 8512 paths visit every cell, but breadth-first search cannot give this number, and once the question changes, it returns to the 90,111-step count.
• In the knight’s tour, trying the square with the fewest options first finds the tour in 25 nodes on all four starting squares of the five-by-five board; natural order ranges between 182 and 101,718 nodes.
• On the four-by-four board there is no tour, and both orderings visit 29,976 nodes: the move-ordering heuristic buys nothing on a no answer, because it removes nothing from the space.

Next Step

This lesson’s last row opened a distinction: a search’s yes answer and its no answer do not cost the same. The next lesson makes this distinction the topic’s central question. The Hamiltonian path problem is an existence question and is framed as a decision problem; what will be measured is the step gap between deciding, finding the path, and verifying a given path. Class names will again be left to Theory of Computation, but the gap will be counted here.