Agents & Search›Core· 35 min read

Problem Solving as Search

Many AI problems become “find a path from the start state to a goal state”.

What you will learn

Describe a problem as states and actions
Define state space and goal test
Model a small puzzle as search

Turning a problem into search

Surprisingly many AI problems — mazes, route planning, puzzles, games — are the same shape: start in one state, take actions, reach a goal state. To define a search problem you list four things:

State — a snapshot of the situation (e.g. which cell you are standing in).
Actions — the moves allowed from a state (up, down, left, right).
Start state — where you begin.
Goal test — how you know you are finished.

A tiny maze as a graph

Picture a small maze. Each cell is a state; each open doorway is an action linking two states. We can write the whole maze as a dictionary of neighbours:

A maze written as a graph of states and the moves between them

# Each cell lists the cells you can move to (the "state space")
maze = {
    'A': ['B'],
    'B': ['A', 'C', 'D'],
    'C': ['B'],
    'D': ['B', 'E'],   # E is the exit
    'E': []
}

start = 'A'
goal  = 'E'
print('Neighbours of B:', maze['B'])

Note: Output: Neighbours of B: ['A', 'C', 'D'] Solving the maze now means: find a path of states from A to E. That is exactly what search algorithms do (next lesson).

The collection of all states you could reach is called the state space. For a maze it is tiny; for chess it is astronomically large — which is why we need smart ways to search it.

Tip: Once a problem is written as states + actions + goal test, you can reuse the same search algorithm for completely different problems — a maze, a puzzle, or planning delivery routes.

Q. In a maze search problem, what is a “state”?

Answer: A state captures the current situation. For a maze that is the cell you are standing in; actions move you to neighbouring states.

✍️ Practice

Add a cell F connected to D and write it into the maze dictionary.
Write the four-part search definition (state, actions, start, goal) for a sliding 8-puzzle.

🏠 Homework

Model planning a trip between 4 cities as a search problem: what are the states, actions and goal?