Tracing the Queue Search

Let’s trace the queue search on this maze:

    0   1   2
  ┌───┬───┬───┐
0 │ S │   │   │
  ├───┼───┼───┤
1 │   │ █ │   │
  ├───┼───┼───┤
2 │   │   │ E │
  └───┴───┴───┘

The queue starts with the start cell:

    0   1   2             0   1   2
  ┌───┬───┬───┐         ┌───┬───┬───┐
0 │ S │   │   │       0 │ x │   │   │
  ├───┼───┼───┤         ├───┼───┼───┤
1 │   │ █ │   │       1 │   │   │   │
  ├───┼───┼───┤         ├───┼───┼───┤
2 │   │   │ E │       2 │   │   │   │
  └───┴───┴───┘         └───┴───┴───┘
      maze                 visited

┌────────┐
│ (0, 0) │
└────────┘
     ▲
front, back

We dequeue (0, 0) and enqueue its open neighbors, right then down. Those two cells, (0, 1) and (1, 0), are the cells one move from the start:

    0   1   2             0   1   2
  ┌───┬───┬───┐         ┌───┬───┬───┐
0 │[S]│   │   │       0 │ x │ x │   │
  ├───┼───┼───┤         ├───┼───┼───┤
1 │   │ █ │   │       1 │ x │   │   │
  ├───┼───┼───┤         ├───┼───┼───┤
2 │   │   │ E │       2 │   │   │   │
  └───┴───┴───┘         └───┴───┴───┘
      maze                 visited

┌────────┬────────┐
│ (0, 1) │ (1, 0) │
└────────┴────────┘
     ▲        ▲
   front    back

We dequeue (0, 1) from the front and enqueue its open, unvisited neighbor (0, 2). Notice that (0, 2) goes to the back, behind (1, 0). Even though we just discovered it, it will not be dequeued until (1, 0) has been:

    0   1   2             0   1   2
  ┌───┬───┬───┐         ┌───┬───┬───┐
0 │ S │[ ]│   │       0 │ x │ x │ x │
  ├───┼───┼───┤         ├───┼───┼───┤
1 │   │ █ │   │       1 │ x │   │   │
  ├───┼───┼───┤         ├───┼───┼───┤
2 │   │   │ E │       2 │   │   │   │
  └───┴───┴───┘         └───┴───┴───┘
      maze                 visited

┌────────┬────────┐
│ (1, 0) │ (0, 2) │
└────────┴────────┘
     ▲        ▲
   front    back

So next we dequeue (1, 0), the other cell one move out, and enqueue (2, 0):

    0   1   2             0   1   2
  ┌───┬───┬───┐         ┌───┬───┬───┐
0 │ S │   │   │       0 │ x │ x │ x │
  ├───┼───┼───┤         ├───┼───┼───┤
1 │[ ]│ █ │   │       1 │ x │   │   │
  ├───┼───┼───┤         ├───┼───┼───┤
2 │   │   │ E │       2 │ x │   │   │
  └───┴───┴───┘         └───┴───┴───┘
      maze                 visited

┌────────┬────────┐
│ (0, 2) │ (2, 0) │
└────────┴────────┘
     ▲        ▲
   front    back

This is the order we described in the previous section. Both cells one move from the start are now dequeued, and the queue holds exactly the two cells two moves out, (0, 2) and (2, 0). The search dequeued every cell one move out before it dequeued any cell two moves out.

The cells two moves out work the same way. We dequeue (0, 2) and enqueue (1, 2); then we dequeue (2, 0) and enqueue (2, 1). Now both cells two moves out are dequeued, and the queue holds the two cells three moves out:

    0   1   2             0   1   2
  ┌───┬───┬───┐         ┌───┬───┬───┐
0 │ S │   │   │       0 │ x │ x │ x │
  ├───┼───┼───┤         ├───┼───┼───┤
1 │   │ █ │   │       1 │ x │   │ x │
  ├───┼───┼───┤         ├───┼───┼───┤
2 │[ ]│   │ E │       2 │ x │ x │   │
  └───┴───┴───┘         └───┴───┴───┘
      maze                 visited

┌────────┬────────┐
│ (1, 2) │ (2, 1) │
└────────┴────────┘
     ▲        ▲
   front    back

We dequeue (1, 2) and enqueue the exit (2, 2). But the search does not stop here. It only checks for the exit when a cell is dequeued, and the exit is still at the back of the queue, behind (2, 1):

    0   1   2             0   1   2
  ┌───┬───┬───┐         ┌───┬───┬───┐
0 │ S │   │   │       0 │ x │ x │ x │
  ├───┼───┼───┤         ├───┼───┼───┤
1 │   │ █ │[ ]│       1 │ x │   │ x │
  ├───┼───┼───┤         ├───┼───┼───┤
2 │   │   │ E │       2 │ x │ x │ x │
  └───┴───┴───┘         └───┴───┴───┘
      maze                 visited

┌────────┬────────┐
│ (2, 1) │ (2, 2) │
└────────┴────────┘
     ▲        ▲
   front    back

So (2, 1) is dequeued first. It has no open, unvisited neighbor, so it enqueues nothing, and the queue now holds only the exit. We dequeue (2, 2), find it is the exit, and return true:

    0   1   2             0   1   2
  ┌───┬───┬───┐         ┌───┬───┬───┐
0 │ S │   │   │       0 │ x │ x │ x │
  ├───┼───┼───┤         ├───┼───┼───┤
1 │   │ █ │   │       1 │ x │   │ x │
  ├───┼───┼───┤         ├───┼───┼───┤
2 │   │   │[E]│       2 │ x │ x │ x │
  └───┴───┴───┘         └───┴───┴───┘
      maze                 visited

(empty — the exit was reached)