At any given moment, large telescopes are trained on the night sky, since it is always night somewhere on Earth. They scrutinize Betelgeuse, which is said to be on the verge of exploding; they search for exoplanets and photograph nebulae—even black holes. And telescope time is precious! Each observation can be made only within a suitable time window, so the team must decide which observations to carry out each night and at precisely what time. The diagram on the left below shows a catalogue of eleven observations. Each is represented by a duration (black rectangle) and a possible time interval. Beneath it is the telescope schedule devised by the astrophysicists, which fits nine of the observations into two nights. There is almost no idle time: the telescope will move straight from one observation to the next.
Assignment problems -----------------------
But can the team do better and observe one more star over two nights? The stakes are high for the astrophysics team, because telescope time is rented by the night! Is this the best schedule—the best possible combination? How can we tell when the star catalogue at the Institut de planétologie et d’astrophysique de Grenoble (Isère) contains hundreds of thousands of targets? Combinatorics studies collections—often finite—of objects satisfying certain properties. Counting all such collections or finding the "best" one are combinatorial questions.
A famous combinatorial problem was posed by Leonhard Euler in 1779. Given six regiments, each containing six officers of different ranks, is it possible to arrange the thirty-six officers in a 6-by-6 square so that no row or column contains two officers of the same rank or regiment? The problem is easy to state; its difficulty often lies in the sheer number of combinations that must be assessed to identify the right one. This combinatorial explosion must be limited as far as possible, yet even the simplest problems lie beyond human capabilities. Computers have therefore been indispensable tools for solving them since at least 1953, if Harold William Kuhn (1925–2014), inventor of the Hungarian method for the assignment problem, is to be believed. But even a computer cannot explore the tree of all possible combinations without a healthy dose of anticipation (look-ahead ) and careful analysis of the search already performed (look-back)!