A problem space, also called a state space, is the set of all situations a problem can be in, and its size decides how a computer can search it. The 8-puzzle has 181,440 reachable states and can be searched exhaustively in an instant. Checkers has about 5 x 10^20 positions and took dozens of computers years to solve, while a 19x19 Go board has about 2.08 x 10^170 legal positions, far beyond any exhaustive search.
Key takeaways
- A problem space is the set of states plus the moves that connect them. Its size, not its rules, sets the difficulty.
- Sizes grow by multiplication: 181,440 states in the 8-puzzle, 10,461,394,944,000 in the 15-puzzle, and 43,252,003,274,489,856,000 for the Rubik's Cube.
- Rubik's Cube was fully searched anyway: in 2010 researchers proved that every position can be solved in 20 moves or fewer, using about 35 CPU-years.
- Checkers was solved in 2007 (perfect play is a draw), but Go with about 2.08 x 10^170 legal positions cannot be searched exhaustively.
- When a space is too large, AI programs rely on heuristics, which trade a guarantee of the best answer for speed.
What a problem space contains
Formulating a problem for search means naming three things: the states, the moves that turn one state into another, and the goal. In a sliding-tile puzzle, a state is one arrangement of the tiles, a move slides a tile into the blank, and the goal is the ordered arrangement. A solver then looks for a path through the states. The space is not the same as the solution. A space can be huge while the shortest path is short, as the Rubik's Cube shows, and a small-looking rule set can still hide an enormous number of states.
How fast the number of states grows
The 8-puzzle has nine squares, so there are 9! = 362,880 ways to place the tiles. Only half can be reached from any given starting position, which leaves 181,440 states. A computer can list all of these in a fraction of a second. Moving to the 4x4 version, the 15-puzzle, multiplies the arrangement count to 16! and halves it again, giving 10,461,394,944,000 reachable states. That is about 58 million times as many, from adding seven squares. These two figures follow from simple arithmetic, which makes them a useful way to see why a small change in size can make a problem far harder.
Three real search results
The Rubik's Cube has 43,252,003,274,489,856,000 positions. In 2010, Tomas Rokicki, Herbert Kociemba, Morley Davidson, and John Dethridge showed that every one can be solved in 20 moves or fewer, a number called God's number, and the computation took about 35 CPU-years donated by Google.
In 2007, a research team announced in Science that checkers, with roughly 5 x 10^20 positions, was solved: perfect play by both sides leads to a draw. Dozens of computers worked on it, almost continuously, from 1989. Go sits much higher. John Tromp counted the legal positions on a 19x19 board in 2016 and found about 2.08 x 10^170, around 1.2 percent of all 3^361 ways of coloring the points.
Sizes compared
| Problem | Number of states or positions | Status |
|---|---|---|
| 8-puzzle | 181,440 reachable states | Searched in full on any computer |
| 15-puzzle | 10,461,394,944,000 reachable states | Solvable with a good heuristic |
| Rubik's Cube | 43,252,003,274,489,856,000 | All positions shown solvable in 20 moves or fewer (2010) |
| Checkers | About 5 x 10^20 | Solved in 2007; perfect play is a draw |
| Go, 19x19 | About 2.08 x 10^170 legal positions | Cannot be searched exhaustively |
The 8-puzzle and 15-puzzle counts are calculated from the arrangement formula above, while the other three are published results.
What programs do when the space is too big
When exhaustive search is impossible, programs search selectively. A heuristic is a rule of thumb that estimates how close a state is to the goal, so the search follows promising paths first. The cost is that the result may not be the best one. Other tools shrink the space before searching, such as a better representation of the states or a split of the problem into smaller pieces. This is why space size alone does not predict whether AI can handle a task: the Rubik's Cube space is vast yet was fully resolved, while Go's is far larger.
Questions to ask about a claimed AI problem
- What are the states, the moves, and the goal, stated precisely?
- Roughly how many states exist, and does the claim say how that number was reached?
- Does the solver guarantee the best answer, or only a good one?
- Does the result depend on symmetry or structure that real cases may lack?
FAQ
Is a problem space the same as a search space?
In most textbooks the terms overlap. The problem space is the set of states and moves, and the search space is the part of it that a particular algorithm actually explores.
Why are only half of the 8-puzzle arrangements reachable?
Sliding tiles can only produce arrangements of one parity. Half of the 9! orderings cannot be reached from a given start, which gives 181,440 reachable states.
Does solving checkers mean AI has solved games in general?
No. Checkers has about 5 x 10^20 positions, and the method took years on many computers. Go has about 2.08 x 10^170, so the same approach does not carry over.
Does a larger space always mean a harder problem?
Not always. The Rubik's Cube space is enormous, yet researchers proved that 20 moves always suffice, so the answer depends on structure and method as well as on size.
Related reading
- Worked examples of problem formulation
- Toy problems and their limits
- The traveling salesman problem and AI
- Search applied to robot navigation
More in AI Basics.
Last verified: October 2026
Sources
- God's Number is 20, Rokicki T, Kociemba H, Davidson M, Dethridge J, 2010
- Number of legal Go positions, Tromp J, computed January 20, 2016
- Checkers Is Solved, Schaeffer J et al., Science, 2007