The preceding algorithms systematically search the space of assignments of values to variables. If the space is finite, they will either find a solution or report that no solution exists. Unfortunately, many spaces are too big for systematic search and are possibly even infinite. In any reasonable time, systematic search will have failed to consider enough of the space to give any meaningful results. This section and the next consider methods intended to work in these very large spaces. The methods do not systematically search the whole search space but they are designed to find solutions quickly on average. They do not guarantee that a solution will be found even if one exists, and so they are not able to prove that no solution exists. They are often the method of choice for applications where solutions are known to exist or are very likely to exist.

Local search methods start with a total assignment of a value to each variable and try to improve this assignment iteratively by taking improving steps, by taking random steps, or by restarting with another total assignment. Many different local search techniques have been proposed. Understanding when these techniques work for different problems forms the focus of a number of research communities, in both operations research and AI.

A generic local search algorithm for CSPs is given in Figure 4.7. The array $A$ specifies an assignment of a value to each variable. The first for each loop assigns a random value to each variable. The first time it is executed is called a random initialization. Each iteration of the outer loop is called a try. The second and subsequent assignments of a random value to each variable in line 11 and line 12 is a random restart. An alternative to random initialization is to use some more informed guess, utilizing some heuristic or prior knowledge, which is then iteratively improved.

The while loop (line 13 to line 15) does a local search, or a walk, through the assignment space. It considers a set of possible successors of the total assignment $A$, and selects one to be the next total assignment. In Figure 4.7, the possible successors of a total assignment are those assignments that differ in the assignment of a single variable.

This walk through assignments continues until either a satisfying assignment is found and returned or some stopping criterion is satisfied. The stopping criterion, the $\text{stop\_walk}()$ function in the algorithm, is used to decide when to stop the current local search and do a random restart, starting again with a new assignment. A stopping criterion could be as simple as stopping after a certain number of steps.

This algorithm is not guaranteed to halt. In particular, if the termination condition is false, it goes on forever if there is no solution, and, even if there is a solution, it is possible to get trapped in some region of the search space. An algorithm is complete if it guarantees to finds an answer whenever there is one. This algorithm can be complete or incomplete, depending on the selection and the stopping criterion.

One version of this algorithm is random sampling. In random sampling, the stopping criterion $\text{stop\_walk}()$ always returns true so that the while loop from line 13 is never executed. Random sampling keeps picking random assignments until it finds one that satisfies the constraints, and otherwise it does not halt. Random sampling is complete in the sense that, given enough time, it guarantees that a solution will be found if one exists, but there is no upper bound on the time it may take. It is typically very slow. The efficiency depends on the product of the domain sizes and how many solutions exist.

Another version is a random walk when $\text{stop\_walk}()$ is always false, and so there are no random restarts. In a random walk the while loop is only exited when it has found a satisfying assignment. In the while loop, random walk selects a variable and a value for that variable at random. Random walk is also complete in the same sense as random sampling. Each step takes less time than resampling all variables, but it can take more steps than random sampling, depending on how the solutions are distributed. When the domain sizes of the variables differ, a random walk algorithm can either select a variable at random and then a value at random, or select a variable–value pair at random. The latter is more likely to select a variable when it has a larger domain.