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))?