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

"""
Explanation: Brute Force CSP Solver
Utility Functions
The function arb(S) takes a set S as input and returns an arbitrary element from 
this set.  The set S is not changed.
End of explanation
"""


gCounter = 0

def solve(P):
    return brute_force_search({}, P)

"""
Explanation: The procedure solve(P) takes a constraint satisfaction problem 
P as input.  Here P is a triple of the form 
$$ \mathcal{P} = \langle \mathtt{Vars}, \mathtt{Values}, \mathtt{Constraints} \rangle $$
where 
- $\mathtt{Vars}$ is a set of strings which serve as variables,
- $\mathtt{Values}$ is a set of values that can be assigned 
  to the variables in $\mathtt{Vars}$.
- $\mathtt{Constraints}$ is a set of formulas that are represented as Boolean expressions.
  Each of these formulas is  called a constraint of $\mathcal{P}$.
The sole purpose of the function solve is to call the function brute_force_search, which needs an additional argument.  This argument is a partial variable assignment that is initially empty.  Every recursive iteration of the function brute_force_search assigns one additional variable.
End of explanation
"""


def brute_force_search(Assignment, csp):
    Variables, Values, Constraints = csp
    if len(Assignment) == len(Variables): # all variables have been assigned
        global gCounter
        gCounter += 1
        if check_all_constraints(Assignment, Constraints):
            return Assignment             # Assignment is a solution
        else:
            return None                   # Assignment does not solve the problem
    var = arb(Variables - Assignment.keys())
    for value in Values:
        NewAss      = Assignment.copy()
        NewAss[var] = value
        result      = brute_force_search(NewAss, csp)
        if result != None:
            return result
    return None

"""
Explanation: The function brute_force_search takes two arguments:
- Assignment is a <em style="color:blue">partial variable assignment</em> that is
   represented as a dictionary.  Initially, this assignment will be the  empty
   dictionary.  Every recursive call of brute_force_search adds the assignment of one 
   variable to  the given assignment. 
- csp is a constraint satisfaction problem.
The implementation of brute_force_search works as follows:
- If all variables have been assigned a value, the dictionary Assignment will have the same number of entries as the set Variables has elements.  Hence, in that case Assignment is a complete assignment of all variables and we have to test whether    all constraints are satisfied.  This is done using the auxiliary procedure check_all_constraints.
- Otherwise, we pick a variable that has not been assigned and recursively try to assign all possible 
  values for this variable.
End of explanation
"""


def check_all_constraints(Assignment, Constraints):
    A = Assignment.copy()
    return all(eval(f, A) for f in Constraints)

"""
Explanation: The function check_all_constraints takes two arguments:
- Assignment is a variable assignment that is represented as a dictionary.
- Constraints is a set of Boolean Python expressions.
The function returns True iff all these expressions evaluate as True using
the given Assignment.
Below, we have to create a copy of Assignment since the function eval modifies the assignment given to it.
End of explanation
"""


%%capture
%run Map-Coloring.ipynb

P = map_coloring_csp()
P

solve(P)

gCounter

"""
Explanation: Map Coloring
End of explanation
"""


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

P = create_csp(8)
P

"""
Explanation: N Queens Problem
The notebook N-Queens-Problem-CSP.ipynb provides the function
create_csp(n) that returns a CSP encoding the 
n queens puzzle.
End of explanation
"""


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

8 ** 8

show_solution(Solution)

"""
Explanation: Brute force search takes about 30 seconds on my desktop to solve the eight queens puzzle.
End of explanation
"""


8**8 / 7**7

"""
Explanation: In the $8$ queens problem we have to test $8^8$ different assignments.  The $7$ queens problem only has $7^7$ assignments.
End of explanation
"""


30 / (8**8 / 7**7)

P = create_csp(7)

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

"""
Explanation: Therefore, the time needed to solve the $7$ queens problem should be smaller by a factor of $\displaystyle\frac{8^8}{7^7}$:
End of explanation
"""


