# Thirty-six officers problem

The thirty-six officers problem is a mathematical puzzle proposed by Leonhard Euler in 1782.[1][2]

The problem asks if it is possible to arrange six regiments consisting of six officers each of different ranks in a 6 × 6 square so that no rank or regiment will be repeated in any row or column. Such an arrangement would form a Graeco-Latin square. Euler correctly conjectured there was no solution to this problem, and Gaston Tarry proved this in 1901,[3][4] but the problem has led to important work in combinatorics.[5]

Besides the 6 × 6 case the only other case where the equivalent problem has no solution is the 2 × 2 case, i.e. when there are four officers.

In 1959, R. C. Bose and S. S. Shrikhande constructed some counterexamples (dubbed the Euler spoilers) of order 22 using mathematical insights.[6] Then E. T. Parker found a counterexample of order 10 using a one-hour computer search on a UNIVAC 1206 Military Computer while working at the UNIVAC division of Remington Rand (this was one of the earliest combinatorics problems solved on a digital computer).

In April 1959, Parker, Bose, and Shrikhande presented their paper showing Euler's conjecture to be false for all n ≥ 10. Thus, Graeco-Latin squares exist for all orders n ≥ 3 except n = 6.[7]