Lab 4 2014
From 6.034 Wiki
(Difference between revisions)
| Line 14: | Line 14: | ||
== Constraint Satisfaction Problems == | == Constraint Satisfaction Problems == | ||
| - | Your task here is simple. Complete the implementation of a simple constraint satisfaction problem solver! | + | Your task here is simple. Complete the implementation of a simple constraint satisfaction problem solver! Then test it on |
| - | problems you've seen worked out in the class. I | + | problems you've seen worked out in the class. I could just imagine your excitement and anticipation already! |
| - | We have provided you a basic CSP implementation in <tt>csp.py</tt>. Your job is to use your | + | We have provided you a basic CSP implementation in <tt>csp.py</tt>. Your job is to use your understanding of the algorithms you've learned to complete the implementation. |
| - | understanding of the | + | |
You will need to fill in | You will need to fill in | ||
| Line 35: | Line 34: | ||
# Let X be the variable currently being assigned. | # Let X be the variable currently being assigned. | ||
# Let x be the value being assigned to X. | # Let x be the value being assigned to X. | ||
| - | # Finds all the binary constraints that | + | # Finds all the binary constraints that are associated with X. |
| - | # For each neighbor variable, Y, connected to X by a binary constraint. | + | # For each constraint |
| - | ## For each y in Y's domain | + | |
| - | ### If constraint fails for X=x and Y=y | + | ## For each neighbor variable, Y, connected to X by a binary constraint. |
| - | #### Remove y from Y's domain | + | ### For each variable value y in Y's domain |
| - | ### If the domain of Y is reduced down to the empty set, then the check fails. | + | #### If constraint checking fails for X=x and Y=y |
| - | # If all constraints passed declare success | + | ##### Remove y from Y's domain |
| + | #### If the domain of Y is reduced down to the empty set, then the entire check fails return False. | ||
| + | # If all constraints passed declare success and return True | ||
=== Forward Checking with Propagation through Singletons === | === Forward Checking with Propagation through Singletons === | ||
| Line 49: | Line 50: | ||
# For each singleton variable in the queue | # For each singleton variable in the queue | ||
## Finds all the binary constraints that singleton X is associated with. | ## Finds all the binary constraints that singleton X is associated with. | ||
| + | ## For each constraint | ||
### For each neighbor variable, Y, connected to X by a binary constraint. | ### For each neighbor variable, Y, connected to X by a binary constraint. | ||
#### For each value of y in Y's domain | #### For each value of y in Y's domain | ||
| - | ##### If constraint fails for X = (X's singleton value) and Y = y | + | ##### If constraint check fails for X = (X's singleton value) and Y = y |
###### Remove y from the domain of Y for values | ###### Remove y from the domain of Y for values | ||
| - | ##### If the domain of Y is reduced down to the empty set, then check fails. | + | ##### If the domain of Y is reduced down to the empty set, then the entire check fails return False. |
| - | # Check if new singletons are introduced | + | ## Check if new unvisited singletons are introduced; if so add them to your queue. |
| - | # Stop when there are no more singletons. | + | ## Stop when there are no more singletons. |
=== Useful Functions === | === Useful Functions === | ||
Revision as of 02:31, 23 October 2010
This problem set is due Friday, November 5th. If you have questions about it, ask the list 6034tas@csail.mit.edu.
