Constraint Satisfaction

CSP (Constraint Satisfaction Problems) problems and solvers. (Chapter 6)

class csp.CSP(variables, domains, neighbors, constraints)

Bases: Problem

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

constraints(A, a, B, b)

Return True if neighbors A, B satisfy the constraint when A=a, B=b. Every call is tallied in self.nchecks, so callers can measure the number of consistency checks performed (e.g. to reproduce the benchmarks in Figure 6.1), just as self.nassigns tallies the assignments made.

assign(var, val, assignment)

Add {var: val} to assignment; Discard the old value if any.

unassign(var, assignment)

Remove {var: val} from assignment. DO NOT call this if you are changing a variable to a new value; just call assign for that.

nconflicts(var, val, assignment)

Return the number of conflicts var=val has with other variables.

count_lost_values(var, val, assignment)

Return how many values would be ruled out in the domains of the unassigned neighbours of var if var were assigned val (the count used by the least-constraining-value heuristic).

display(assignment)

Show a human-readable representation of the CSP.

actions(state)

Return a list of applicable actions: non conflicting assignments to an unassigned variable.

result(state, action)

Perform an action and return the new state.

goal_test(state)

The goal is to assign all variables, with all constraints satisfied.

support_pruning()

Make sure we can prune values from domains. (We want to pay for this only if we use it.)

suppose(var, value)

Start accumulating inferences from assuming var=value.

prune(var, value, removals)

Rule out var=value.

choices(var)

Return all values for var that aren’t currently ruled out.

infer_assignment()

Return the partial assignment implied by the current inferences.

restore(removals)

Undo a supposition and all inferences from it.

conflicted_vars(current)

Return a list of variables in current assignment that are in conflict

csp.no_arc_heuristic(csp, queue)

Return the arc queue unchanged (no ordering heuristic for AC3).

csp.dom_j_up(csp, queue)

Order the arc queue so arcs whose second variable has the smallest current domain are popped first (a SortedSet keyed by the negated domain size).

csp.AC3(csp, queue=None, removals=None, arc_heuristic=<function dom_j_up>)

[Figure 6.3]

csp.revise(csp, Xi, Xj, removals, checks=0)

Return true if we remove a value.

csp.AC3b(csp, queue=None, removals=None, arc_heuristic=<function dom_j_up>)

An improved version of AC3 that uses double-support checks to share work between an arc (Xi, Xj) and its reverse (Xj, Xi). Returns a tuple (is_consistent, checks): False if a domain is wiped out, True if the CSP is made arc-consistent, where checks counts the consistency checks performed.

csp.partition(csp, Xi, Xj, checks=0)

Helper for AC3b: split the domains of Xi and Xj using double-support checks. Returns (Si_p, Sj_p, Sj_u, checks) where Si_p is the set of Xi values supported by Xj, Sj_p the set of Xj values already known to be supported by Xi, Sj_u the remaining (as yet unconfirmed) Xj values, and checks the updated check count.

csp.AC4(csp, queue=None, removals=None, arc_heuristic=<function dom_j_up>)

Enforce arc consistency using AC4, which keeps per-value support counters so that pruning a value only triggers re-checks of the values it supported. Returns a tuple (is_consistent, checks): False if a domain is wiped out, True if the CSP is made arc-consistent, where checks counts the consistency checks performed.

csp.first_unassigned_variable(assignment, csp)

The default variable order.

csp.mrv(assignment, csp)

Minimum-remaining-values heuristic.

csp.num_legal_values(csp, var, assignment)

Return how many values are still legal for var (used by the mrv heuristic): the size of its current domain if pruning is active, otherwise the number of domain values that conflict with no other variable in the assignment.

csp.unordered_domain_values(var, assignment, csp)

The default value order.

csp.lcv(var, assignment, csp)

Least-constraining-values heuristic.

csp.no_inference(csp, var, value, assignment, removals)

The default inference step for backtracking: do nothing and always succeed.

csp.forward_checking(csp, var, value, assignment, removals)

Prune neighbor values inconsistent with var=value.

csp.mac(csp, var, value, assignment, removals, constraint_propagation=<function AC3b>)

Maintain arc consistency.

csp.backtracking_search(csp, select_unassigned_variable=<function first_unassigned_variable>, order_domain_values=<function unordered_domain_values>, inference=<function no_inference>)

[Figure 6.5]

csp.min_conflicts(csp, max_steps=100000)

Solve a CSP by stochastic Hill Climbing on the number of conflicts.

csp.min_conflicts_value(csp, var, current)

Return the value that will give var the least number of conflicts. If there is a tie, choose at random.

csp.tree_csp_solver(csp)

[Figure 6.11]

csp.topological_sort(X, root)

Returns the topological sort of X starting from the root.

Input: X is a list with the nodes of the graph N is the dictionary with the neighbors of each node root denotes the root of the graph.

Output: stack is a list with the nodes topologically sorted parents is a dictionary pointing to each node’s parent

Other: visited shows the state (visited - not visited) of nodes

csp.build_topological(node, parent, neighbors, visited, stack, parents)

Build the topological sort and the parents of each node in the graph.

csp.make_arc_consistent(Xj, Xk, csp)

Make arc between parent (Xj) and child (Xk) consistent under the csp’s constraints, by removing the possible values of Xj that cause inconsistencies.

csp.assign_value(Xj, Xk, csp, assignment)

Assign a value to Xk given Xj’s (Xk’s parent) assignment. Return the first value that satisfies the constraints.

class csp.UniversalDict(value)

Bases: object

A universal dict maps any key to the same value. We use it here as the domains dict for CSPs in which all variables have the same domain. >>> d = UniversalDict(42) >>> d[‘life’] 42

csp.different_values_constraint(A, a, B, b)

A constraint saying two neighboring variables must differ in value.

csp.MapColoringCSP(colors, neighbors)

Make a CSP for the problem of coloring a map with different colors for any two adjacent regions. Arguments are a list of colors, and a dict of {region: [neighbor,…]} entries. This dict may also be specified as a string of the form defined by parse_neighbors.

csp.parse_neighbors(neighbors)

Convert a string of the form ‘X: Y Z; Y: Z’ into a dict mapping regions to neighbors. The syntax is a region name followed by a ‘:’ followed by zero or more region names, followed by ‘;’, repeated for each region name. If you say ‘X: Y’ you don’t need ‘Y: X’. >>> parse_neighbors(‘X: Y Z; Y: Z’) == {‘Y’: [‘X’, ‘Z’], ‘X’: [‘Y’, ‘Z’], ‘Z’: [‘X’, ‘Y’]} True

csp.queen_constraint(A, a, B, b)

Constraint is satisfied (true) if A, B are really the same variable, or if they are not in the same row, down diagonal, or up diagonal.

class csp.NQueensCSP(n)

Bases: CSP

Make a CSP for the nQueens problem for search with min_conflicts. Suitable for large n, it uses only data structures of size O(n). Think of placing queens one per column, from left to right. That means position (x, y) represents (var, val) in the CSP. The main structures are three arrays to count queens that could conflict:

rows[i]      Number of queens in the ith row (i.e. val == i)
downs[i]     Number of queens in the \ diagonal
             such that their (x, y) coordinates sum to i
ups[i]       Number of queens in the / diagonal
             such that their (x, y) coordinates have x-y+n-1 = i

We increment/decrement these counts each time a queen is placed/moved from a row/diagonal. So moving is O(1), as is nconflicts. But choosing a variable, and a best value for the variable, are each O(n). If you want, you can keep track of conflicted variables, then variable selection will also be O(1).

>>> len(backtracking_search(NQueensCSP(8)))
8

nconflicts(var, val, assignment)

The number of conflicts, as recorded with each assignment. Count conflicts in row and in up, down diagonals. If there is a queen there, it can’t conflict with itself, so subtract 3.

assign(var, val, assignment)

Assign var, and keep track of conflicts.

unassign(var, assignment)

Remove var from assignment (if it is there) and track conflicts.

record_conflict(assignment, var, val, delta)

Record conflicts caused by addition or deletion of a Queen.

display(assignment)

Print the queens and the nconflicts values (for debugging).

csp.flatten(seqs)

Concatenate a sequence of lists into a single flat list.

class csp.Sudoku(grid)

Bases: CSP

A Sudoku problem. The box grid is a 3x3 array of boxes, each a 3x3 array of cells. Each cell holds a digit in 1..9. In each box, all digits are different; the same for each row and column as a 9x9 grid. >>> e = Sudoku(easy1) >>> e.display(e.infer_assignment()) . . 3 | . 2 . | 6 . . 9 . . | 3 . 5 | . . 1 . . 1 | 8 . 6 | 4 . . ——+——-+—— . . 8 | 1 . 2 | 9 . . 7 . . | … | . . 8 . . 6 | 7 . 8 | 2 . . ——+——-+—— . . 2 | 6 . 9 | 5 . . 8 . . | 2 . 3 | . . 9 . . 5 | . 1 . | 3 . . >>> AC3(e) # doctest: +ELLIPSIS (True, …) >>> e.display(e.infer_assignment()) 4 8 3 | 9 2 1 | 6 5 7 9 6 7 | 3 4 5 | 8 2 1 2 5 1 | 8 7 6 | 4 9 3 ——+——-+—— 5 4 8 | 1 3 2 | 9 7 6 7 2 9 | 5 6 4 | 1 3 8 1 3 6 | 7 9 8 | 2 4 5 ——+——-+—— 3 7 2 | 6 8 9 | 5 1 4 8 1 4 | 2 5 3 | 7 6 9 6 9 5 | 4 1 7 | 3 8 2 >>> h = Sudoku(harder1) >>> backtracking_search(h, select_unassigned_variable=mrv, inference=forward_checking) is not None True

R3 = [0, 1, 2]

Cell()

Implement next(self).

bgrid = [[[[0, 1, 2], [3, 4, 5], [6, 7, 8]], [[9, 10, 11], [12, 13, 14], [15, 16, 17]], [[18, 19, 20], [21, 22, 23], [24, 25, 26]]], [[[27, 28, 29], [30, 31, 32], [33, 34, 35]], [[36, 37, 38], [39, 40, 41], [42, 43, 44]], [[45, 46, 47], [48, 49, 50], [51, 52, 53]]], [[[54, 55, 56], [57, 58, 59], [60, 61, 62]], [[63, 64, 65], [66, 67, 68], [69, 70, 71]], [[72, 73, 74], [75, 76, 77], [78, 79, 80]]]]

boxes = [[0, 1, 2, 3, 4, 5, 6, 7, 8], [9, 10, 11, 12, 13, 14, 15, 16, 17], [18, 19, 20, 21, 22, 23, 24, 25, 26], [27, 28, 29, 30, 31, 32, 33, 34, 35], [36, 37, 38, 39, 40, 41, 42, 43, 44], [45, 46, 47, 48, 49, 50, 51, 52, 53], [54, 55, 56, 57, 58, 59, 60, 61, 62], [63, 64, 65, 66, 67, 68, 69, 70, 71], [72, 73, 74, 75, 76, 77, 78, 79, 80]]

rows = [[0, 1, 2, 9, 10, 11, 18, 19, 20], [3, 4, 5, 12, 13, 14, 21, 22, 23], [6, 7, 8, 15, 16, 17, 24, 25, 26], [27, 28, 29, 36, 37, 38, 45, 46, 47], [30, 31, 32, 39, 40, 41, 48, 49, 50], [33, 34, 35, 42, 43, 44, 51, 52, 53], [54, 55, 56, 63, 64, 65, 72, 73, 74], [57, 58, 59, 66, 67, 68, 75, 76, 77], [60, 61, 62, 69, 70, 71, 78, 79, 80]]

cols = [(0, 3, 6, 27, 30, 33, 54, 57, 60), (1, 4, 7, 28, 31, 34, 55, 58, 61), (2, 5, 8, 29, 32, 35, 56, 59, 62), (9, 12, 15, 36, 39, 42, 63, 66, 69), (10, 13, 16, 37, 40, 43, 64, 67, 70), (11, 14, 17, 38, 41, 44, 65, 68, 71), (18, 21, 24, 45, 48, 51, 72, 75, 78), (19, 22, 25, 46, 49, 52, 73, 76, 79), (20, 23, 26, 47, 50, 53, 74, 77, 80)]

neighbors = {0: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 18, 19, 20, 27, 30, 33, 54, 57, 60}, 1: {0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 18, 19, 20, 28, 31, 34, 55, 58, 61}, 2: {0, 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 18, 19, 20, 29, 32, 35, 56, 59, 62}, 3: {0, 1, 2, 4, 5, 6, 7, 8, 12, 13, 14, 21, 22, 23, 27, 30, 33, 54, 57, 60}, 4: {0, 1, 2, 3, 5, 6, 7, 8, 12, 13, 14, 21, 22, 23, 28, 31, 34, 55, 58, 61}, 5: {0, 1, 2, 3, 4, 6, 7, 8, 12, 13, 14, 21, 22, 23, 29, 32, 35, 56, 59, 62}, 6: {0, 1, 2, 3, 4, 5, 7, 8, 15, 16, 17, 24, 25, 26, 27, 30, 33, 54, 57, 60}, 7: {0, 1, 2, 3, 4, 5, 6, 8, 15, 16, 17, 24, 25, 26, 28, 31, 34, 55, 58, 61}, 8: {0, 1, 2, 3, 4, 5, 6, 7, 15, 16, 17, 24, 25, 26, 29, 32, 35, 56, 59, 62}, 9: {0, 1, 2, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 36, 39, 42, 63, 66, 69}, 10: {0, 1, 2, 9, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 37, 40, 43, 64, 67, 70}, 11: {0, 1, 2, 9, 10, 12, 13, 14, 15, 16, 17, 18, 19, 20, 38, 41, 44, 65, 68, 71}, 12: {3, 4, 5, 9, 10, 11, 13, 14, 15, 16, 17, 21, 22, 23, 36, 39, 42, 63, 66, 69}, 13: {3, 4, 5, 9, 10, 11, 12, 14, 15, 16, 17, 21, 22, 23, 37, 40, 43, 64, 67, 70}, 14: {3, 4, 5, 9, 10, 11, 12, 13, 15, 16, 17, 21, 22, 23, 38, 41, 44, 65, 68, 71}, 15: {6, 7, 8, 9, 10, 11, 12, 13, 14, 16, 17, 24, 25, 26, 36, 39, 42, 63, 66, 69}, 16: {6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 17, 24, 25, 26, 37, 40, 43, 64, 67, 70}, 17: {6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 24, 25, 26, 38, 41, 44, 65, 68, 71}, 18: {0, 1, 2, 9, 10, 11, 19, 20, 21, 22, 23, 24, 25, 26, 45, 48, 51, 72, 75, 78}, 19: {0, 1, 2, 9, 10, 11, 18, 20, 21, 22, 23, 24, 25, 26, 46, 49, 52, 73, 76, 79}, 20: {0, 1, 2, 9, 10, 11, 18, 19, 21, 22, 23, 24, 25, 26, 47, 50, 53, 74, 77, 80}, 21: {3, 4, 5, 12, 13, 14, 18, 19, 20, 22, 23, 24, 25, 26, 45, 48, 51, 72, 75, 78}, 22: {3, 4, 5, 12, 13, 14, 18, 19, 20, 21, 23, 24, 25, 26, 46, 49, 52, 73, 76, 79}, 23: {3, 4, 5, 12, 13, 14, 18, 19, 20, 21, 22, 24, 25, 26, 47, 50, 53, 74, 77, 80}, 24: {6, 7, 8, 15, 16, 17, 18, 19, 20, 21, 22, 23, 25, 26, 45, 48, 51, 72, 75, 78}, 25: {6, 7, 8, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 26, 46, 49, 52, 73, 76, 79}, 26: {6, 7, 8, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 47, 50, 53, 74, 77, 80}, 27: {0, 3, 6, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 45, 46, 47, 54, 57, 60}, 28: {1, 4, 7, 27, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 45, 46, 47, 55, 58, 61}, 29: {2, 5, 8, 27, 28, 30, 31, 32, 33, 34, 35, 36, 37, 38, 45, 46, 47, 56, 59, 62}, 30: {0, 3, 6, 27, 28, 29, 31, 32, 33, 34, 35, 39, 40, 41, 48, 49, 50, 54, 57, 60}, 31: {1, 4, 7, 27, 28, 29, 30, 32, 33, 34, 35, 39, 40, 41, 48, 49, 50, 55, 58, 61}, 32: {2, 5, 8, 27, 28, 29, 30, 31, 33, 34, 35, 39, 40, 41, 48, 49, 50, 56, 59, 62}, 33: {0, 3, 6, 27, 28, 29, 30, 31, 32, 34, 35, 42, 43, 44, 51, 52, 53, 54, 57, 60}, 34: {1, 4, 7, 27, 28, 29, 30, 31, 32, 33, 35, 42, 43, 44, 51, 52, 53, 55, 58, 61}, 35: {2, 5, 8, 27, 28, 29, 30, 31, 32, 33, 34, 42, 43, 44, 51, 52, 53, 56, 59, 62}, 36: {9, 12, 15, 27, 28, 29, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 63, 66, 69}, 37: {10, 13, 16, 27, 28, 29, 36, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 64, 67, 70}, 38: {11, 14, 17, 27, 28, 29, 36, 37, 39, 40, 41, 42, 43, 44, 45, 46, 47, 65, 68, 71}, 39: {9, 12, 15, 30, 31, 32, 36, 37, 38, 40, 41, 42, 43, 44, 48, 49, 50, 63, 66, 69}, 40: {10, 13, 16, 30, 31, 32, 36, 37, 38, 39, 41, 42, 43, 44, 48, 49, 50, 64, 67, 70}, 41: {11, 14, 17, 30, 31, 32, 36, 37, 38, 39, 40, 42, 43, 44, 48, 49, 50, 65, 68, 71}, 42: {9, 12, 15, 33, 34, 35, 36, 37, 38, 39, 40, 41, 43, 44, 51, 52, 53, 63, 66, 69}, 43: {10, 13, 16, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 44, 51, 52, 53, 64, 67, 70}, 44: {11, 14, 17, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 51, 52, 53, 65, 68, 71}, 45: {18, 21, 24, 27, 28, 29, 36, 37, 38, 46, 47, 48, 49, 50, 51, 52, 53, 72, 75, 78}, 46: {19, 22, 25, 27, 28, 29, 36, 37, 38, 45, 47, 48, 49, 50, 51, 52, 53, 73, 76, 79}, 47: {20, 23, 26, 27, 28, 29, 36, 37, 38, 45, 46, 48, 49, 50, 51, 52, 53, 74, 77, 80}, 48: {18, 21, 24, 30, 31, 32, 39, 40, 41, 45, 46, 47, 49, 50, 51, 52, 53, 72, 75, 78}, 49: {19, 22, 25, 30, 31, 32, 39, 40, 41, 45, 46, 47, 48, 50, 51, 52, 53, 73, 76, 79}, 50: {20, 23, 26, 30, 31, 32, 39, 40, 41, 45, 46, 47, 48, 49, 51, 52, 53, 74, 77, 80}, 51: {18, 21, 24, 33, 34, 35, 42, 43, 44, 45, 46, 47, 48, 49, 50, 52, 53, 72, 75, 78}, 52: {19, 22, 25, 33, 34, 35, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 53, 73, 76, 79}, 53: {20, 23, 26, 33, 34, 35, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 74, 77, 80}, 54: {0, 3, 6, 27, 30, 33, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 72, 73, 74}, 55: {1, 4, 7, 28, 31, 34, 54, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 72, 73, 74}, 56: {2, 5, 8, 29, 32, 35, 54, 55, 57, 58, 59, 60, 61, 62, 63, 64, 65, 72, 73, 74}, 57: {0, 3, 6, 27, 30, 33, 54, 55, 56, 58, 59, 60, 61, 62, 66, 67, 68, 75, 76, 77}, 58: {1, 4, 7, 28, 31, 34, 54, 55, 56, 57, 59, 60, 61, 62, 66, 67, 68, 75, 76, 77}, 59: {2, 5, 8, 29, 32, 35, 54, 55, 56, 57, 58, 60, 61, 62, 66, 67, 68, 75, 76, 77}, 60: {0, 3, 6, 27, 30, 33, 54, 55, 56, 57, 58, 59, 61, 62, 69, 70, 71, 78, 79, 80}, 61: {1, 4, 7, 28, 31, 34, 54, 55, 56, 57, 58, 59, 60, 62, 69, 70, 71, 78, 79, 80}, 62: {2, 5, 8, 29, 32, 35, 54, 55, 56, 57, 58, 59, 60, 61, 69, 70, 71, 78, 79, 80}, 63: {9, 12, 15, 36, 39, 42, 54, 55, 56, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74}, 64: {10, 13, 16, 37, 40, 43, 54, 55, 56, 63, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74}, 65: {11, 14, 17, 38, 41, 44, 54, 55, 56, 63, 64, 66, 67, 68, 69, 70, 71, 72, 73, 74}, 66: {9, 12, 15, 36, 39, 42, 57, 58, 59, 63, 64, 65, 67, 68, 69, 70, 71, 75, 76, 77}, 67: {10, 13, 16, 37, 40, 43, 57, 58, 59, 63, 64, 65, 66, 68, 69, 70, 71, 75, 76, 77}, 68: {11, 14, 17, 38, 41, 44, 57, 58, 59, 63, 64, 65, 66, 67, 69, 70, 71, 75, 76, 77}, 69: {9, 12, 15, 36, 39, 42, 60, 61, 62, 63, 64, 65, 66, 67, 68, 70, 71, 78, 79, 80}, 70: {10, 13, 16, 37, 40, 43, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 71, 78, 79, 80}, 71: {11, 14, 17, 38, 41, 44, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 78, 79, 80}, 72: {18, 21, 24, 45, 48, 51, 54, 55, 56, 63, 64, 65, 73, 74, 75, 76, 77, 78, 79, 80}, 73: {19, 22, 25, 46, 49, 52, 54, 55, 56, 63, 64, 65, 72, 74, 75, 76, 77, 78, 79, 80}, 74: {20, 23, 26, 47, 50, 53, 54, 55, 56, 63, 64, 65, 72, 73, 75, 76, 77, 78, 79, 80}, 75: {18, 21, 24, 45, 48, 51, 57, 58, 59, 66, 67, 68, 72, 73, 74, 76, 77, 78, 79, 80}, 76: {19, 22, 25, 46, 49, 52, 57, 58, 59, 66, 67, 68, 72, 73, 74, 75, 77, 78, 79, 80}, 77: {20, 23, 26, 47, 50, 53, 57, 58, 59, 66, 67, 68, 72, 73, 74, 75, 76, 78, 79, 80}, 78: {18, 21, 24, 45, 48, 51, 60, 61, 62, 69, 70, 71, 72, 73, 74, 75, 76, 77, 79, 80}, 79: {19, 22, 25, 46, 49, 52, 60, 61, 62, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 80}, 80: {20, 23, 26, 47, 50, 53, 60, 61, 62, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79}}

display(assignment)

Print the Sudoku grid for the given assignment as a 9x9 board.

csp.Zebra()

Return an instance of the Zebra Puzzle.

csp.solve_zebra(algorithm=<function min_conflicts>, **args)

Solve the Zebra Puzzle with the given CSP algorithm, print which person is in each house, and return a tuple (zebra_owner_house, water_drinker_house, nassigns, full_assignment).

class csp.NaryCSP(domains, constraints)

Bases: object

A nary-CSP consists of: domains : a dictionary that maps each variable to its domain constraints : a list of constraints variables : a set of variables var_to_const: a variable to set of constraints dictionary

display(assignment=None)

More detailed string representation of CSP

consistent(assignment)

assignment is a variable:value dictionary

returns True if all of the constraints that can be evaluated evaluate to True given assignment.

class csp.Constraint(scope, condition)

Bases: object

A Constraint consists of: scope : a tuple of variables condition: a function that can applied to a tuple of values for the variables.

holds(assignment)

Returns the value of Constraint con evaluated in assignment.

precondition: all variables are assigned in assignment

csp.all_diff_constraint(*values)

Returns True if all values are different, False otherwise

csp.is_word_constraint(words)

Returns True if the letters concatenated form a word in words, False otherwise

csp.meet_at_constraint(p1, p2)

Returns a function that is True when the words meet at the positions (p1, p2), False otherwise

csp.adjacent_constraint(x, y)

Returns True if x and y are adjacent numbers, False otherwise

csp.sum_constraint(n)

Returns a function that is True when the the sum of all values is n, False otherwise

csp.is_constraint(val)

Returns a function that is True when x is equal to val, False otherwise

csp.ne_constraint(val)

Returns a function that is True when x is not equal to val, False otherwise

csp.no_heuristic(to_do)

Return the to_do arc set unchanged (no ordering heuristic for GAC).

csp.sat_up(to_do)

Order the to_do arc set so that (variable, constraint) pairs whose constraint has the smallest scope are processed first (a SortedSet keyed by 1 / scope size).

class csp.ACSolver(csp)

Bases: object

Solves a CSP with arc consistency and domain splitting

GAC(orig_domains=None, to_do=None, arc_heuristic=<function sat_up>)

Makes this CSP arc-consistent using Generalized Arc Consistency orig_domains: is the original domains to_do : is a set of (variable,constraint) pairs returns the reduced domains (an arc-consistent variable:domain dictionary)

new_to_do(var, const)

Returns new elements to be added to to_do after assigning variable var in constraint const.

any_holds(domains, const, env, other_vars, ind=0, checks=0)

Returns True if Constraint const holds for an assignment that extends env with the variables in other_vars[ind:] env is a dictionary Warning: this has side effects and changes the elements of env

domain_splitting(domains=None, to_do=None, arc_heuristic=<function sat_up>)

Return a solution to the current CSP or False if there are no solutions to_do is the list of arcs to check

csp.partition_domain(dom)

Partitions domain dom into two

class csp.ACSearchSolver(csp, arc_heuristic=<function sat_up>)

Bases: Problem

A search problem with arc consistency and domain splitting A node is a CSP

goal_test(node)

Node is a goal if all domains have 1 element

actions(state)

Return the successor states obtained by splitting some still-multi-valued variable’s domain in two and enforcing GAC on each half; only arc-consistent results are kept.

result(state, action)

Return the successor state, which is just the chosen reduced domains.

csp.ac_solver(csp, arc_heuristic=<function sat_up>)

Arc consistency (domain splitting interface)

csp.ac_search_solver(csp, arc_heuristic=<function sat_up>)

Arc consistency (search interface)

class csp.Crossword(puzzle, words)

Bases: NaryCSP

An n-ary CSP for a crossword puzzle. The puzzle is a grid where ‘_’ marks a writable cell and ‘*’ a blocked cell; each maximal run of two or more cells (across or down) becomes a variable sequence constrained to spell one of the given words.

display(assignment=None)

Print the crossword grid, filling in letters from assignment where known.

class csp.Kakuro(puzzle)

Bases: NaryCSP

An n-ary CSP for a Kakuro puzzle. Each ‘_’ cell is a variable with domain 1..9; every horizontal or vertical run of cells must contain distinct digits that sum to the clue given in the adjacent ‘[down, right]’ header cell.

display(assignment=None)

Print the Kakuro grid, showing clue cells and filling in digits from assignment where known.