Min-conflicts Algorithm - Example

Example

A two step example of the Min-conflicts algorithm looking at the N-Queens Problem:

Min-Conflicts solves the N-Queens Problem by randomly selecting a column from the Chess board for queen reassignment. The algorithm searches each potential move for the number of conflicts (number of attacking queens), shown in each square. The algorithm moves the queen to the square with the minimum number of conflicts, breaking ties randomly. Note that the number of conflicts is generated by each new direction that a queen can attack from. If two queens would attack from the same direction (row, or diagonal) then the conflict is only counted once. Also note that if a queen is in a position in which a move would put it in greater conflict than its current position, it does not make a move. It follows that if a queen is in a state of minimum conflict, it does not have to move.

This algorithm's run time for solving N-Queens is independent of problem size. This algorithm will even solve the million-queens problem on average of 50 steps. This discovery and observations lead to a great amount of research in 1990 and began research on local search problems and the distinctions between easy and hard problems. N-Queens is easy for local search because solutions are densely distributed throughout the state space. It is also effective for hard problems. For example, it has been used to schedule observations for the Hubble Space Telescope, reducing the time taken to schedule a week of observations from three weeks to around 10 minutes.