What is state space representation? Illustrate with one example.

State‑space representation is a formal model that describes all possible configurations (states) of a problem and the permissible transitions (actions) between them. Each node in the graph denotes a unique state of the system, while each directed edge denotes an action that transforms one state into another. The complete set of nodes and edges constitutes the state space; it is the foundation on which search algorithms (e.g., breadth‑first search, A*) operate.

Key components

Illustrative example – 3‑tile sliding puzzle

Consider a miniature sliding‑tile puzzle with three numbered tiles (1, 2, 3) and a blank (0) on a $2\times 2$ board. The initial configuration $S_0$ and the goal configuration are:

$$S_0=\left[\begin{array}{cc}1& 2\\ 3& 0\end{array}\right],Goal=\left[\begin{array}{cc}1& 2\\ 0& 3\end{array}\right]$$

From $S_0$ the blank can move Left (L) or Up (U), generating two successor states $S_1$ and $S_2$. From each of these, a single move reaches the goal state $S_3$. The resulting state‑space graph is shown below.

Interpretation of the figure

• S0 – initial board $\left[\begin{array}{cc}1& 2\\ 3& 0\end{array}\right]$
• S1 – after moving the blank left: $\left[\begin{array}{cc}1& 2\\ 0& 3\end{array}\right]$ (which is already the goal in this tiny instance)
• S2 – after moving the blank up: $\left[\begin{array}{cc}1& 0\\ 3& 2\end{array}\right]$
• S3 – goal board $\left[\begin{array}{cc}1& 2\\ 0& 3\end{array}\right]$

The graph compactly captures every reachable configuration and the actions that connect them. A search algorithm can now traverse this graph from S0 to S3, guaranteeing that any found path corresponds to a valid sequence of moves solving the puzzle.