L'ensemble des états possibles d'un puzzle et de tous les mouvements légaux entre ces états constitue l'espace du problème. Il s'agit de la représentation mentale ou formelle d'un problème qui comprend l'état initial, l'état final et les opérateurs permettant de passer d'un état à un autre.

Newell et Simon ont introduit ce concept dans leur analyse de la résolution de problèmes chez l'humain. La recherche au sein de l'espace du problème peut être exhaustive ou guidée par des heuristiques qui réduisent le nombre de pistes envisagées. La taille et la structure de cet espace déterminent sa difficulté. Les experts l'élaguent efficacement en repérant les pistes prometteuses ; les novices, quant à eux, explorent souvent sans succès.

Les problèmes bien définis possèdent des espaces clairement spécifiés ; les problèmes mal définis obligent le résolveur à construire lui-même cet espace. La compréhension des espaces de problèmes facilite la conception de l’enseignement, des outils d’aide à la décision et des algorithmes de recherche en intelligence artificielle. La formulation d’un problème détermine les limites des solutions possibles.

• Représentation des états et des opérateurs dans un problème
• Comprend l'état initial, l'objectif et les étapes légales
• La recherche peut être systématique ou heuristique.
• L'expertise réduit l'espace de recherche effectif