Editing State space (computer science) (section)

==Properties==
{{Chess diagram
| tright
|
|__|__|__|__|__|ql|_|__
|__|__|__|ql|__|__|__|__
|__|__|__|__|__|__|ql|__
|ql|__|__|__|__|__|__|__
|__|__|__|__|__|__|__|ql
|__|ql|__|__|__|__|__|__
|__|__|__|__|ql|__|__|__
|__|__|ql|__|__|__|__|__
|A valid state in the state space of the eight queens puzzle
}}
A state space has some common properties:
* complexity, where [[branching factor]] is important
* structure of the space, see also [[graph theory]]:
** directionality of arcs
** tree
** [[rooted graph]]
For example, the Vacuum World has a branching factor of 4, as the vacuum cleaner can end up in 1 of 4 adjacent squares after moving (assuming it cannot stay in the same square nor move diagonally). The arcs of Vacuum World are bidirectional, since any square can be reached from any adjacent square, and the state space is not a tree since it is possible to enter a loop by moving between any 4 adjacent squares.

State spaces can be either infinite or finite, and discrete or continuous. 

===Size===
The size of the state space for a given system is the number of possible configurations of the space.<ref name=MIDYNS/>
====Finite====
If the size of the state space is finite, calculating the size of the state space is a [[Enumerative combinatorics|combinatorial]] problem.<ref name=SACEA/> For example, in the [[eight queens puzzle]], the state space can be calculated by counting all possible ways to place 8 pieces on an 8x8 chessboard. This is the same as choosing 8 positions without replacement from a set of 64, or
:<math> \binom{64}{8} = 4,426,165,368</math>
This is significantly greater than the number of legal configurations of the queens, 92. In many games the effective state space is small compared to all reachable/legal states. This property is also observed in [[chess]], where the effective state space is the set of positions that can be reached by game-legal moves.  This is far smaller than the set of positions that can be achieved by placing combinations of the available chess pieces directly on the board.

====Infinite====
All continuous state spaces can be described by a corresponding [[continuous function]] and are therefore infinite.<ref name=MIDYNS/> Discrete state spaces can also have ([[countable set|countably]]) infinite size, such as the state space of the time-dependent "counter" system,<ref name=CMUINF/> similar to the system in [[queueing theory]] defining the number of customers in a line, which would have state space {0, 1, 2, 3, ...}.