Suppose we have a group of officers in six regiments, each regiment consisting of the same six ranks (say, a colonel, a lieutenant colonel, a major, a captain, a first lieutenant, and a second lieutenant). Is it possible to arrange these 36 officers into a 6 × 6 square so that no rank or regiment is repeated in any row or column? That is, each row and column must contain an officer of each regiment and of each rank.

In 1782 Leonhard Euler wrote, “After we have put a lot of thought into finding a solution, we have to admit that such an arrangement is impossible, though we can’t give a rigorous demonstration of this.” He saw that the equivalent problem is impossible in a 2 × 2 square and surmised that it’s impossible in every case where the side of the square contains 4k + 2 cells.

It wasn’t until 1901 that French mathematician Gaston Terry proved that the 6 × 6 square has no solution, and it wasn’t until 1960 that Euler’s conjecture about the pattern of impossible squares was proven wrong: In fact, the task is impossible only in these two cases, 2 × 2 and 6 × 6.