import os
os.getenv('PYTHONHASHSEED')

assert hash("test") == 4418353137104490830, "You python hash seed is not correct, results might differ"

"""
Explanation: If we want to have reproducible results, the environment variable PYTHONHASHSEED has to be set to a fixed value, for example to 0.
Below we check that this environment is set so that results are reproducible.
In order to set this variable we have to use the following sequence of commands in the anaconda shell.
conda activate ai
conda env config vars set PYTHONHASHSEED=0
conda activate ai
It is necessary to reactivate the environment ai for the setting to take effect.
End of explanation
"""


import ast

"""
Explanation: A Backtracking Solver with Constraint Propagation
Utility Functions
End of explanation
"""


def collect_variables(expression): 
    tree      = ast.parse(expression)
    Variables = { node.id for node in ast.walk(tree) 
                          if  isinstance(node, ast.Name) 
                          if node.id not in dir(__builtins__)
                }
    return frozenset(Variables)

"""
Explanation: 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.
End of explanation
"""


def arb(S):
    for x in S:
        return x

"""
Explanation: The function arb(S) takes a set S as input and returns an arbitrary element from 
this set.
End of explanation
"""


class Backtrack(Exception):
    pass

"""
Explanation: Backtracking is simulated by raising the Backtrack exception.  We define this new class of exceptions so that we can distinguish Backtrack exceptions from ordinary exceptions.  This is done by creating a new, empty class that is derived from the class Exception.
End of explanation
"""


def union(L):
    return { x for S in L
               for x in S
           }

union([ {1, 2}, {'a', 'b'}, {1, 'a'} ])

"""
Explanation: Given a list of sets L, the function union(L) returns the set of all elements occurring in some set $S$ that is itself a member of the list L, i.e. we have
$$ \texttt{union}(L) = { x \mid \exists S \in L : x \in L }. $$
End of explanation
"""


def solve(P, lcv=False):
    Variables, Values, Constraints = P 
    VarsInConstrs  = union([ collect_variables(f) for f in Constraints ])
    MisspelledVars = (VarsInConstrs - Variables) | (Variables - VarsInConstrs)
    if len(MisspelledVars) > 0:
        print('Did you misspell any of the following Variables?')
        for v in MisspelledVars:
            print(v)
    Annotated    = { (f, collect_variables(f)) for f in Constraints }
    ValuesPerVar = { v: Values for v in Variables }
    UnaryConstrs = { (f, V) for f, V in Annotated if  len(V) == 1 }
    OtherConstrs = { (f, V) for f, V in Annotated if  len(V) >= 2 }
    try:
        for f, V in UnaryConstrs:
            var = arb(V)
            ValuesPerVar[var] = solve_unary(f, var, ValuesPerVar[var])
        return backtrack_search({}, ValuesPerVar, OtherConstrs, lcv)
    except Backtrack:
        return None

"""
Explanation: The Constraint Propagation Solver
The procedure solve(P, lcv=False) takes two arguments:
* P is a constraint satisfaction problem, i.e. P is a triple of the form 
   $$ \mathtt{P} = \langle \mathtt{Variables}, \mathtt{Values}, \mathtt{Constraints} \rangle $$
   where 
   - Variables is a set of strings which serve as variables,
   - Values is a set of values that can be assigned to the variables in the set Variables.
   - Constraints is a set of formulas from first order logic.
     Each of these formulas is  called a constraint of P.
     The formulas are represented as strings.
* lcv is a Boolean flag.  If this flag is set to True, the least constraining value heuristic is used when choosing values. 
  Otherwise, the values are chosen arbitrarily.   
Initially, the function solve checks that the set Constraints does not contain any variables that are not 
elements of the set Variables.  Furthermore, it checks that all variables in Variables do indeed occur 
in one of the constraints.  These two checks are useful to capture spelling mistakes.
Then, the function solve converts the CSP P into an augmented CSP where every constraint $f$ is annotated with the variables occurring in $f$.  
The most important data structure maintained by solve is the dictionary ValuesPerVar.  For every variable $x$ occurring in a constraint of P, the expression $\texttt{ValuesPerVar}[x]$ is the set of values that can be used to instantiate the variable $x$.  Initially, 
$\texttt{ValuesPerVar}[x]$ is set to Values, but as the search for a solution proceeds, the sets $\texttt{ValuesPerVar}[x]$ are reduced by removing any values that cannot be part of a solution.
This way, the consequences of binding one variable to a value are propagated to the other variables.
Next, the function solve divides the constraints into two groups:
- The unary constraints are those that only contain a single variable.
The unary constraints can be solved immediately: 
  If $f$ is a unary constraint containing only the variable $x$, the set $\texttt{ValuesPerVar}(x)$ 
  is reduced to the set of those values $v$ such that $\texttt{eval}(f, {x\mapsto v})$ is true.
- The remaining constraints contain at least two different variables.
After the unary constraints have been taken care of, backtrack_search is called to solve the remaining constraint satisfaction problem.  The function backtrack_search uses both backtracking and constraint propagation to solve the remaining constraints.
Furthermore, the most constrained variable heuristic and, if lvc is set to True, the least constraining value heuristic are used.
End of explanation
"""


def solve_unary(f, x, Values):
    Legal = { value for value in Values if eval(f, { x: value }) }
    if len(Legal) == 0:
        raise Backtrack()
    return Legal

"""
Explanation: The function solve_unary takes three arguments:
* f is a unary constraint, i.e. a constraint that contains only one variable,
* x is the variable occurring in f, and 
* Values is the set of values that can be assigned to the variable x.  
The function returns the subset of those values v from the set Values that can be substituted for x such that $\texttt{eval}(f, { x \mapsto v })$ evaluates as True.  If the unary constraint f is unsolvable, then the given CSP is unsolvable and an exception is raised.
End of explanation
"""


def backtrack_search(Assignment, ValuesPerVar, Constraints, lcv):
    if len(Assignment) == len(ValuesPerVar):
        return Assignment
    x = most_constrained_variable(Assignment, ValuesPerVar)
    if lcv and len(ValuesPerVar[x]) > 1:
        ValueList = least_constraining(x, ValuesPerVar, Assignment, Constraints)
    else:
        ValueList = ValuesPerVar[x]
    for v in ValueList: 
        try:
            NewValues    = propagate(x, v, Assignment, Constraints, ValuesPerVar)
            NewAssign    = Assignment.copy()
            NewAssign[x] = v
            return backtrack_search(NewAssign, NewValues, Constraints, lcv)
        except Backtrack:
            continue
    raise Backtrack()

"""
Explanation: The function backtrack_search takes four arguments:
- Assignment is a partial variable assignment that is represented as a
   dictionary.  Initially, this assignment will be the  empty dictionary.   
   Every recursive call of backtrack_search adds the assignment of one 
   variable to  the given assignment. 
- ValuesPerVar is a dictionary.  For every variable x, ValuesPerVar[x] is the set of values 
   that still might be assigned to x.
- Constraints is a set of pairs of the form (F, V) where F is a constraint and V is the 
   set of variables occurring in V.
- lcv is a Boolean flag.  If this flag is set to true, the least constraining value heuristic is used.
The function tries to solve the given CSP via backtracking.  Instead of picking the variables arbitrarily, it uses 
the most constraint variable heuristic and therefore instantiates those variables first, that have the least
remaining values.  This way, a dead end in the search is discovered sooner.
End of explanation
"""


def most_constrained_variable(Assignment, ValuesPerVar):
    Unassigned = { (x, len(U)) for x, U in ValuesPerVar.items()
                               if  x not in Assignment
                 }
    minSize = min(lenU for _, lenU in Unassigned)
    return arb({ x for x, lenU in Unassigned if lenU == minSize })

"""
Explanation: The function most_constrained_variable takes two parameters:
- Assignment is a partial variable assignment that assigns values to variables.  It is represented as a dictionary.
- ValuesPerVar is a dictionary that maps variables to the set of values that may be assigned to these variables,
  i.e. for every variable x, ValuesPerVar[x] is the set of values that can be assigned to the variable x
  without violating a constraint.
The function returns an unassigned variable x such that the number of values in ValuesPerVar[x] is minimal among all other unassigned variables.
End of explanation
"""


import math

"""
Explanation: We import math because this gives us access to the infinite value $\infty$, which is available as math.inf.
End of explanation
"""


def least_constraining(x, ValuesPerVar, Assignment, Constraints):
    NumbersValues = []
    for value in ValuesPerVar[x]:
        ReducedValues = ValuesPerVar.copy()
        num_removed = shrinkage(x, value, Assignment, ReducedValues, Constraints)
        if num_removed != math.inf:
            NumbersValues.append( (num_removed, value) )
    NumbersValues.sort(key=lambda p: p[0])
    return [val for _, val in NumbersValues]

"""
Explanation: The function least_constraining takes four arguments:
* x is a variable. 
* ValuesPerVar is a dictionary.  For every variable var, ValuesPerVar[var] is the set of values that can be assigned to var.
* Assignment is a partial variable assignment.
* Constraints is a set of annotated constraints.
This function returns a list of values that can be substituted for the variable x.
This list is sorted so that the least constraining values are at the beginning of this list.
End of explanation
"""


def shrinkage(x, value, Assignment, ValuesPerVar, Constraints):
    count     = 0   # number of values removed from ValuesPerVar
    BoundVars = set(Assignment.keys())
    for f, Vars in Constraints:
        if x in Vars:
            UnboundVars = Vars - BoundVars - { x }
            if len(UnboundVars) == 1:
                y = arb(UnboundVars)
                Legal = set()
                for w in ValuesPerVar[y]:
                    NewAssign    = Assignment.copy()
                    NewAssign[x] = value
                    NewAssign[y] = w
                    if eval(f, NewAssign):
                        Legal.add(w)
                    else:
                        count += 1
                if len(Legal) == 0:
                    return math.inf
                ValuesPerVar[x] = Legal
    return count           

"""
Explanation: The function shrinkage takes 5 arguments:
- x is a variable that has not yet been assigned a value.
- value is a value that is to be assigned to the variable x.
- Assignment is a partial variable assignment that does not assign a value to x.
- ValuesPerVar is a dictionary that has variables as keys.  For every variable z, ValuesPerVar[z] is the set of values that 
  can still be assigned to the variable z.
- Constraints 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.
This function returns the shrinkage number, which is the number of values that need to be removed from the set 
ValuesPerVar[y] for those variables y that are different from x if we assign value to the variable x. 
If the assignment { x: value } results in any of the sets ValuesPerVar[y]
becoming empty, then the function returns math.inf in order to signal that the assignment { x: value } leads to an unsolvable problem.
End of explanation
"""


def propagate(x, v, Assignment, Constraints, ValuesPerVar):
    ValuesDict    = ValuesPerVar.copy()
    ValuesDict[x] = { v }
    BoundVars     = set(Assignment.keys())
    for f, Vars in Constraints:
        if x in Vars:
            UnboundVars = Vars - BoundVars - { x }
            if len(UnboundVars) == 1:
                y = arb(UnboundVars)
                Legal = set()
                for w in ValuesDict[y]:
                    NewAssign = Assignment.copy()
                    NewAssign[x] = v
                    NewAssign[y] = w
                    if eval(f, NewAssign):
                        Legal.add(w)
                if not Legal:
                    raise Backtrack()
                ValuesDict[y] = Legal
    return ValuesDict

"""
Explanation: The function propagate takes five arguments:
- x is a variable,
- v is a value that is supposed to be assigned to x.
- Assignment is a partial assignment that contains assignments for variables that are different from x.
- Constraints is a set of annotated constraints.
- ValuesPerVar is a dictionary assigning sets of values to all variables.  For every unassigned variable z,  ValuesPerVar[z] is the set of values that still might be assigned to z.
The purpose of the function  propagate is to compute how the sets ValuesPerVar[z] can be shrunk when the value v is assigned to the variable x.  The dictionary ValuesPerVar with appropriately reduced sets ValuesPerVar[z] is returned.  In particular, the consequences of assigning the value v to the variable x are propagated:
If there is a constraint f such that x occurs in f and there is just one variable y left that occurs in 
f and that is not yet bound in Assignment, then the values that can still be assigned to y are computed
and the dictionary ValuesDict is updated accordingly.  If there are no values left that can be assigned to 
y without violating the constraint f, the function backtracks.
End of explanation
"""


%%capture
%run N-Queens-Problem-CSP.ipynb

P = create_csp(8)

"""
Explanation: Solving the Eight-Queens-Puzzle
End of explanation
"""


%%time
Solution = solve(P, lcv=True)
print(f'Solution = {Solution}')

show_solution(Solution)

"""
Explanation: Constraint Propagation with the least constraining value heuristic takes about 27 milliseconds on my Windows desktop to solve the eight queens puzzle.
End of explanation
"""


%%time
Solution = solve(P)
print(f'Solution = {Solution}')

P = create_csp(32)

"""
Explanation: Constraint Propagation without the least constraining value heuristic takes only 13 milliseconds on my desktop to solve the eight queens puzzle.
End of explanation
"""


%%time
Solution = solve(P, True)
print(f'Solution = {Solution}')

"""
Explanation: Constraint propagation can solve the 32 queens problem in less than $2.2$ seconds, if the least constraining value heuristic is used.
End of explanation
"""


%%time
Solution = solve(P)
print(f'Solution = {Solution}')

"""
Explanation: Constraint propagation can solve the 32 queens problem in less than $264$ milliseconds, if the least constraining value heuristic is not used.
The $n$-queens problem is a relatively easy CSP and hence the least constraining value is not useful.
End of explanation
"""


%run Zebra.ipynb

zebra = zebra_csp()

"""
Explanation: Solving the Zebra Puzzle
End of explanation
"""


%%time
Solution = solve(zebra, True)

show_solution(Solution)

"""
Explanation: Constraint propagation with the least constraining value heuristic takes about 12 milliseconds to solve the Zebra Puzzle.
End of explanation
"""


%%time
Solution = solve(zebra)

"""
Explanation: If the least constraining value heuristic is not used, it takes about 12 milliseconds to solve the Zebra Puzzle.
End of explanation
"""


%run Sudoku-Frame.ipynb

csp = sudoku_csp(Sudoku)

"""
Explanation: Solving a Sudoku Puzzle
End of explanation
"""


%%time
Solution = solve(csp, True)

show_solution(Solution)

"""
Explanation: Constraint propagation with the least constraining value heuristic takes about 112 milliseconds to solve 
the given sudoku.
End of explanation
"""


%%time
Solution = solve(csp, False)

"""
Explanation: Constraint propagation without the least constraining value heuristic takes 133 milliseconds to solve 
the given sudoku. Hence, in this case the least constraining value heuristic is useful.
End of explanation
"""


csp = find_alternative(csp, Solution)
csp

%%time
Solution = solve(csp)
if Solution:
    print('There is another solution.')
else:
    print('The solution is unique!')

"""
Explanation: Let's check whether the solution is unique.
End of explanation
"""


%run Crypto-Arithmetic.ipynb

csp = crypto_csp()
csp

"""
Explanation: Solving the Crypto-Arithmetic Puzzle
End of explanation
"""


%%time
Solution = solve(csp, True)

show_solution(Solution)

"""
Explanation: Constraint propagation takes about 118 milliseconds to solve the crypto-arithmetic puzzle if the 
least constraining value heuristic is used.
End of explanation
"""


%%time
Solution = solve(csp)

"""
Explanation: Constraint propagation takes about 1.1 seconds if the least constraining value heuristic is not used.
End of explanation
"""


csp = crypto_csp_hard()

%%time
Solution = solve(csp, True)

%%time
Solution = solve(csp)

"""
Explanation: Let us try the hard version of the puzzle.
End of explanation
"""


