A local search method that retains one current candidate and repeatedly chooses an improving neighbor of its objective. For a conflict-minimization constraint satisfaction problem, a candidate can assign all variables within their constraint domains while violating some inter-variable constraints; the objective counts those violations. Zero conflicts certifies a solution, while a positive-conflict local minimum need not certify impossibility. Plateaus and local minima motivate sideways moves, randomized choices and restarting. Prescribed variables must remain fixed in every initialization and move.
A repair method for a constraint satisfaction problem: choose a currently conflicted, movable variable, and assign a permitted value minimizing its number of violated constraints with the other variables held fixed. Tie handling can permit sideways moves. For the queens completion problem, keep prescribed rows fixed, select a conflicted unfixed row, and choose a column minimizing attacks. Never interpret failure to improve as proof that no solution exists.
Articles by others on the same topic
Hill climbing is an optimization algorithm that belongs to the family of local search methods. It is often used in artificial intelligence and computer science to find a solution to problems by iteratively making incremental changes to a solution and selecting the best one available. The process can be thought of as climbing a hill: the algorithm starts at a given point (a solution) and explores neighboring points (solutions) in the solution space.