# Striking examples of success of local search algorithms

In N queens problem https://en.wikipedia.org/wiki/Eight_queens_puzzle, trying to find solution by backtracking encounters difficulties quite fast (even for SWI-Prolog, http://swish.swi-prolog.org/example/clpfd_queens.pl, which solves N=100 in 0.2 sec, entering N=150 in the link above did not reach a solution in a reasonable amount of time ("time limit exceeded"), and as for ECLiPSe (another Prolog with constraint poropagation) it chokes much, much earlier..).

On the other hand, local search works incredibly well on this problem (https://stackoverflow.com/questions/1863531/n-queens-probiem-how-far-can-we-go, answer by the user chesslover), as the solutions seem to be reachable easily enough by hill climbing (or rather, in this case, hill descending with occasional short range climbing), starting from a random position in the space of possible configurations (each column is occupied by exactly one queen).

Which other well known problems appear to have similar properties (say, a part from examples given in https://en.wikipedia.org/wiki/Local_search_(optimization))?

The following paper

has a thorough comparison of local search vs. backtracking-like algorithm. In the introduction, it even features a question:

"What is the essential difference between local search and backtracking, that sometimes enables local search causes to scale far better than backtracking"

While describing his variation of a hybrid local search + backtracking algorithm, Prestwich tests it on

• classic $N$ queens problem
• graph coloring with "real-world applications to timetabling, scheduling, frequency assignment, computer register allocation, printed circuit board testing, and pattern matching"
• satisfiability (SAT)

All of the above (with possible specialization) can serve as examples for your question.

The other reference that is directly related to a comparison of local search algorithm to backtracking-like is:

which will also talk about the possible reasons for local search to perform better than backtracking.

In general, the possible reasons can be summarized as (Prestwich, 2001):

• randomness
• incompleteness
• scalability
• different search space