Constraint satisfaction · Part 2

A constraint satisfaction problem, abbreviated CSP, describes decisions using variables, domains and constraints. A variable names a choice to be made. Its domain is the set of allowed values. A constraint is a rule that the chosen values must satisfy.

We will keep using the same example as Part 1: variables X₁, X₂ and X₃, each with initial domain {0,1,2}, and constraints X₁<2, X₂>0 and X₃<X₁. The function dom returns a variable’s allowed-value set; here dom(X₁)=dom(X₂)=dom(X₃)={0,1,2}.

The formal shorthand is P=(𝓧,dom,𝓒), where P names the problem, 𝓧={X₁,X₂,X₃} is the variable set, and 𝓒 is the set of three constraints. We first use these objects in ordinary language before returning to the formulas later in the pack.

Capital X denotes a variable and lowercase x can denote a candidate value from its domain. Braces denote a set of options; they do not say which value has been chosen. The aim is to find one or all total assignments that use allowed values and satisfy every rule.

The three rules form the conjunction (X₁ < 2) ∧ (X₂ > 0) ∧ (X₃ < X₁). The symbol ∧ means AND: every rule must hold. The next recap revisits ∧ and the alternative connective ∨ (OR) before using them in the examples.

Logical connectives combine statements into a larger condition. The symbol ∧ means AND, also called conjunction: the combined condition is true only if every part is true. The symbol ∨ means OR, also called disjunction: the combined condition is true if at least one part is true. This OR is inclusive, so it is also true when both parts are true.

The running CSP has variables X₁,X₂,X₃ with domains {0,1,2}. Its three constraints must hold together: (X₁ < 2) ∧ (X₂ > 0) ∧ (X₃ < X₁). Parentheses group the individual statements; ∧ connects them. Writing the constraints as a comma-separated set or list is shorthand for requiring all of them, rather than choosing just one.

Take the total assignment (1,0,0), in order X₁,X₂,X₃. The three rules give true, false, true. Their conjunction is therefore false: this candidate is not a solution, even though two rules hold.

For a separate OR illustration, consider (X₁=1) ∨ (X₂=2). At (1,0,0), the left statement is true and the right is false, so the OR is true. At (1,2,0), both are true and the OR is still true. At (0,0,0), both are false and the OR is false. This example is not an additional constraint in the running CSP; satisfying it alone does not establish a solution.

A CSP takes the conjunction of all its constraints. Within one constraint, AND and OR may be combined to describe the permitted alternatives. For example, the solutions can be written as (X₁=1) ∧ ((X₂=1) ∨ (X₂=2)) ∧ (X₃=0). The outer AND fixes X₁ and X₃; the grouped OR permits either remaining X₂ value. Without parentheses, AND is conventionally read before OR; explicit grouping makes the intended rule easier to see.

The truth table uses r and s to stand for statements, not CSP variables. It assumes their inputs are available so each statement has a true/false value. With a partial context, a rule whose scope is incomplete remains pending, as in the evaluation examples. The logical symbols do not turn a missing value into false.

Do not confuse ∧ and ∨, which combine statements, with ∩ and ∪, which combine sets. For example, X₂∈{1,2} describes a choice from a set and is equivalent to (X₂=1) ∨ (X₂=2); it does not assign the set {1,2} as X₂’s value.

An assignment records selected variable–value pairs. A proper partial assignment leaves at least one variable undecided. Here a partial assignment is also called a context, often named A. For example, A={X₁=1} sets only X₁. The question mark in the slide is a visual reminder of an unassigned variable, not a fourth allowed value.

A total assignment gives every variable a value. We often name a total assignment a and write its values as a tuple in the fixed order X₁,X₂,X₃. Thus a=(1,2,0) means X₁=1, X₂=2 and X₃=0. It is a solution because 1<2, 2>0 and 0<1 all hold.

Being total does not imply being correct. The candidate (0,1,0) uses legal domain values and fills every position, but its final rule becomes 0<0, which is false. This total assignment is not a solution. That distinction matters later when local search deliberately works with complete candidates that still violate rules.

A rule can be evaluated when every variable it uses has a value. The set of variables used by a rule is its scope. With only X₁=1 assigned, X₁<2 is true, but X₂>0 and X₃<X₁ are pending. Pending means that input is missing, rather than that the rule has failed. Formally, a partial assignment may include any subset, including all variables; the left-hand example is specifically a proper partial assignment.

At (1,2,0), the combined test is (1<2) ∧ (2>0) ∧ (0<1), which is true because all three parts hold. At (0,1,0), the last part is false, making the whole conjunction false.

Generate-and-test enumerates total assignments and checks their constraints. Three variables with three allowed values each give 3×3×3=27 candidates before filtering. This is straightforward but can waste work constructing a complete candidate whose failure could have been noticed earlier.

Depth-first search (DFS) with backtracking builds a partial assignment one choice at a time. It tests a constraint once its whole scope is assigned. Choosing X₁=2 immediately violates X₁<2, so the entire branch can be rejected without trying the nine combinations of X₂ and X₃ below it.

Constraint propagation operates on domains. It can reason about the existence of partners before selecting them. For example, X₁=0 cannot be part of a satisfying pair for X₃<X₁ because no X₃ in {0,1,2} is below 0. It can therefore delete 0 from dom(X₁) while X₃ is still unassigned.

The contrast is about the working object: ordinary backtracking checks the values in a chosen context, whereas propagation removes unsupported values from sets of remaining alternatives. These methods can be combined. Part 2 will make assumptions by splitting a domain, then propagate their consequences in each separate branch.

Generalized arc consistency (GAC) filters domains using support. For X₃<X₁, the value X₁=1 has the supporting partner X₃=0, while X₁=0 has none in {0,1,2}. A value needs one satisfying partner combination for each checked rule, rather than working with every possible partner.

E is the set of pending (variable,constraint) checks, using the same notation as Part 1. E₀ is the full initial edge set. A pair (X,c) asks whether the remaining values of X have support for c; it is not multiplication.

A deletion can invalidate another check, which returns to E. The algorithm stops on an empty domain or when all scheduled checks are complete. Its output is a domain mapping, not a list of total assignments. The next recap reads those domains before domain splitting resumes systematic search.

The running example reaches dom(X₁)={1}, dom(X₂)={1,2} and dom(X₃)={0}. The unary rules remove X₁=2 and X₂=0. The binary rule X₃<X₁ also eliminates X₁=0 and the unsupported X₃ values. The remaining domain sets tell us which choices have survived filtering.

A singleton is a set containing one value, such as {1}. The first and third variables now have only one possible value each, while X₂ can still use 1 or 2. Writing dom(X₂)={1,2} describes options; writing X₂=1 makes a particular choice. These statements describe different stages of solving.

GAC has three outcomes in general. If some domain becomes empty, the current branch cannot contain a solution. If every domain is a singleton and all GAC checks are complete, those values determine a solution. If the domains are nonempty but choices remain, filtering alone is inconclusive: there may be several solutions, one solution or none. This final possibility is illustrated by the equality/equality/inequality example from Part 1.

In this particular running CSP, both remaining X₂ values lead to solutions. Domain splitting will make the alternatives explicit in separate branches. This creates the bridge to the first new topic of Part 2: copy the filtered domains, restrict one domain differently in each branch, and propagate again. Later, local search will explore a different approach by modifying one complete candidate at a time.

For this particular CSP, the remaining alternatives are (X₁=1) ∧ ((X₂=1) ∨ (X₂=2)) ∧ (X₃=0). AND (∧) combines the fixed requirements with the choice; OR (∨) connects the two allowed X₂ values. The OR does not mean that a single assignment sets X₂ to both values.

Part 1 ended with pruned domains, which may still leave alternatives. Part 2 first completes systematic search by splitting a domain and propagating each branch. It then introduces local search, which starts from a total assignment and repairs conflicts.

For local search we use h(a), the number of violated constraints. A candidate with h(a)=0 is a solution. A run with a finite time or step budget that stops with h(a)>0 has not proved impossibility.

Keep the working object in mind: splitting works with branches of domain restrictions, whereas local search changes complete candidates. Their output claims are therefore different.

Part 1 introduced consistency algorithms. GAC filters domains but may stop with several choices and no existence proof. Generate-and-test could enumerate the remaining combinations; splitting instead makes one restricted-domain assumption at a time and runs GAC again, so each assumption can trigger further pruning.

Domain splitting makes an unresolved choice explicit. Choose a variable whose domain has more than one value and partition that domain into nonempty, disjoint sets covering all its values. Make a separate copy of the current domains for each branch and restrict the chosen domain to one part.

Run GAC in each branch. Reject empty-domain branches, record fully consistent singleton-domain solutions, and split again if alternatives remain. For example, {1,2,3,4} can be split into {1,2} and {3,4}; the parts need not always be singletons.

The running CSP already reduces to {1}, {1,2}, {0}. Splitting X₂ into {1} and {2} immediately determines the solutions (1,1,0) and (1,2,0). Keeping branches separate prevents a deletion made under one assumption from leaking into another.

For finite domains, repeated splitting into proper smaller parts eventually reaches singleton choices or failures. Sound propagation plus exhaustive exploration therefore finds all solutions or proves none exists. Stopping after one branch does not establish that full claim.

The choice (X₂=1) ∨ (X₂=2) is an OR between branch assumptions. Each branch still requires the AND of all original constraints: (X₁ < 2) ∧ (X₂ > 0) ∧ (X₃ < X₁). Explore both branches to enumerate every solution; one total assignment chooses one X₂ value.

Let dom₀ be the domain function returned by GAC in the current branch. Choose X with |dom₀(X)|>1. A two-way split partitions that set into nonempty parts D₁ and D₂. They must cover it, D₁∪D₂=dom₀(X), and must be disjoint, D₁∩D₂=∅.

Union ∪ combines the choices; intersection ∩ keeps shared choices; ∅ is the empty set. Nonempty, disjoint, covering parts are proper smaller subsets of the original domain. A solution’s chosen X value therefore belongs to exactly one branch, so no solution is lost and no assignment is duplicated across the two parts.

The branch maps dom₁ and dom₂ copy all domains from dom₀ except the selected variable: domⱼ(X)=Dⱼ and domⱼ(Y)=dom₀(Y) for every other Y, with j∈{1,2}. They must be separate copies because later pruning in one branch depends on that branch’s assumption.

Splitting into halves is common; balanced parts are a convenient choice rather than the reason correctness holds. After restricting X, propagation must follow all affected consequences. If the parent is already GAC-consistent, an optimized implementation can seed its worklist with affected edges instead of every edge.

The second line combines three statements using ∧: the parts are disjoint AND the first is nonempty AND the second is nonempty. Together with the coverage equality on the first line, all these conditions are required. The symbols ∪ and ∩ operate on sets, while ∧ combines true/false requirements.

The full signature Con_Solve(𝓧,𝓒,E) makes the variable set 𝓧, constraint set 𝓒 and pending checks E explicit. Variables carry their current domains. GAC(𝓧,𝓒,E) is the same filtering step introduced in Part 1; here the domains are carried with the variables instead of being passed as a separate dom argument. The result dom₀ maps each variable to its remaining allowed values.

Lines 3–6 handle two stopping cases. If some variable X has an empty domain, return ∅: this branch has no solution. If every variable has one value, {X=x | X∈𝓧, x∈dom₀(X)} forms the complete assignment from those unique values. The extra outer braces return a solution set containing that one assignment. Thus {{…}} and ∅ mean one solution and no solutions, respectively.

Otherwise, lines 8–9 choose X with more than one remaining value and partition dom₀(X) into two nonempty, disjoint parts D₁ and D₂ covering the original domain. Lines 10–11 create branch mappings dom₁ and dom₂. For every other variable Y≠X, its domain initially stays dom₀(Y). X instead receives D₁ in the first branch and D₂ in the second. The parentheses keep the scope of ∀Y≠X explicit; X’s own domain is set separately.

Line 12 constructs E′, the affected variable–constraint checks. Z is another variable and c′ is a constraint containing both X and Z. The condition {X,Z}⊆scope(c′) says both variables belong to that constraint’s scope. Revising X can remove a supporting value for Z, so the pair (Z,c′) needs checking again. The prime mark ′ labels another or updated object; it is not a derivative. The set conditions are all required.

On line 13, 𝓧[dom₁] means the same variables equipped with the first branch’s domain mapping; 𝓧[dom₂] uses the second mapping. This is a domain override, rather than selecting a subset of variables as in an assignment restriction a[S]. Both recursive calls retain the same constraints 𝓒. They receive independent domain and worklist copies, and ∪ combines their solution sets.

The affected worklist E′ is sufficient because line 2 first establishes a GAC fixed point. Further deletions can schedule additional checks. The first call begins with all network edges in E. With finite domains, sound filtering and exhaustive splitting, the procedure finds every solution or establishes that none exist. If one branch returns ∅, the other branch still needs to be explored.

Use Next line to reveal comments one at a time, select a line number directly, or choose Show all. All comments are visible automatically in print. In this pseudocode, = stores a computed value or domain on lines 2 and 10–12; inside a condition, = compares values.

Step through the running example and identify the domain selected for splitting. After initial GAC, only X₂ has multiple values. Each restriction yields a complete solution, so there are two solution leaves.

Now select the equality/equality/inequality contradiction. GAC alone cannot reject its root domains, but branching commits to values that must agree across constraints. Propagation then exposes failures in every branch.

This contrast shows why propagation and search work together. GAC removes locally impossible choices; splitting ensures that remaining alternatives are eventually considered. Exhaustive failure is a proof of impossibility, unlike a bounded local-search failure.

The assignment space contains all combinations of allowed variable values. Generate-and-test, backtracking and domain splitting search this space systematically. Pruning can skip impossible branches, but the remaining space may still be enormous. With infinite domains, the assignment space may even be infinite; an exhaustive search may then fail to terminate.

Local search changes the goal of the exploration: keep one total candidate assignment and repeatedly modify it, rather than trying to cover every alternative. A local change might replace the value of one variable. The candidate may violate constraints while the algorithm searches for a repair.

This can require much less work than systematic exploration and can find solutions quickly on some problems. It is not a guarantee of greater speed on every problem. In a bounded run, local search may miss an existing solution because it explores only selected candidates or becomes trapped. Finishing without a solution therefore does not prove that the CSP is unsatisfiable.

The worked examples in these packs have finite domains. The reference to infinite spaces describes a broader class of CSPs; local search itself still requires suitable ways to choose candidate values and moves.

Backtracking builds a partial assignment and prunes a branch when a completed rule fails. Local search instead begins with a total assignment, even if that candidate violates some constraints, and repeatedly changes it.

The lowercase letter a names a complete candidate assignment: one allowed value for every variable. h(a), read “h of a”, is its conflict score, the number of constraints that a violates. Each violated constraint contributes 1; each satisfied constraint contributes 0. A lower score means fewer broken rules, and h(a)=0 means that a is a solution.

For a=(0,1,0), in variable order X₁,X₂,X₃, the rules X₁<2 and X₂>0 hold, but X₃<X₁ fails because 0<0 is false. Exactly one rule is broken, so h(a)=1. Changing X₁ to 1 gives (1,1,0); all three rules hold and the new candidate has score 0.

A neighboring candidate is obtained by one permitted local change, such as changing one variable’s value. A policy decides which neighbor to propose and whether to accept it. Zero conflicts verifies success; a nonzero score describes an unfinished repair, not a proof that repair is impossible.

We begin with generic search: a complete candidate, a neighborhood of allowed moves, a conflict score, and the selection and stopping functions in a common loop.

Random sampling tests independent fresh candidates. Random walk keeps the current candidate and changes a randomly chosen variable/value pair. Keeping these as separate topics makes the distinction between restarting and moving locally explicit.

Iterative best improvement (IBI) uses score-guided selection to choose a most-improving step. We then study tabu memory, a plateau example, and random-restart/random-step escape strategies. Strict descent and tabu have different acceptance behavior: tabu may allow a move that does not improve the current score.

Simulated annealing uses temperature to control the acceptance of worse moves. Its probability rule and cooling schedule precede the final interactive comparison. The same candidate space and conflict score let us compare the policies without changing the problem at every step.

A local-search state is a domain-valid total assignment. Its neighborhood is the set of candidates reachable by one permitted local change. In our CSP examples, change the value of exactly one variable to another value in its domain, keeping all other values fixed. This defines possible moves before we decide which moves to take.

For the running CSP, start at a=(0,1,0), in variable order X₁,X₂,X₃. Only X₃<X₁ fails, so the conflict count is h(a)=1. Changing X₁ to 1 gives the neighbor (1,1,0), with no conflicts. Changing X₂ to 0 gives (0,0,0), with two conflicts: X₂>0 and X₃<X₁ both fail. Both are valid neighbors even though one is better and the other is worse.

A movement policy supplies two decisions: which neighbor to propose and whether to accept it. Random walk chooses a random one-variable change and retains it. Strict best improvement examines the neighborhood and takes a neighbor with the lowest score only when that score improves the current one. Simulated annealing can accept a worse proposed neighbor according to its temperature.

Random sampling is the contrasting baseline: it draws a fresh total assignment rather than following one neighboring move. The generic local-search loop can express sampling by skipping repairs and immediately beginning a fresh attempt. The next sections connect each method to that common loop, making clear what is shared and what changes.

The graph-coloring example that follows uses exactly the same idea. A total assignment gives each vertex a color, one move recolors one vertex, and h(a) counts equal-colored endpoints on constrained edges.

The added local-search example is a graph-coloring CSP. Variables A, B, C and D choose among red, green and blue. Its edges are A–B, B–C, C–D, D–A and A–C. Each edge represents a different-color constraint.

The complete rule is (A≠B) ∧ (B≠C) ∧ (C≠D) ∧ (D≠A) ∧ (A≠C). Each comparison requires the colors of two joined vertices to differ. The ∧ symbols mean AND, so all five comparisons must hold together.

The assignment shown is a={A=red, B=green, C=red, D=blue}. The four outside edges satisfy their rules: red≠green, green≠red, red≠blue and blue≠red. The diagonal A–C breaks A≠C because both vertices are red. Exactly one constraint is violated, so the conflict score is h(a)=1.

A neighbor changes one vertex to another domain color. The lab evaluates the entire resulting coloring, since one change can fix some conflicts and create others. h(a)=0 verifies a solution of this graph-coloring CSP; it does not mean the candidate is optimal for an additional objective that the model has not specified.

An evaluation function assigns a score to a complete candidate a. Here the score is simply the number of violated constraints: add 1 for each broken rule and 0 for each satisfied rule. Lower scores are preferred. A score of zero means all rules hold.

We use the same notation throughout local search: h(a) is the conflict score of candidate a. It is a number, not a domain, an assignment or a worklist.

For a=(0,1,0), X₁<2 and X₂>0 hold, contributing 0 each. X₃<X₁ fails, contributing 1. The total score is therefore 0+0+1=1. For (1,1,0), all three contributions are zero and the score is 0.

This is the common framework for the local-search methods that follow. The inputs are the variable set 𝓧 and constraint set 𝓒. The current candidate a always contains one allowed value for every variable. Use Next line or click a line number to reveal its explanation; Show all exposes the complete commentary.

Lines 2–5 start an attempt by choosing a random allowed value for each variable. rand(dom(X)) means choose randomly from X’s domain. a[X] stores X’s current value. In this pseudocode, = sets a value on lines 4 and 7–9; inside the rule tests, =0 or =1 checks a result.

Line 6 combines two requirements with AND (∧): the attempt has not been stopped, and at least one constraint still fails. stop() ends this attempt, for example at a step limit or when no improving move remains. Lines 7–9 choose a variable Y, choose an allowed value y, and update just that variable. The selection functions determine the method; they may use random choices or the current conflict score h(a).

The expression ε(a[scope(c)],c) checks rule c using just the values of the variables it needs. It returns 1 when the rule holds and 0 when it fails. ∃c∈𝓒 means at least one constraint; ∀c∈𝓒 means every constraint. The test on line 11 is performed after the repair loop, so a solution found on the final allowed update is still returned.

If no solution was returned, line 14 calls terminate(). True ends the whole search; false repeats from a fresh random assignment. stop() therefore controls one attempt, whereas terminate() controls whether there will be another attempt. Returning ∅ means no solution was found by this run; it does not prove that the CSP has no solution.

Random sampling skips repairs; random walk chooses random local changes; iterative best improvement uses the score to guide changes. For a method that can reject a proposal, such as annealing, value selection can retain the old value when a proposal is rejected. The following coloring example makes a complete attempt visible before we study the individual methods.

Use the same four-vertex coloring throughout the five methods. Each vertex is a variable with domain {red, green, blue}. Every edge requires different colors at its two ends. The conflict score h(a) counts edges whose endpoints have the same color; h(a)=0 means a solution.

This first demonstration uses guided improving moves to make the shared loop visible. Begin with all vertices red. Press Next to change one variable, inspect the rule results, and repeat. The later methods change how these updates are selected.

The initial score is 5. With the preset choices, two repairs reach scores 2 and then 0. Back revisits a state; Reset returns to the chosen start.

Random sampling draws a fresh total assignment on each attempt, then tests every constraint. It does not repair the previous candidate. A later sample can repeat earlier values by chance.

For the running CSP, (0,1,0) fails X₃<X₁. A later independent sample, (1,2,0), satisfies all three rules. The arrow between these candidates means “sample again”, not “repair one variable”.

In the generic loop, stop() is true immediately, so the inner repair loop is skipped. The outer loop samples, tests and starts again until success or the overall limit.

On a finite CSP, repeated random sampling gives more chances to encounter a solution, but a finite run can miss every solution. The following lab lets you see this directly without calculating probabilities.

Each Next action draws a fresh color for every vertex, then checks all five edge rules. A color may happen to remain the same, but it was sampled again rather than deliberately kept.

Compare successive candidates and their conflict counts. No information from a failed sample guides the next one. A zero score is a solution; exhausting the finite step budget is not a proof that no solution exists.

The seed selects a repeatable sequence of random choices. Changing it gives another run of the same method.

A random walk keeps the current total assignment. At each step it chooses one variable and an allowed replacement value at random, leaving the other values unchanged. In this lab the replacement differs from the current value.

For the running CSP, (0,1,0) has one conflict. Changing X₂ to 0 gives (0,0,0), with two conflicts. Random walk keeps the move because it does not use the score to decide whether to accept it.

In the ideal generic loop, stop() is always false and the walk continues until it finds a solution. A practical run needs a step or time limit so it can finish when unsuccessful. Reaching that limit does not establish that no solution exists.

Next, IBI uses the score to guide its choice of move instead of choosing blindly.

A random-walk step chooses one vertex and a different color at random. All other colors remain unchanged. Unlike random sampling, it follows a sequence of neighboring candidates.

The score is displayed for explanation, but it does not decide whether the move is kept. With the preset seed and plateau start, the scores are 1, then 1, then 0: a sideways move makes a solution reachable. Other seeds can take different routes.

Use Back to inspect a transition and Reset before changing the seed or starting coloring. A run that ends at a positive score has simply failed to find a solution within its budget.

Iterative best improvement (IBI) uses an evaluation function to guide successive changes to a total assignment. Here the score h(a) is the number of constraints violated by assignment a. A score of zero means that every rule is satisfied; a positive score means that repair is unfinished.

The most-improving-step policy examines all allowed one-variable changes and chooses a neighboring assignment with the smallest score. If several neighbors share the minimum, a tie-breaking rule selects one. The strict version used in the plateau demonstration accepts a move only when that minimum is strictly lower than the current score.

For a=(0,1,0), the constraints X₁<2, X₂>0 and X₃<X₁ give h(a)=1. Changing X₁ to 1 yields (1,1,0) with score 0. Changing X₁ to 2 gives score 1 because the unary rule X₁<2 fails. Changing X₂ to 0 gives score 2. The slide displays three of the six one-value changes; the other three, X₂→2, X₃→1 and X₃→2, each have score 1. The unique lowest-score neighbor here is therefore (1,1,0), a solution.

Repeated strict improvements cannot cycle through equal-score candidates because the score decreases on every accepted move. However, stopping with a positive score is not a proof of impossibility. There may be a solution that requires a sideways or temporarily worse move to reach.

The next chapter explains tabu search: its memory changes which moves are allowed, and it may accept a move that does not strictly improve the current score. The following interactive plateau illustrates why escape strategies are needed.

Tabu search remembers recently changed variables and temporarily avoids selecting them again. The number t tells us how many recent changes to remember; it is called the tabu tenure.

For t=2 and memory [X₁,X₃], X₁ and X₃ are temporarily blocked. After changing X₂, the memory becomes [X₃,X₂]: X₁ is available again. These brackets form an ordered memory list.

Choose a low-score move among the allowed variables. Tabu can keep moving even when the best allowed move has an equal or worse score. This may help escape a plateau while reducing immediate reversals. It still may miss a solution in a finite run.

The lab uses this simple rule with t=2, without an exception for recently changed variables.

After the score-guided policy and tabu variant, this example examines the limit of strict IBI. The candidate is complete, but the chosen neighborhood contains no immediately improving move. This is a reason to change the search policy, rather than conclude that the CSP has no solution.

Strict best improvement examines the one-variable neighbors, chooses one with the fewest conflicts, and moves only if its score is strictly smaller than the current score. The strict condition matters: a best-neighbor policy that allows equal or worse moves behaves differently.

The initial coloring is A=red, B=green, C=red, D=blue, with one conflict on A–C. No single recoloring has a score below 1, so strict improvement stops. This is an unresolved plateau, not evidence that the graph cannot be colored.

A sideways move B→blue keeps h(a)=1. After that move, A→green removes the remaining conflict without creating another, and h(a) becomes 0. The explorer demonstrates this two-move path using the same graph and conflict count as the full lab.

A plateau has equal-score neighboring states; a strict local minimum has only higher-score neighbors. Both can stop strict descent before a solution. Allowing sideways moves may help, but uncontrolled equal-score moves can also cycle.

Two escape strategies for local optima are random restarts and random steps. Both address the fact that the best immediate improvement need not lead to a solution. The graph example needs scores 1→1→0, so its first sideways move is forbidden by strict descent.

A random restart discards the current total assignment and samples a new one. Improvement resumes from that different starting point. This can reach a region whose improving paths are more useful, at the cost of giving up the current candidate.

A random step retains the current candidate but occasionally replaces the improvement policy with a random variable/value update. It may preserve or increase the conflict count. On the plateau, one helpful sideways update is B→blue, after which A→green reaches score zero; a random policy is not guaranteed to choose that helpful move.

There is no universally best mixture of improvement, restarts and random steps. Their usefulness depends on the geometry of the candidate space, including where plateaus and local minima occur. A finite unsuccessful run remains inconclusive about whether the CSP has a solution.

Tabu memory limits recent changes. Next, simulated annealing uses temperature to control the probability of accepting a worse move. These are different ways to help search escape a local trap.

The preset plateau has one conflict. Every one-variable neighbor has a score of at least 1, so strict improvement has no permitted improving move and stops. This is a local obstacle, not a proof that the problem has no solution.

Switch Policy to Tabu to keep exploring while avoiding the last two changed variables. It can accept an equal or worse score, which lets it pass through candidates strict improvement would reject.

For a successful strict-improvement example, select All red. The preset run reduces the score from 5 to 2 to 0. Comparing the two starts shows why restarting elsewhere can help.

Both panels deliberately examine the same proposed change. The current candidate a has h(a)=1 conflict. The proposed candidate a′ has h(a′)=2 conflicts. The arrow describes a proposal, not an accepted update; its score increase is Δh=2−1=1.

Temperature T controls the chance of accepting that worse proposal. At higher temperature, acceptance is more likely. If accepted, a′ replaces a and the current score becomes 2. At lower temperature, rejection is more likely. If rejected, the algorithm keeps a and its score remains 1.

Temperature does not alter either candidate’s colors or conflict count. It changes only the acceptance probability. For this worse move and a positive finite temperature, either decision remains possible: high temperature does not guarantee acceptance and low temperature does not guarantee rejection.

Accepting a worse intermediate candidate can help search leave a trap and reach a better candidate later. Better and equal-score proposals are always accepted in this demonstration. The next section gives the acceptance formula.

Let a be the current candidate and a′ the proposed candidate. The prime mark means “proposed”; it does not mean a derivative. Their conflict scores are h(a) and h(a′).

The score change is Δh=h(a′)−h(a), read “new score minus old score”. A negative change is better, zero is equal, and a positive change is worse. Accept better or equal proposals.

For a worse proposal, use probability p=exp(−Δh/T), with positive temperature T. exp(z) means e raised to the power z. You do not need to derive this formula: a larger score increase lowers the chance, while a higher temperature raises it.

To make an accept/reject decision, draw a random number u between 0 and 1. Accept when u<p; otherwise retain the old candidate.

A move from score 1 to score 3 has Δh=2. At T=4 its acceptance chance is about 61%; at T=0.5 it is about 2%. A draw u=0.5 accepts it in the warm case and rejects it in the cool case. The interactive probability lab lets you compare these decisions directly.

Use Δh=2 and u=0.5 to reproduce the hot and cold decisions from the previous slide. At T=4 the probability exceeds the draw, so the move is accepted. At T=0.5 it is below the draw, so the move is rejected.

Next hold temperature fixed and increase Δh. The acceptance curve decreases: a larger worsening is less likely to be accepted. For Δh≤0 the probability is 1, so every permitted draw accepts the proposal.

The displayed draw can be controlled for teaching, whereas a running annealing policy generates draws randomly. A probability of 0.607 is neither a promise that every hot move is accepted nor a score decrease; it describes the proportion of such proposals accepted over repeated independent draws.

An annealing schedule specifies how temperature decreases during a run. Start warm to make exploration easier, then lower T so worse moves become less likely.

In this lab, T starts at 2 and falls a little after every step: approximately 2, 1.84, 1.69, and so on. These values illustrate gradual cooling; memorizing the schedule is not needed to understand the method.

For the same worse proposal, warm search is more willing to move and cool search is more selective. Cooling too fast can leave the algorithm trapped. A finite run may still fail to find a solution.

The next coloring lab starts with annealing selected, then lets you compare it with the other policies on exactly the same problem.

The graph is the same one used in the earlier four demonstrations: variables A,B,C,D, three possible colors, and a different-color rule on each edge. h(a) counts conflicting edges.

Annealing is selected initially. Step through the proposals and check whether each is accepted. A rejected proposal leaves the coloring unchanged. T is temperature, Δh is proposed score minus current score, p is the chance of acceptance, and u is the random test draw; accept when u<p.

Afterward, reset and select another policy to compare. Strict improvement requires a lower score. Random sampling redraws every value. Random walk changes one value without consulting the score. Tabu avoids the last two changed variables while choosing a low-score allowed move.

Keep the start and seed fixed for a repeatable comparison. The seed selects a sequence of random choices, not a better algorithm. The lab stops at a solution or after at most 40 steps; an unsuccessful run is inconclusive.

Generate-and-test and backtracking enumerate assignments in different ways. Over finite domains, exhaustive enumeration finds all solutions or establishes that none exists. Backtracking can avoid completing branches that already violate a rule.

GAC alone processes domains. Empty domains establish impossibility for the current branch; fully consistent singleton domains establish a solution. Nonempty nonsingleton domains are generally inconclusive. Adding exhaustive splitting completes the finite search.

Local search maintains one total candidate and follows a sequence of changes. h(a)=0 verifies a solution, but budget exhaustion generally leaves the satisfiability question open. Local search may be effective on large instances, but speed and success depend on the problem and settings; no blanket comparison makes it universally faster.

Before choosing a method, decide whether you need one feasible assignment, every feasible assignment, or a proof of impossibility. A method’s stopping condition must support the claim you intend to make.

For each question, state your prediction before opening its linked example. Use the assignment lab to distinguish false from pending, and the GAC lab to distinguish domains from total assignments.

For the contradiction, identify a support for each rule and then explain why the witnesses cannot all agree. For annealing, keep the same positive score change while comparing temperatures; this isolates the role of T.

The following slide gives the deductions. Check both your computation and the strength of the conclusion: solution, impossible branch, or unresolved.

With only X₁=1 assigned, X₁ < 2 can be evaluated and is true. X₂ > 0 and X₃ < X₁ remain pending, because their scopes contain unassigned variables.

GAC leaves dom(X₁)={1}, dom(X₂)={1,2} and dom(X₃)={0}. These are domains, not equations assigning sets as variable values. Choosing X₂=1 produces (1,1,0); choosing X₂=2 produces (1,2,0).

The equality/equality/inequality example has support for every value in each constraint taken separately. Globally the equalities imply X₁=X₃, which violates the inequality. GAC therefore stays locally consistent without establishing satisfiability.

For Δh=2, exp(−2/4)=exp(−0.5)≈0.607, and exp(−2/0.5)=exp(−4)≈0.018. This compares acceptance probabilities for the same worsening, not the probability that the whole solver succeeds.

The systematic path models choices, propagates consequences and branches on alternatives. A complete finite exploration, with sound pruning, can enumerate solutions or prove that the problem has none.

The local path starts complete, changes values according to a policy and measures conflicts. Restarts, tabu memory and annealing can allow trajectories that strict descent cannot follow.

Always match the conclusion to the evidence. A verified zero-conflict assignment proves existence. A sound empty domain rejects its branch. Exhaustive rejection proves impossibility. A bounded unsuccessful repair run is inconclusive.

Use the handout to revisit definitions, worked examples and algorithm assumptions. The interactive examples connect each method to its effect on domains or candidate assignments.

For further reading, see Poole and Mackworth, Artificial Intelligence: Foundations of Computational Agents, Chapter 4. Use the live HTML slides for experiments and the handout for the full reasoning and limits of each method.

Explain why disjoint, covering domain splits preserve every alternative, and why separate branch copies are needed. Show the two solutions by choosing each remaining X₂ value.

Use the coloring plateau to explain a sideways move, then use the hot/cold annealing example to distinguish score change, temperature, acceptance probability and a random test draw. Finish by stating precisely what the solver’s observed result proves.