In [ ]:
%%HTML
<style>
.container { width:100% }
</style>
The module extractVariables implements the function $\texttt{extractVars}(e)$ that takes a Python expression $e$ as its argument and returns the set of all variables and function names occurring in $e$.
In [ ]:
import extractVariables as ev
The function collect_variables(expr) takes a string expr that can be interpreted as a Python expression as input and collects all variables occurring in expr. It takes care to eliminate the function symbols from the names returned by extract_variables.
In [ ]:
def collect_variables(expr):
return frozenset(var for var in ev.extractVars(expr)
if var not in dir(__builtins__)
)
The function arb(S) takes a set S as input and returns an arbitrary element from
this set.
In [ ]:
def arb(S):
for x in S:
return x
We need the function choice from the module random. Given a list L, random.choice(L) returns a random element from L. In order to have reproducible results, we set the seed for the random number generator.
In [ ]:
import random
random.seed(42)
Given a dictionary A, the function extend(A) returns a dictionary B such that B[key] = value and B[x] = A[x] for all x that are different from key.
In [ ]:
def extend(A, key, value):
B = A.copy()
B[key] = value
return B
The module Set implements sets as
AVL trees.
The API provided by Set offers the following functions and methods:
Set() creates an empty set.S.isEmpty() checks whether the set Sis empty.S.member(x) checks whether x is an element of the set S.S.insert(x) inserts x into the set S.
This does not return a new set but rather modifies the set S.S.delete(x) deletes x from the set S.
This does not return a new set but rather modifies the set S.S.pop() returns the smallest element of the set S.
Furthermore, this element is removed from S.S.pop_last() returns the biggest element of the set S.
Furthermore, this element is removed from S.S.first() returns the smallest element of the set S.S.last() returns the biggest element of the set S.Since sets are implemented as ordered binary trees, the elements of a set need to be comparable, i.e. if x and y are inserted into a set, then the
expression x < y must return a Boolean value and < has to define a
linear order.
The module Set can be used to implement a priority queue that supports the removal of elements.
In [ ]:
import Set
The function cast_to_set(L) returns a set containing all elements from the iterable L.
In [ ]:
def cast_to_Set(L):
Result = Set.Set()
for x in L:
Result.insert(x)
return Result
The procedure solve(P) takes a constraint satisfaction problem
P as input. Here P is a triple of the form
$$ \mathcal{P} = \langle \mathtt{Variables}, \mathtt{Values}, \mathtt{Constraints} \rangle $$
where
The CSP P is solved using local search.
In [ ]:
def solve(P):
Variables, Values, Constraints = P
Variables = list(Variables) # convert to list for random.choice(Variables) to work
Values = list(Values)
Annotated = { (f, collect_variables(f)) for f in Constraints }
Assign = { x: random.choice(Values) for x in Variables }
iteration = 0
lastVar = arb(Variables)
while True:
Conflicts = [ (numConflicts(x, Assign, Annotated), x) for x in Variables
if x != lastVar
]
maxNum, _ = Set.last(cast_to_Set(Conflicts))
if maxNum == 0 and numConflicts(lastVar, Assign, Annotated) == 0:
print(f'Number of iterations: {iteration}')
return Assign
if iteration % 10 == 0: # avoid infinite loop
x = random.choice(Variables)
else: # choose var with max number of conflicts
FaultyVars = [ var for (num, var) in Conflicts if num == maxNum ]
x = random.choice(FaultyVars)
Conflicts = [ (numConflicts(x, extend(Assign, x, val), Annotated), val)
for val in Values
]
if iteration % 10 == 0: # avoid infinite loop
newVal = random.choice(Values)
else:
minNum, _ = Set.first(cast_to_Set(Conflicts))
ValuesForX = [ val for (n, val) in Conflicts if n == minNum ]
newVal = random.choice(ValuesForX)
Assign[x] = newVal
lastVar = x
iteration += 1
The function numConflicts takes three arguments:
x is a variable,Assign is a dictionary mapping variables to values,Annotated is a set of pairs of the form (f, V) where f is a constraint and V is the set of variables occurring in f.The function returns the number of constraints f such that x occurs in f but f is not satisfied.
In [ ]:
def numConflicts(x, Assign, Annotated):
NewAssign = Assign.copy()
return len([ (f, V) for (f, V) in Annotated
if x in V and not eval(f, NewAssign)
])
In [ ]:
%run N-Queens-Problem-CSP.ipynb
In [ ]:
P = create_csp(8)
Local search takes about 22 milliseconds on my desktop to solve the eight queens puzzle.
In [ ]:
%%time
Solution = solve(P)
print(f'Solution = {Solution}')
In [ ]:
show_solution(Solution)
The 50 queens problem can be solved in 5 seconds.
In [ ]:
P = create_csp(50)
In [ ]:
%%time
Solution = solve(P)
In [ ]:
%run Zebra.ipynb
In [ ]:
zebra = zebra_csp()
In [ ]:
%%time
Solution = solve(zebra)
Solving the Zebra Puzzle takes about 7 seconds.
In [ ]:
show_solution(Solution)
In [ ]:
%run Sudoku.ipynb
In [ ]:
csp = sudoku_csp(Sudoku)
csp
Solving the given Sudoku puzzle takes about 1 minute and 30 seconds.
In [ ]:
%%time
Solution = solve(csp)
In [ ]:
show_solution(Solution)
In [ ]:
%run Crypto-Arithmetic.ipynb
In [ ]:
csp = crypto_csp()
Solving the crypto-arithmetic puzzle took about 7 seconds.
In [ ]:
%%time
Solution = solve(csp)
In [ ]:
show_solution(Solution)
In [ ]: