Problem formulation in artificial intelligence is the step of turning a task into a precise search problem: a set of states, a start state, the actions available in each state, a transition model that says what each action does, a goal test, and a cost for each step. The choices made here, above all what a state contains, decide whether a solver finishes in milliseconds or never, so formulation is often harder than the search that follows it.
Key takeaways
- A formulation has six parts: state space, actions, transition model, action cost, start state, and goal test.
- Goal formulation comes first; the Russell and Norvig exercise set asks readers to explain why problem formulation must follow it.
- A state should hold only what planning needs. Berkeley's CS188 notes show that pathing needs a position, while eating every dot also needs one true or false flag per dot.
- State counts multiply, so one extra variable can change a problem from solvable to hopeless.
- The same puzzle can be formulated two ways with very different sizes: 8 queens drops from about 1.8 x 10^14 ordered placements to 2,057 boards.
The six parts of a formulation
Berkeley's CS188 course text, in its chapter on state spaces and search problems, defines a search problem by the following pieces. The state space is the set of all states the world can be in. Actions are what the agent may do in each state. The transition model returns the next state when an action is taken in a state. An action cost says what each move costs. The start state is where the agent begins, and the goal test is a function that takes a state and says whether it is a goal. A solution, called a plan, is a sequence of actions from the start state to a state that passes the goal test.
The ordering matters. The exercises that accompany the Russell and Norvig textbook, hosted by the book's open-source exercise site, begin by asking why problem formulation must follow goal formulation. A goal such as "get from the depot to the customer" can be formulated as shortest distance, shortest time, or lowest fuel, and each choice produces a different cost function and possibly a different answer.
Example one: the 8-puzzle
The 8-puzzle is a three-by-three tray with eight numbered tiles and one blank. It is the standard first example because every part of the formulation can be written in one line.
| Part | 8-puzzle formulation |
|---|---|
| State | The position of each tile and the blank on the nine squares |
| Start state | Any arrangement that can reach the goal |
| Actions | Slide the blank up, down, left, or right, where the board allows |
| Transition model | The blank and the neighboring tile swap places |
| Goal test | Tiles appear in the target order |
| Action cost | One per move, so total cost equals number of moves |
The numbers come from simple counting. Nine squares can be filled in 9! = 362,880 ways, but one of the textbook exercises asks readers to show that the states split into two disjoint sets, with no path between them. Counting the states reachable from the standard goal, which a short breadth-first search confirms, gives 181,440, and the farthest arrangement is 31 moves away. These figures were computed for this article, not quoted from a publication. A search over 181,440 states is trivial for a computer, which is what makes the puzzle useful for teaching.
Example two: deciding what a state contains
CS188 draws a line between a world state, which holds all information about a configuration, and a search state, which holds only what planning needs. Its Pacman examples make the point. If the task is to reach an exit, the search state is Pacman's (x, y) position. If the task is to eat every dot, each dot needs a true or false flag as well. Details such as the total distance traveled can stay in the world state and out of the search.
The same page counts the full game by multiplying the number of values each variable can take: 120 positions for Pacman, four directions, 12 positions for each of two ghosts, and 30 dots that are each eaten or not. That product, 120 x 4 x 12 x 12 x 2^30, is about 7.4 x 10^13 states. Dropping the dots from the state, when the task does not depend on them, removes the factor of 2^30, roughly a billion.
Example three: 8 queens, two ways
Placing eight queens on a chessboard so that none attack each other can be formulated in more than one way. In the naive version, any queen may go on any empty square, so the search faces 64 x 63 x 62 x 61 x 60 x 59 x 58 x 57, about 1.8 x 10^14, ordered placements. In a smarter version, queens are added one per column from the left, and only on squares that no earlier queen attacks. Enumerating that tree gives 2,057 boards, including the empty one. Both formulations describe the same puzzle and have the same solutions; only the second keeps illegal positions out of the state space. Both figures were calculated for this article.
Common formulation mistakes
- The state leaves out a fact the goal depends on, so a "solution" fails in practice.
- The state includes facts the goal ignores, so the space grows without benefit.
- The action list allows moves the real world forbids, such as sliding a tile through another tile.
- The cost measures the wrong thing, such as steps when time or money matters.
- The goal test is vague, for example "good enough" with no threshold.
The exercise set shows the same habit in practice: it asks for formulations precise enough to implement and, for a maze, asks readers to list the simplifications made when moving from the real world to the abstract model. Each simplification is a decision someone should be able to defend.
FAQ
What is the difference between problem formulation and problem solving?
Formulation defines the problem in terms a program can use. Solving is the search through that space for a plan. A weak formulation can make a good search algorithm look bad.
Why must the goal be defined first?
The goal determines which facts belong in a state and what a step should cost. Without it, a designer cannot say what to include or what to leave out.
Is every AI task a search problem?
No. Route planning, puzzles, and scheduling fit the search framing well. Tasks such as image classification are usually posed as learning from examples, where the equivalent choices concern the data and the objective.
Why do the 8-puzzle and 8 queens appear so often?
They are small enough to enumerate and exact enough to check, so errors in a formulation show up quickly. Real problems add noise and missing information that these examples leave out.
Related reading
- Constraint satisfaction problems explained
- The robot navigation problem
- Heuristics in AI search
- How AI approaches problem solving
More in AI Basics.
Last verified: October 2026
Sources
- State Spaces and Search Problems, Introduction to Artificial Intelligence (CS 188) course text, University of California, Berkeley, 2024
- Search exercises, Artificial Intelligence: A Modern Approach exercise site, Russell and Norvig, aimacode project
- Artificial Intelligence: A Modern Approach, 4th US edition, Stuart Russell and Peter Norvig, book site at the University of California, Berkeley
- Counts of 8-puzzle states and 8-queens placements: computed for this article by direct enumeration