Practical 1: Breadth First Search and Iterative Deepening Depth First Search

step expanded   frontier after expanding
1    Gate       Reception Canteen
2    Reception  Canteen Office Library
3    Canteen    Office Library Ground
4    Office     Library Ground Hall
5    Library    Ground Hall Lab1
6    Ground     Hall Lab1
7    Hall       Lab1 Lab2
8    Lab1       Lab2
9    Lab2       GOAL

path found : Gate -> Reception -> Office -> Hall -> Lab2
edges      : 4

Follow that table once and BFS is yours for life. deque is a double-ended queue: append puts a state on the right, popleft takes one off the left, so the oldest state is always the one expanded. That one line, popleft instead of pop, is the whole difference between breadth first and depth first.

Three things in the output are worth saying in the journal.

The frontier is a queue. Look at step 2: Canteen was found at step 1 and Office and Library at step 2, and Canteen is expanded first.

parent does two jobs. It is the reached set, because if nxt not in parent is the test that stops a state being added twice, and it is also how the path is recovered afterwards, by walking backwards from the goal.

BFS found a shortest path, not the only one. Gate to Reception to Library to Lab1 to Lab2 is also four edges. BFS returned the Office route because Office was put into the frontier before Library, which is the order they appear in Reception's list. Both answers are correct and a marker who insists on one of them is wrong. What BFS guarantees is the number of edges, not which of the equally short paths you get.

Part 2: the problem both algorithms will solve

The 8-puzzle: eight numbered tiles in a three by three frame with one blank, and the blank can swap with any tile next to it. The goal is the tiles in order with the blank at the bottom right.

A state is nine numbers in a row, reading the frame left to right and top to bottom, with 0 for the blank. So this frame

1 7 4
2 . 3
8 6 5

is the tuple (1, 7, 4, 2, 0, 3, 8, 6, 5). A tuple, not a list, because a state has to go into a set and a list cannot.

The solvability test, which has to come first

Half of all the arrangements of an 8-puzzle cannot be reached from the goal at all, and a student who types a scrambled frame in at random has an even chance of setting a puzzle with no solution. BFS will then search every reachable state and report failure, and IDDFS will run for ever, because it has no reason to stop.

The test is the inversion count. Write out the eight tiles in the order they appear, ignoring the blank, and count the pairs that are in the wrong order relative to each other. For our goal, with the blank in the corner, the puzzle is solvable when that count is even.

from collections import deque
GOAL = (1, 2, 3, 4, 5, 6, 7, 8, 0)

def inversions(state):
    tiles = [v for v in state if v != 0]
    return sum(1 for i in range(len(tiles))
               for j in range(i + 1, len(tiles)) if tiles[i] > tiles[j])

def moves(state):
    i = state.index(0)
    row, col = divmod(i, 3)
    for dr, dc, name in ((-1, 0, "up"), (1, 0, "down"), (0, -1, "left"), (0, 1, "right")):
        r, c = row + dr, col + dc
        if 0 <= r < 3 and 0 <= c < 3:
            j = r * 3 + c
            nxt = list(state)
            nxt[i], nxt[j] = nxt[j], nxt[i]
            yield name, tuple(nxt)

def bfs(start):
    if start == GOAL:
        return [], 1
    frontier = deque([(start, [])])
    reached = {start}
    while frontier:
        state, path = frontier.popleft()
        for move, child in moves(state):
            if child in reached:
                continue
            if child == GOAL:
                return path + [move], len(reached) + 1
            reached.add(child)
            frontier.append((child, path + [move]))
    return None, len(reached)

print("%-24s %11s %10s %10s" % ("state", "inversions", "solvable", "BFS visited"))
for name, s in [("1 7 4 / 2 . 3 / 8 6 5", (1, 7, 4, 2, 0, 3, 8, 6, 5)),
                ("2 1 3 / 4 5 6 / 7 8 .", (2, 1, 3, 4, 5, 6, 7, 8, 0)),
                ("1 2 3 / 4 5 6 / 8 7 .", (1, 2, 3, 4, 5, 6, 8, 7, 0))]:
    inv = inversions(s)
    path, visited = bfs(s)
    print("%-24s %11d %10s %10d"
          % (name, inv, "yes" if inv % 2 == 0 else "no", visited))

state                     inversions   solvable BFS visited
1 7 4 / 2 . 3 / 8 6 5             10        yes      22187
2 1 3 / 4 5 6 / 7 8 .              1         no     181440
1 2 3 / 4 5 6 / 8 7 .              1         no     181440

Read the last two rows. Those two frames look almost solved: one of them has only the 7 and the 8 swapped. Both are impossible, and BFS proved it by visiting 181,440 states, which is every state reachable from either of them, and finding no goal. That number is 9! divided by 2, which is exactly the point: the 362,880 arrangements of nine symbols split into two halves, and no sequence of slides ever crosses between them.

So: count inversions before you search. One line saves a student in an examination hall from watching a program search for two minutes and print nothing.

Part 3: both algorithms, on the same puzzle

"""Practical 1: BFS and IDDFS on the 8-puzzle."""
from collections import deque

GOAL = (1, 2, 3, 4, 5, 6, 7, 8, 0)
START = (1, 7, 4, 2, 0, 3, 8, 6, 5)

def show(state):
    for r in range(3):
        row = state[r * 3:r * 3 + 3]
        print("   " + " ".join("." if v == 0 else str(v) for v in row))

def solvable(state):
    tiles = [v for v in state if v != 0]
    inv = sum(1 for i in range(len(tiles))
              for j in range(i + 1, len(tiles)) if tiles[i] > tiles[j])
    return inv % 2 == 0, inv

def moves(state):
    i = state.index(0)
    row, col = divmod(i, 3)
    for dr, dc, name in ((-1, 0, "up"), (1, 0, "down"),
                         (0, -1, "left"), (0, 1, "right")):
        r, c = row + dr, col + dc
        if 0 <= r < 3 and 0 <= c < 3:
            j = r * 3 + c
            nxt = list(state)
            nxt[i], nxt[j] = nxt[j], nxt[i]
            yield name, tuple(nxt)

def bfs(start):
    """Breadth first: expand the OLDEST state in the frontier."""
    if start == GOAL:
        return [], 1, 1
    frontier = deque([(start, [])])
    reached = {start}
    generated = 1
    while frontier:
        state, path = frontier.popleft()
        for move, child in moves(state):
            generated += 1
            if child in reached:
                continue
            if child == GOAL:
                return path + [move], generated, len(reached) + 1
            reached.add(child)
            frontier.append((child, path + [move]))
    return None, generated, len(reached)

def depth_limited(state, limit, path, on_path, counter):
    """Depth first, but refusing to go deeper than `limit` moves."""
    if state == GOAL:
        return list(path)
    if limit == 0:
        return None
    for move, child in moves(state):
        counter[0] += 1
        if child in on_path:
            continue
        on_path.add(child)
        path.append(move)
        found = depth_limited(child, limit - 1, path, on_path, counter)
        path.pop()
        on_path.discard(child)
        if found is not None:
            return found
    return None

def iddfs(start, max_depth=30):
    """Depth-limited search again and again, with the limit going up by one."""
    counter = [1]
    for limit in range(max_depth + 1):
        found = depth_limited(start, limit, [], {start}, counter)
        if found is not None:
            return found, counter[0], limit + 1, limit
    return None, counter[0], None, None

print("start")
show(START)
print("goal")
show(GOAL)
ok, inv = solvable(START)
print()
print("inversions :", inv, "  solvable :", ok)
print()

bfs_path, bfs_gen, bfs_mem = bfs(START)
print("BFS    moves %d  generated %d  states held %d" % (len(bfs_path), bfs_gen, bfs_mem))
id_path, id_gen, id_mem, id_limit = iddfs(START)
print("IDDFS  moves %d  generated %d  states held %d  (found at limit %d)"
      % (len(id_path), id_gen, id_mem, id_limit))
print()
print("BFS   :", " ".join(bfs_path))
print("IDDFS :", " ".join(id_path))

start
   1 7 4
   2 . 3
   8 6 5
goal
   1 2 3
   4 5 6
   7 8 .

inversions : 10   solvable : True

BFS    moves 18  generated 40254  states held 22187
IDDFS  moves 18  generated 205881  states held 19  (found at limit 18)

BFS   : up left down right up right down down left left up right up left down right right down
IDDFS : up left down right up right down down left left up right up left down right right down

Each move names the direction the blank moves. "up" means the blank swaps with the tile above it, which is the same as sliding that tile down. Say which convention you used, in the journal: the marker cannot read your mind and the other convention gives the mirror answer.

Both algorithms found an 18-move solution, and here they found the same one, because both try the moves in the same order and both stop at the first 18-move answer they meet. That is a coincidence of this implementation, not a guarantee.

Two details in depth_limited are what make it work and are worth a line each in the journal.

on_path, not a global reached set. Depth-limited search must not refuse a state just because some earlier branch saw it, because that other branch may have been deeper. It must only refuse a state that is already on the path it is standing on, which is what stops it going round in circles. That is why the set is added to before the recursive call and removed after it.

counter is a list. A plain integer cannot be changed by a function it is passed to. A one-element list can, and that is the simplest way to count nodes across a recursion.

Part 4: the comparison MU asks for

One puzzle proves nothing about the trade-off, because the whole difference is in how the two grow. So run both on five puzzles whose answers are 2, 8, 12, 16 and 18 moves deep.

from collections import deque
GOAL = (1, 2, 3, 4, 5, 6, 7, 8, 0)

def moves(state):
    i = state.index(0)
    row, col = divmod(i, 3)
    for dr, dc, name in ((-1, 0, "up"), (1, 0, "down"), (0, -1, "left"), (0, 1, "right")):
        r, c = row + dr, col + dc
        if 0 <= r < 3 and 0 <= c < 3:
            j = r * 3 + c
            nxt = list(state)
            nxt[i], nxt[j] = nxt[j], nxt[i]
            yield name, tuple(nxt)

def bfs(start):
    if start == GOAL:
        return [], 1, 1
    frontier = deque([(start, [])])
    reached = {start}
    generated = 1
    while frontier:
        state, path = frontier.popleft()
        for move, child in moves(state):
            generated += 1
            if child in reached:
                continue
            if child == GOAL:
                return path + [move], generated, len(reached) + 1
            reached.add(child)
            frontier.append((child, path + [move]))
    return None, generated, len(reached)

def depth_limited(state, limit, path, on_path, counter):
    if state == GOAL:
        return list(path)
    if limit == 0:
        return None
    for move, child in moves(state):
        counter[0] += 1
        if child in on_path:
            continue
        on_path.add(child)
        path.append(move)
        found = depth_limited(child, limit - 1, path, on_path, counter)
        path.pop()
        on_path.discard(child)
        if found is not None:
            return found
    return None

def iddfs(start, max_depth=30):
    counter = [1]
    for limit in range(max_depth + 1):
        found = depth_limited(start, limit, [], {start}, counter)
        if found is not None:
            return found, counter[0], limit + 1
    return None, counter[0], None

PUZZLES = [
    (1, 2, 3, 4, 5, 6, 0, 7, 8),
    (1, 3, 0, 4, 2, 8, 7, 6, 5),
    (1, 3, 7, 5, 2, 6, 4, 8, 0),
    (1, 5, 6, 7, 3, 4, 8, 2, 0),
    (1, 7, 4, 2, 0, 3, 8, 6, 5),
]
print("%6s %10s %10s %10s %10s %8s"
      % ("moves", "BFS gen", "BFS held", "IDS gen", "IDS held", "IDS/BFS"))
for start in PUZZLES:
    bp, bg, bm = bfs(start)
    ip, ig, im = iddfs(start)
    print("%6d %10d %10d %10d %10d %8.1f"
          % (len(bp), bg, bm, ig, im, ig / bg))

 moves    BFS gen   BFS held    IDS gen   IDS held  IDS/BFS
     2          9          7         11          3      1.2
     8        362        226        816          9      2.3
    12       2009       1180       5826         13      2.9
    16      12882       7394      50262         17      3.9
    18      40254      22187     205881         19      5.1

That table is the whole practical, and it says four things.

Both find the same number of moves, every time. Both are optimal on this problem, because every move costs one. BFS is optimal because it finishes a level before starting the next; IDDFS is optimal because it tries depth d only after depth d minus 1 has failed.

BFS memory explodes. From 7 states to 22,187 as the answer goes from 2 moves to 18. Multiply the frame by one row and one column, making a 15-puzzle, and this column runs out of the machine's memory long before it finds an answer. That is the real limit of BFS, and it is memory and not time.

IDDFS memory is the depth, plus one. Look at the column: 3, 9, 13, 17, 19, against answers of 2, 8, 12, 16 and 18 moves. It holds one path and nothing else. A 15-puzzle needs 80 states at worst, not millions.

IDDFS pays for that in repeated work, and the bill is small. It generated 5.1 times as many nodes as BFS on the deepest puzzle. It sounds worse than it is: the work at each depth is dominated by the deepest level, because each level of this tree is roughly twice the one above it, so re-searching every shallower level costs about as much again as the deepest one. The ratio grows slowly, from 1.2 to 5.1, and it buys a memory saving of 22,187 states down to 19.

The honest summary, and the one to write in the journal: IDDFS is the one to use when memory is the constraint and the cost of a repeated visit is low, which on this problem it is. BFS is the one to use when you can afford to hold a level and want the goal found in one pass.

Note on the times

Node counts are in the table and times are not, on purpose. The counts are the same on every machine, and the times are not: they depend on the processor, the version of Python and what else is running. If your write-up quotes seconds, quote the machine as well, and never rank two algorithms on a difference of a few hundredths of a second.

Procedure

1. Write the campus graph as a dictionary and run BFS on it, printing the frontier after every expansion. Check the path by hand on the map.
2. Write the 8-puzzle state as a tuple of nine numbers with 0 for the blank, and write moves to generate the legal successors.
3. Count the inversions of your start state and confirm it is even before searching. Try a state with an odd count and watch BFS visit 181,440 states and fail.
4. Implement BFS with a deque, a reached set and a path, counting nodes generated and states held.
5. Implement depth-limited search recursively with an on-path set, then IDDFS as a loop over the limit.
6. Run both on the same start state and confirm both return the same number of moves.
7. Run both on five start states of growing depth and print the comparison table.
8. Record which algorithm used more memory, which generated more nodes, and by what factor.

Observations

Result

Breadth First Search and Iterative Deepening Depth First Search were implemented and run on the same 8-puzzle. Both returned an optimal 18-move solution. BFS generated 40,254 nodes and held 22,187 states at once; IDDFS generated 205,881 nodes, 5.1 times as many, and held 19. Over five puzzles of depths 2 to 18 the same pattern held: BFS memory grew exponentially with depth while IDDFS memory grew by one state per level, and IDDFS's extra work grew only from 1.2 to 5.1 times BFS's. The inversion test identified two unsolvable frames on which BFS had to visit all 181,440 reachable states to report failure.

Where marks are lost

Searching an unsolvable puzzle. Count inversions first. An odd count on this goal means there is no solution, and no algorithm will find one.

Using pop() instead of popleft(). That is depth first search, wearing BFS's name. The program still runs, still prints a path, and the path is not shortest.

Using one global reached set in depth-limited search. It makes the search incomplete: a state first met at depth 6 is refused at depth 2, where it might have been on the answer. Use an on-path set.

A state kept as a list. A list cannot go into a set and cannot be a dictionary key. Tuples.

Not counting anything. MU's third line is "compare the performance and efficiency of both algorithms". Without nodes generated and states held there is nothing to compare, and that is a third of the exercise.

Comparing on one puzzle. The whole difference is in how the two grow. One puzzle cannot show growth.

Forgetting that IDDFS never terminates on an unsolvable puzzle unless you give it a maximum depth. max_depth=30 is in the program above because the deepest 8-puzzle is 31 moves.

Saying the moves without saying the convention. Name whether a move is the blank's direction or the tile's.

For the journal

Aim; the five parts of a search problem named for the 8-puzzle; the campus graph and the step-by-step BFS table, with the path checked by hand; the state representation and the moves function; the inversion test with the three-row table showing the two unsolvable frames and the 181,440 states; the full program with BFS, depth-limited search and IDDFS; its output showing 18 moves from both; the five-puzzle comparison table; the observation tables above; the result; one sentence on which algorithm you would choose and why.

Quick revision

• BFS expands the oldest state in the frontier, so the frontier is a queue: deque with popleft.
• BFS is optimal when every step costs the same, and it holds a whole level in memory.
• IDDFS is depth-limited search run again and again with the limit rising by one.
• IDDFS holds one path: memory is the depth plus one.
• IDDFS is optimal for the same reason, and complete, and its repeated work cost 5.1 times BFS's on an 18-move puzzle.
• Depth-limited search uses an ON-PATH set, not a global reached set.
• A state must be hashable: use a tuple.
• The 8-puzzle inversion count must be even for our goal. 9! / 2 = 181,440 states are reachable.
• Report nodes generated and states held. Those are the same on every machine; seconds are not.
• Use BFS when memory is cheap and you want one pass. Use IDDFS when memory is the constraint.

Questions you must be able to answer

1. What is the one line that makes your program breadth first rather than depth first? frontier.popleft(). Taking the oldest state out of the frontier makes it a queue and searches level by level. pop() takes the newest and makes it depth first.

2. Why is BFS optimal here, and when would it not be? Because every move costs one, so the first time the goal is reached it is by a fewest-moves path. If moves had different costs, BFS would no longer be optimal and uniform cost search would be needed.

3. Iterative deepening throws away all its work after every round. Why is it not hopeless? Because almost all the work is at the deepest level. Each level of this tree is roughly twice the size of the one above it, so re-searching every shallower level costs about as much again as searching the deepest one once. Measured here, the total was 5.1 times BFS's work, for a memory saving of 22,187 states to 19.

4. How much memory does each algorithm use on the 18-move puzzle? BFS held 22,187 states at once. IDDFS held 19, which is the depth plus one.

5. Why must depth-limited search use an on-path set rather than a global visited set? Because a state rejected for having been seen somewhere else may lie on the answer through this path at a shallower depth. Rejecting it makes the search incomplete. Only a state already on the current path is a genuine cycle.

6. How do you know an 8-puzzle is solvable before you search? Count the inversions among the eight tiles, ignoring the blank. For a goal with the blank in the corner and the tiles in order, an even count is solvable and an odd count is not.

7. How many states can be reached from a solvable 8-puzzle position, and why is it not 9 factorial? 181,440, which is 9! divided by 2. A slide changes the inversion parity and the blank's row together in a way that keeps one quantity fixed, so the arrangements split into two halves and no slide crosses between them.

8. Your program returns a path of 18 moves and your neighbour's returns a different path of 18 moves. Who is right? Both. BFS guarantees the number of moves, not which of the equally short paths comes out, and that depends on the order the successors are generated in.

9. What happens if you run IDDFS on an unsolvable puzzle with no maximum depth? It never stops. It keeps raising the limit and searching for ever. Cap the limit, at 31 for the 8-puzzle, and report failure.

10. Your counter is an integer and it stays at zero. Why? Because an integer passed to a function cannot be changed by it. Use a one-element list, or a class, or return the count.