Problem Solving with AI: The State-Space Framework

Every classic AI problem — 8-puzzle, water jug, missionaries and cannibals, N-queens — is the same thing underneath: a state space you search. Here is the shared vocabulary, the search strategies, and how to pick one.

Before deep learning, before neural networks, “artificial intelligence” meant one thing: searching for a solution. Give the machine a puzzle, a set of legal moves, and a description of what winning looks like — and let it explore until it finds a path.

Nine problems show up in every AI syllabus on earth: the 8-puzzle, tic-tac-toe, block world, missionaries and cannibals, the travelling salesman, N-queens, the water jug, monkey and banana, and the vacuum cleaner. They look wildly different. They are all the same problem wearing different costumes.

This page gives you the costume-removal kit. Read it once, and the other nine pages become nine variations on a theme you already understand.

The one idea: a problem is a graph

Any problem you can describe with these four things is a state-space search problem:

Component	What it means	Example (8-puzzle)
State	A complete snapshot of the world at one moment	The exact arrangement of the 8 tiles + blank
Initial state	Where you start	The scrambled board you’re handed
Goal state (or goal test)	How you know you’ve won	Tiles in order 1–8 with blank last
Operators	The legal moves that turn one state into another	Slide blank Up / Down / Left / Right

Add these two and you can also talk about good solutions rather than just any solution:

Path cost — what each move costs (usually 1 per move, sometimes a distance, sometimes time).
Solution — the sequence of operators from initial state to goal.

Once you have those, the problem is a graph:

every possible state is a node
every legal move is an edge
solving the problem = finding a path from the start node to a goal node

That graph is called the state space. Nobody ever writes it down — it’s far too big. You generate it lazily, one node at a time, as the search explores.

Two ways to describe a state

Everything hinges on how you encode a state. Get this right and the code writes itself; get it wrong and you’ll fight the problem forever.

1. Explicit representation. Write down the whole world.

# 8-puzzle: a tuple of 9 slots, 0 = blank
state = (1, 2, 3,
         4, 0, 6,
         7, 5, 8)

2. Predicate / logical representation. Write down only what’s true.

ON(A, B)          # block A is on block B
ONTABLE(B)        # block B is on the table
CLEAR(A)          # nothing on top of A
HANDEMPTY         # the robot arm holds nothing

Sliding-tile and board problems use the explicit form. Block world and monkey and banana use the predicate form, because they came out of the logic/planning tradition. Both are just states; the choice is about convenience.

The rule that saves you every time: a state must be hashable and comparable. You will store thousands of them in a visited set. In Python that means tuples and frozensets, never lists or dicts.

Operators, and why they need preconditions

An operator is a function state → state, but it isn’t always legal. Every operator has two halves:

Preconditions — what must be true before you can apply it.
Effects — what changes after you apply it.

Operator: MOVE-BLANK-UP
  Preconditions: the blank is not in the top row
  Effects:       swap the blank with the tile directly above it

Operator: POUR(4-gallon → 3-gallon)
  Preconditions: 4-gallon jug is not empty AND 3-gallon jug is not full
  Effects:       transfer min(contents of 4, space left in 3)

Coding this up almost always looks like one function:

def successors(state):
    """Yield every (next_state, action, cost) legal from `state`."""
    for op in OPERATORS:
        if op.applicable(state):
            yield op.apply(state), op.name, op.cost

Write successors correctly and you can drop any search algorithm on top of it without changing a line. That’s the whole payoff of the framework.

How big is the state space?

This number decides which algorithm you’re allowed to use. Learn to estimate it before you write code.

Problem	State-space size	Comment
Vacuum cleaner (2 rooms)	8	Trivially solvable by hand
Water jug (4 & 3 gallon)	20	5 × 4 combinations
Missionaries & cannibals	32	Only 16 are legal
8-puzzle	181,440	9!/2 — half are unreachable
Tic-tac-toe	5,478 legal	255,168 distinct games
4-queens / 8-queens	256 / 16,777,216	$4^4$ and $8^8$ naïvely
15-puzzle	~10¹³	Needs a good heuristic
TSP, 20 cities	~6 × 10¹⁶	$(n-1)!/2$ — brute force is dead

Below roughly $10^6$ , plain breadth-first search will do. Above it, you need a heuristic. Above $10^{15}$ , you need to give up on optimality and take a good answer instead.

The search strategies

Every algorithm below is the same loop. They differ in one line: which node you pull out of the frontier next.

def search(start, is_goal, successors, frontier):
    frontier.push((start, []))
    visited = set()
    while frontier:
        state, path = frontier.pop()      # <-- THIS LINE is the algorithm
        if is_goal(state):
            return path
        if state in visited:
            continue
        visited.add(state)
        for nxt, action, cost in successors(state):
            if nxt not in visited:
                frontier.push((nxt, path + [action]))
    return None

Strategy	Frontier is a…	Finds shortest path?	Memory	Use when
BFS	queue (FIFO)	✅ yes (equal costs)	💀 huge	Small space, need optimal
DFS	stack (LIFO)	❌ no	✅ tiny	Deep space, any solution will do
Depth-limited	stack + cutoff	❌ no	✅ tiny	You know the depth bound
Iterative deepening	stack, repeated	✅ yes	✅ tiny	BFS optimality on a DFS budget
Uniform cost (Dijkstra)	priority queue on $g$	✅ yes (any costs)	💀 huge	Moves cost different amounts
Greedy best-first	priority queue on $h$	❌ no	medium	Speed over quality
A*	priority queue on $f = g + h$	✅ yes (if $h$ admissible)	large	The default for path problems
Hill climbing	current node only	❌ no	✅ tiny	Huge space, local moves (N-queens)
Minimax / α-β	game tree	✅ optimal play	medium	Two players (tic-tac-toe)

Heuristics: the thing that makes big problems tractable

A heuristic $h(n)$ is a cheap guess at how far state $n$ is from the goal. It doesn’t have to be right — it has to be useful.

A* picks the node with the smallest

$f(n) = g(n) + h(n)$

where $g(n)$ is the real cost you’ve spent getting to $n$ , and $h(n)$ is the guess at what’s left. That single formula is the workhorse of AI search.

Two properties matter:

Admissible — $h(n)$ never overestimates the true remaining cost. This guarantees A* finds the optimal path.
Consistent — $h(n) \le c(n, n') + h(n')$ for every edge. This guarantees A* never has to re-open a node.

Classic examples you’ll meet on the following pages:

Problem	Heuristic	Admissible?
8-puzzle	Number of misplaced tiles	✅ (each needs ≥1 move)
8-puzzle	Sum of Manhattan distances	✅ and much stronger
TSP	Cost of the minimum spanning tree of unvisited cities	✅
N-queens	Number of attacking pairs	used for hill climbing
Missionaries	People still on the wrong bank	✅

How to invent a heuristic: relax the problem. Remove a constraint, solve the easier version exactly, and use that cost as $h$ . “Misplaced tiles” comes from letting tiles teleport. “Manhattan distance” comes from letting tiles pass through each other. Relaxation always produces an admissible heuristic — that’s a theorem, not a coincidence.

Two families you’ll see on these pages

Not every problem is “find a path”. Watch for which family each one belongs to, because it changes the whole approach.

A reusable solver you can paste into every problem

Here is the code you’ll reuse on all nine pages. Only successors, is_goal and start change.

from collections import deque
import heapq

def bfs(start, is_goal, successors):
    """Shortest solution when every move costs the same."""
    frontier = deque([(start, [])])
    visited = {start}
    while frontier:
        state, path = frontier.popleft()
        if is_goal(state):
            return path
        for nxt, action in successors(state):
            if nxt not in visited:
                visited.add(nxt)
                frontier.append((nxt, path + [action]))
    return None


def astar(start, is_goal, successors, h):
    """Cheapest solution using a heuristic. `successors` yields (state, action, cost)."""
    counter = 0                                   # tie-breaker so heapq never
    frontier = [(h(start), 0, counter, start, [])]  # compares raw states
    best_g = {start: 0}
    while frontier:
        _, g, _, state, path = heapq.heappop(frontier)
        if is_goal(state):
            return path, g
        for nxt, action, cost in successors(state):
            ng = g + cost
            if ng < best_g.get(nxt, float('inf')):
                best_g[nxt] = ng
                counter += 1
                heapq.heappush(frontier, (ng + h(nxt), ng, counter, nxt, path + [action]))
    return None, float('inf')

Three details in there are worth memorising, because they’re the bugs everyone hits:

Mark visited when you push, not when you pop (in BFS). Otherwise the same state gets queued a dozen times and your memory explodes.
The tie-breaking counter in A*. Without it, Python compares the fourth tuple element when $f$ and $g$ tie — and raw states usually aren’t orderable, so you get a TypeError at a random moment.
best_g instead of a plain visited set. A* may reach a state again via a cheaper route; you must let it in.

How to read the next nine pages

Each problem page follows the same skeleton, so you can compare them directly:

The problem — the story, plainly told
State representation — the exact data structure
Initial and goal states — with a diagram
Operators — with preconditions
State-space size — the number that dictates the algorithm
Diagram of the search — the tree or graph, drawn out
A worked solution — traced move by move
Working Python — that you can run
Why it matters — what real system this is the toy version of

Start with the 8-Puzzle — it is the purest example of the whole framework, and every idea above shows up in it.

Two pages sit alongside the nine problems rather than being problems themselves. State Space Search is the rigorous version of this overview — the formal five-part problem definition, why a three-state space can generate an infinite search tree, and the completeness and complexity of every strategy in the table above. Issues in Search Techniques is the other side of the coin: the ways all of this fails in practice, and how to tell which failure you’re looking at.

Where to go next

State Space Search — the formal treatment: nodes vs states, tree vs graph search, complexity
Issues in Search Techniques — cycles, explosion, plateaux, bad heuristics
The 8-Puzzle — sliding tiles, and where A* was proven
Water Jug Problem — the smallest interesting state space
Missionaries and Cannibals — constraints that prune the tree
Tic-Tac-Toe — when there’s an opponent
Travelling Salesman — when the space is too big to search
A* Search — the algorithm itself, in depth