Combinatorial explosion

In mathematics, a combinatorial explosion is the rapid growth of the complexity of a problem due to the way its combinatorics depends on input, constraints and bounds.

The number of Latin squares as a function of the order (independent of the set from which the entries are drawn) (sequence A002860 in the OEIS) provides an example of combinatorial explosion as illustrated by the following table.

A combinatorial explosion can also occur in some puzzles played on a grid, such as Sudoku.

[2] A Sudoku is a type of Latin square with the additional property that each element occurs exactly once in sub-sections of size √n × √n (called boxes).

Combinatorial explosion occurs as n increases, creating limits to the properties of Sudokus that can be constructed, analyzed, and solved, as illustrated in the following table.

In 2005 all chess game endings with six pieces or fewer were solved, showing the result of each position if played perfectly.

[8] Combinatorial explosion can occur in computing environments in a way analogous to communications and multi-dimensional space.

This rapid increase of leaf nodes can be useful in areas like searching, since many results can be accessed without having to descend very far.

A class hierarchy in an object-oriented language can be thought of as a tree, with different types of object inheriting from their parents.

[9] In administration and computing, a combinatorial explosion is the rapidly accelerating increase in communication lines as organizations are added in a process.

[10] The alternative approach is to realize when this communication will not be a one-off requirement, and produce a generic or intermediate way of passing information.