Problem Solving as Search
Learn how AI turns messy real-world problems into a crisp map of states and actions, then navigates that map to find a solution.
Imagine you're lost in a foreign city. No phone, no map, no shared language with the locals. What do you do? You start where you are, look at what streets are available, pick one, walk a bit, and check whether you've arrived somewhere recognizable. If not, you backtrack and try another street — repeating until you find your hotel.
Congratulations — you just ran a search algorithm. Whether the problem is a maze, a chess position, a GPS route, or scheduling deliveries, a huge portion of AI boils down to exactly this idea: explore possible situations until you find the one you want. This lesson unpacks that idea, names its parts, and builds a working implementation from scratch.
#The Four Ingredients of Any Search Problem
To turn any problem into a search problem, you need exactly four things:
- States — every distinct situation the world can be in. In a maze, a state is your current cell. In the 8-puzzle, a state is a tile arrangement. In route planning, a state is a city.
- Initial state — where you start.
- Goal test — a check that answers "did we make it?" It can be a single target state or a general condition (e.g., tiles in sorted order).
- Actions (transitions) — the moves available from any given state (move N/S/E/W, slide a tile, drive to an adjacent city).
Once you have these four pieces, every problem looks like a graph: nodes are states, edges are actions. Solving the problem means finding a path from the initial state to any state that passes the goal test.
The State Space is a Subway Map of Possibilities
Picture a giant subway map where every station is a possible situation the world can be in, and every rail line is an action that moves you from one situation to another.
You start at one station (the initial state) and want to reach a particular station (the goal). A search algorithm is simply a strategy for deciding which line to take next — without necessarily knowing the full map in advance.
#The Search Tree and the Frontier
When an AI explores a state space it grows a search tree on the fly. The root is the initial state. Each time the agent expands a node it generates child nodes — one for each available action — and those children join a waiting list called the frontier (or open list).
The algorithm picks a node from the frontier, checks whether it is the goal, and if not, expands it again. This continues until a goal is found or the frontier empties (no solution exists).
Different strategies for choosing the next node give completely different algorithms. Pick the oldest node (a queue) and you get Breadth-First Search. Pick the cheapest-cost node and you get Uniform-Cost Search. Add a distance estimate and you get A\*. Same skeleton — different choice.
Note that the state space (the full graph) exists regardless of exploration, while the search tree is what the algorithm actually builds. A state can appear on multiple tree branches via different paths — which is exactly why we need a visited set to avoid revisiting states and spiralling into infinite loops.
# A small state space: city -> list of reachable cities
graph = {
"A": ["B", "C"],
"B": ["A", "D", "E"],
"C": ["A", "F"],
"D": ["B"],
"E": ["B", "F"],
"F": ["C", "E"],
}
print("From B you can reach:", graph["B"])
print("From C you can reach:", graph["C"])#Breadth-First Search from Scratch
from collections import deque
def bfs(graph, start, goal):
frontier = deque([[start]]) # queue of paths
visited = set()
while frontier:
path = frontier.popleft() # oldest path first
node = path[-1] # current state
if node == goal:
return path
if node in visited:
continue
visited.add(node)
for neighbor in graph[node]:
frontier.append(path + [neighbor])
return None
result = bfs(graph, "A", "F")
print("Shortest path:", result)#Real-World Examples and the Bigger Picture
The search framework is surprisingly general:
- Maze navigation — states are grid cells, actions are move N/S/E/W, goal is the exit. BFS finds the route with fewest steps.
- 8-puzzle — states are tile arrangements (362,880 possible), actions are sliding a tile, goal is sorted order. Uninformed search struggles here; A\* shines.
- Route planning — states are road intersections, actions are driving a road segment, goal is the destination. Real GPS apps use A\* with straight-line distance as the heuristic.
The real power of this framework is that it separates problem definition from solution method. You describe your world — states, actions, start, goal — and swap in any search algorithm without touching the problem definition. Real libraries like Python's networkx or full AI toolkits build on exactly this abstraction.
Uninformed vs. Informed Search
BFS is uninformed (blind) — it has no clue which direction the goal lies. Informed search algorithms like A\ add a heuristic*: an estimate of how far the current state is from the goal. This lets the algorithm skip huge chunks of the state space and find solutions dramatically faster. That's the next big topic in this series.
In BFS, what data structure is used for the frontier, and what key property does this give the algorithm?
Don't Confuse the Search Tree with the State Space
The state space is the full graph of all possible states — it exists whether or not you explore it. The search tree is the record the algorithm builds as it runs, tracing every path attempted.
A single state can appear on many branches of the search tree (reached via different routes). This is why the visited set is non-negotiable: without it you'd re-expand the same state again and again, spiralling into an infinite loop. Modern systems — including game-playing AIs like AlphaGo — keep this exact distinction in mind, using learned heuristics to prune the frontier rather than blindly re-exploring.
Key takeaways
- Any problem becomes a search problem once you define states, an initial state, a goal test, and actions.
- The state space is the full graph of all situations; the search tree is what the algorithm builds as it explores.
- The frontier is the key data structure — its type (queue, stack, priority queue) determines the search strategy.
- A visited set prevents infinite loops by ensuring each state is expanded at most once.
- Uninformed search (BFS, DFS) explores blindly; informed search (A*) uses a heuristic to head toward the goal much faster.
Using the lesson's city graph, this BFS explores neighbors in the order they appear in each adjacency list. What does it print as the shortest path from A to F?
from collections import deque
graph = {
"A": ["B", "C"],
"B": ["A", "D", "E"],
"C": ["A", "F"],
"E": ["B", "F"],
}
def bfs(graph, start, goal):
frontier = deque([[start]])
visited = set()
while frontier:
path = frontier.popleft()
node = path[-1]
if node == goal:
return path
if node in visited:
continue
visited.add(node)
for nb in graph.get(node, []):
frontier.append(path + [nb])
return None
print(bfs(graph, "A", "F"))This BFS is meant to find a path in the lesson's graph, but it hangs forever and never returns. What's wrong?
from collections import deque
def bfs(graph, start, goal):
frontier = deque([[start]])
while frontier:
path = frontier.popleft()
node = path[-1]
if node == goal:
return path
for nb in graph[node]:
frontier.append(path + [nb])
return NoneThe frontier's data structure decides the search strategy. To make this BFS process the OLDEST path first (first-in, first-out), which deque method removes from the front?
from collections import deque frontier = deque([[start]]) while frontier: path = frontier.() # oldest path first node = path[-1] ...
Put the body of the BFS loop in the correct order: pull a path off the frontier, read its current node, test the goal, skip already-seen states, mark visited, then expand neighbors.
path = frontier.popleft()
visited.add(node)
if node == goal: return path
if node in visited: continue
node = path[-1]
for nb in graph[node]: frontier.append(path + [nb])
A delivery robot is on a 4x4 grid. Its position is a tuple (row, col) where (0,0) is the top-left corner. It can move up, down, left, or right, but cannot leave the grid or step on a wall.
Walls are at: (1,1), (1,2), (2,1). Start: (0,0). Goal: (3,3).
Complete the BFS function so it finds and prints the shortest path from start to goal.
Try it live — edit the code and hit Run to execute real Python: