Concept

Exact-cover

The problem of choosing pieces from a list so that every cell of a region is covered exactly once, with no gaps and no overlaps. Tilings, dissections and many puzzles reduce to it, and it is solved by systematic backtracking.

Named by 2 essays across one field — each of them below, with the objects they name alongside it.

A random Latin square of order ten with an orthogonal mate. A 10 by 10 grid with a uniformly random Latin square and an orthogonal mate written into each cell; the square has 848 transversals.

A mate is rare until order ten

Euler asked whether a Latin square can have an orthogonal mate, and for every order but two and six the answer is yes for some square. For a square chosen at random the answer is different. Exactly 6 of the 56 reduced squares of order five have a mate and none of order six does; of squares drawn at random, about one in a hundred of order seven has one, one in three hundred of order eight, one in seventy of order nine — and three in five of order ten.

computation · Latin squares

Every convex shape the tangram can make. The 13 convex polygons that the seven tangram pieces can form, each with one arrangement, and the number of arrangements of each: 20, 12, 12, 12, 36, 12, 8, 8, 16, 4, 56, 24, 36.

Thirteen convex tangrams

The seven tangram pieces make thousands of figures, and only thirteen of them are convex. The proof turns a puzzle with sliding pieces into a finite list: every piece is made of the same small triangle, any convex figure puts them all on one grid, and that grid allows exactly twenty convex outlines of the right area. A search tries all twenty and finds that thirteen can be made.

computation · Scissors congruence

Named alongside it

The objects these essays reach for when they reach for this one.

Exhaustive search Classification Convexity Dissection Latin square Lattice Markov chain monte carlo Orthogonal latin squares Sampling Transversal

All concepts