Answers.Body: <p>You want Chapter 6 of Russell &amp; Norvig's <a href="http://aima.cs.berkeley.edu/" rel="nofollow noreferrer">AI: A Modern Approach</a>, for a starting place.</p>
  
  <p>The goal of a constraint solver is to find an assignment of <em>values</em> to <em>variables</em> such that every variable is assigned a value, but none of a list of <em>constraints</em> are violated.</p>
  
  <p>An example problem that a constraint solver can solve is the problem of assigning students to groups for a project. The variables are the names of the students. Each variable has a set of possible values it could take on that correspond to the names of the groups. The constraints prohibit assigning certain students to the same group (perhaps they hate each other), or require certain students to be assigned to the same group (perhaps they like each other). More complex constraints are also possible (e.g. at least 2 of these 5 students need to be in the same group).</p>
  
  <p>Constraint propagation is the idea that several constraints might logically imply a stronger constraint. As a simple example, suppose that student <span class="math-container">$S$</span> must be assigned to group <span class="math-container">$1$</span>. That's one constraint. Suppose further that student <span class="math-container">$T$</span> must be assigned to the same group as <span class="math-container">$S$</span>. That's another constraint. Together, however, they imply that <span class="math-container">$T$</span> must be assigned to group <span class="math-container">$1$</span>. </p>
  
  <p>Most constraint solvers operate by iteratively trying to assign values to variables and then backtracking when a constraint is violated. When assignments are made, different constraint propagation methods make different decisions about how much computational effort to spend deriving the logical consequences of constraints, as opposed to simply trying more assignments of values to variables until the consequences become apparent (one of the existing constraints gets violated). </p>
  
  <p>The simplest form of constraint propagation is called <a href="https://ktiml.mff.cuni.cz/~bartak/constraints/propagation.html" rel="nofollow noreferrer">forward checking</a>. After each speculative assignment of a value to a variable, forward checking looks at all the constraints the variable is involved in. It then derives the logical consequences of the assignments. For example, continuing with the student problem from above, if <span class="math-container">$S$</span> was assigned value <span class="math-container">$1$</span>, then forward checking would notice the constraint <span class="math-container">$S=T$</span>, and would, effectively, add the constraint <span class="math-container">$T=1$</span> (it actually does something a little different, but it has this effect). As another example, if the assignment <span class="math-container">$T=2$</span> were made, forward checking would notice that <span class="math-container">$S=T$</span>, and would add the constraint <span class="math-container">$S=2$</span>. It would also detect the contradiction that <span class="math-container">$S=1$</span> and <span class="math-container">$S=2$</span> are both constraints, and would declare the assignment <span class="math-container">$T=2$</span> invalid. </p>
  
  <p>More advanced constraint propagation methods can reason about these kinds of logical consequences <em>before</em> assignment are made. For example, they could derive that <span class="math-container">$T=1$</span> before the program starts. Wikipedia has a good summary of these, starting with <a href="https://en.wikipedia.org/wiki/Local_consistency#Arc_consistency" rel="nofollow noreferrer">arc consistency</a>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-04-25T03:15:33.720Z
Answers.LastActivityDate: 2019-04-25T03:15:33.720Z
Answers.UserDisplayName: John Doucette
Body: <p>What is the goal of a constraint solver? How are constraints propagated in a constraint satisfaction search?</p>
  
  <p>Any references are also appreciated. </p>
  
Tags: <definitions><constraint-satisfaction-problems>
Title: What is the goal of a constraint solver?
UserDisplayName: Lexi
ThreadText: # What is the goal of a constraint solver?
  
  (Asked by: username_0 on 2019-04-25)
  
  What is the goal of a constraint solver? How are constraints propagated in a constraint satisfaction search?
  
  Any references are also appreciated.
  
  **Tags:** definitions, constraint-satisfaction-problems
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-04-25. Score: 2
  
  You want Chapter 6 of Russell & Norvig's [AI: A Modern Approach](http://aima.cs.berkeley.edu/), for a starting place.
  
  The goal of a constraint solver is to find an assignment of *values* to *variables* such that every variable is assigned a value, but none of a list of *constraints* are violated.
  
  An example problem that a constraint solver can solve is the problem of assigning students to groups for a project. The variables are the names of the students. Each variable has a set of possible values it could take on that correspond to the names of the groups. The constraints prohibit assigning certain students to the same group (perhaps they hate each other), or require certain students to be assigned to the same group (perhaps they like each other). More complex constraints are also possible (e.g. at least 2 of these 5 students need to be in the same group).
  
  Constraint propagation is the idea that several constraints might logically imply a stronger constraint. As a simple example, suppose that student $S$ must be assigned to group $1$. That's one constraint. Suppose further that student $T$ must be assigned to the same group as $S$. That's another constraint. Together, however, they imply that $T$ must be assigned to group $1$.
  
  Most constraint solvers operate by iteratively trying to assign values to variables and then backtracking when a constraint is violated. When assignments are made, different constraint propagation methods make different decisions about how much computational effort to spend deriving the logical consequences of constraints, as opposed to simply trying more assignments of values to variables until the consequences become apparent (one of the existing constraints gets violated).
  
  The simplest form of constraint propagation is called [forward checking](https://ktiml.mff.cuni.cz/~bartak/constraints/propagation.html). After each speculative assignment of a value to a variable, forward checking looks at all the constraints the variable is involved in. It then derives the logical consequences of the assignments. For example, continuing with the student problem from above, if $S$ was assigned value $1$, then forward checking would notice the constraint $S=T$, and would, effectively, add the constraint $T=1$ (it actually does something a little different, but it has this effect). As another example, if the assignment $T=2$ were made, forward checking would notice that $S=T$, and would add the constraint $S=2$. It would also detect the contradiction that $S=1$ and $S=2$ are both constraints, and would declare the assignment $T=2$ invalid.
  
  More advanced constraint propagation methods can reason about these kinds of logical consequences *before* assignment are made. For example, they could derive that $T=1$ before the program starts. Wikipedia has a good summary of these, starting with [arc consistency](https://en.wikipedia.org/wiki/Local_consistency#Arc_consistency).
  
  
  ---
  
  