extends object
Creates an instance of CSP. Construct a CSP problem. If variables is empty, it becomes domains.keys().
Return the actions that can be executed in the given state. The result would typically be a list, but if there are many actions, consider yielding them one at a time in an iterator, rather than building them all at once.
Add {var: val} to assignment; Discard the old value if any.
Return a list of variables in current assignment that are in conflict This is for min_conflicts search.
Show a human-readable representation of the CSP. Subclasses can print in a prettier way, or display with a GUI
Return True if the state is a goal. The default method compares the state to self.goal or checks for state in self.goal if it is a list, as specified in the constructor. Override this method if checking against a single self.goal is not enough.
Return the number of conflicts var=val has with other variables.
Return the cost of a solution path that arrives at state2 from state1 via action, assuming cost c to get up to state1. If the problem is such that the path doesn't matter, this function will only look at state2. If the path does matter, it will consider c and maybe state1 and action. The default method costs 1 for every step in the path.
Return the state that results from executing the given action in the given state. The action must be one of self.actions(state).
Remove {var: val} from assignment. DO NOT call this if you are changing a variable to a new value; just call assign for that.
For optimization problems, each state has a value. Hill Climbing and related algorithms try to maximize this value.
This class describes finite-domain Constraint Satisfaction Problems. A CSP is specified by the following inputs: variables A list of variables; each is atomic (e.g. int or string). domains A dict of {var:[possible_value, ...]} entries. neighbors A dict of {var:[var,...]} that for each variable lists the other variables that participate in constraints. constraints A function f(A, a, B, b) that returns true if neighbors A, B satisfy the constraint when they have values A=a, B=b
In the textbook and in most mathematical definitions, the constraints are specified as explicit pairs of allowable values, but the formulation here is easier to express and more compact for most cases (for example, the n-Queens problem can be represented in O(n) space using this notation, instead of O(n^4) for the explicit representation). In terms of describing the CSP as a problem, that's all there is.
However, the class also supports data structures and methods that help you solve CSPs by calling a search function on the CSP. Methods and slots are as follows, where the argument 'a' represents an assignment, which is a dict of {var:val} entries: assign(var, val, a) Assign a[var] = val; do other bookkeeping unassign(var, a) Do del a[var], plus other bookkeeping nconflicts(var, val, a) Return the number of other variables that conflict with var=val curr_domains[var] Slot: remaining consistent values for var Used by constraint propagation routines. The following methods are used only by graph_search and tree_search: actions(state) Return a list of actions result(state, action) Return a successor of state goal_test(state) Return true if all constraints satisfied The following are just for debugging purposes: nassigns Slot: tracks the number of assignments made display(a) Print a human-readable representation
export