Min-conflicts algorithm

Repeat this process of conflicted variable selection and min-conflict value assignment until a solution is found or a pre-selected maximum number of iterations is reached.

The randomness helps min-conflicts avoid local minima created by the greedy algorithm's initial assignment.

Sub areas of the map tend to hold their colors stable and min conflicts cannot hill climb to break out of the local minimum.

Although Artificial Intelligence and Discrete Optimization had known and reasoned about Constraint Satisfaction Problems for many years, it was not until the early 1990s that this process for solving large CSPs had been codified in algorithmic form.

In collaboration with Hans-Martin Adorf of the Space Telescope European Coordinating Facility, he created a neural network capable of solving a toy n-queens problem (for 1024 queens).

Subsequently, Mark Johnston and the STScI staff used min-conflicts to schedule astronomers' observation time on the Hubble Space Telescope.

This results in a starting position with an average number of constraint violations that is surprisingly small and grows very slowly with n (e.g. 12.8 for n=106).