Before an agent can search for a solution, the problem must be stated precisely: what a state is, which actions exist, what they do, what counts as the goal and what each step costs. A good formulation can shrink the search space by orders of magnitude.

The five components of a search problem

Component	Meaning	Route finding (Romania)	8-puzzle
Initial state	Where the agent starts	In(Arad)	A scrambled board
Actions(s)	Moves applicable in state `s`	Drive to a neighbouring city	Slide the blank Up/Down/Left/Right
Transition model Result(s, a)	The state an action leads to	In(Sibiu) after driving Arad → Sibiu	Board with blank and tile swapped
Goal test	Is `s` a goal?	In(Bucharest)	Tiles in order 0–8
Path cost	Sum of step costs `c(s, a, s′)`	Road kilometres	1 per move

Initial state + actions + transition model define the state space — a graph whose nodes are states and edges are actions. A solution is an action sequence from the initial state to a goal; an optimal solution has the lowest path cost.

Formulating the 8-puzzle

Python

from collections import deque

GOAL = (0, 1, 2,
        3, 4, 5,
        6, 7, 8)                       # 0 is the blank

def actions(state):
    row, col = divmod(state.index(0), 3)
    moves = []
    if row > 0: moves.append("Up")
    if row < 2: moves.append("Down")
    if col > 0: moves.append("Left")
    if col < 2: moves.append("Right")
    return moves

def result(state, action):              # transition model: slide the blank
    i = state.index(0)
    j = i + {"Up": -3, "Down": 3, "Left": -1, "Right": 1}[action]
    s = list(state)
    s[i], s[j] = s[j], s[i]
    return tuple(s)

start = (3, 1, 2,
         0, 4, 5,
         6, 7, 8)
print(actions(start))                            # ['Up', 'Down', 'Right']
print(result(start, "Up") == GOAL)               # True

# the whole state space reachable from the goal, by breadth-first expansion
seen, frontier = {GOAL}, deque([GOAL])
while frontier:
    s = frontier.popleft()
    for a in actions(s):
        t = result(s, a)
        if t not in seen:
            seen.add(t)
            frontier.append(t)
print(len(seen))                                 # 181440 ← 9!/2: only half of all 9! boards are reachable

Formulation decides the size of the space

Problem	Formulation	States
8-queens	Add queens anywhere, one at a time (64 squares, 8 queens)	64 · 63 · … · 57 ≈ 1.8 × 10¹⁴ sequences
8-queens	One queen per column, left to right, never attacking an earlier one	2,057
8-puzzle	All boards	9!/2 = 181,440 reachable
15-puzzle	All boards	16!/2 ≈ 1.05 × 10¹³
Rubik's cube	All positions	≈ 4.3 × 10¹⁹

Search trees, frontiers and repeated states

Search algorithms grow a search tree over the state space. Each node stores a state, its parent, the action that produced it, the path cost g and the depth. The frontier (open list) holds generated-but-not-expanded nodes; the order in which it is expanded is the only difference between most search strategies.

Initialise
Put a node for the initial state on the frontier.
Choose
Remove a node from the frontier according to the strategy (FIFO, LIFO, lowest cost…).
Test
If its state is a goal, return the path (follow parent links back).
Expand
Otherwise generate its children — one per applicable action — and add them to the frontier.
Repeat
Until the frontier is empty → failure.

Measuring a search strategy

Criterion	Question	Symbols used
Completeness	Is it guaranteed to find a solution when one exists?	`b` = branching factor (max children per node)
Optimality (cost-optimal)	Does it find the lowest-cost solution?	`d` = depth of the shallowest goal
Time complexity	How many nodes does it generate?	`m` = maximum depth of the state space (may be ∞)
Space complexity	How many nodes are in memory at once?	`C*` = optimal cost, `ε` = smallest step cost

What are the components of a well-defined search problem?

What is the difference between a state and a node?

Tree search vs graph search?