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. Combinatorial explosion is sometimes used to justify the intractability of certain problems. Examples of such problems include certain mathematical functions, the analysis of some puzzles and games, and some pathological examples which can be modelled as the Ackermann function. A Latin square of order n is an n × n array with entries from a set of n elements with the property that each element of the set occurs exactly once in each row and each column of the array. An example of a Latin square of order three is given by, A common example of a Latin square would be a completed Sudoku puzzle. A Latin square is a combinatorial object (as opposed to an algebraic object) since only the arrangement of entries matters and not what the entries actually are. 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. 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.