<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Breadth First Search
The function search takes three arguments to solve a search problem
Step1:  Given a state and a parent dictionary Parent, the function path_to returns a path leading to the given state.
Step2:  Display Code
Step3:  The function $\texttt{toDot}(\texttt{source}, \texttt{Edges}, \texttt{Fringe}, \texttt{Visited})$ takes a graph that is represented by 
its Edges, a set of nodes Fringe, and set Visited of nodes that have already been visited.
Step4:  Testing
Step5:  Saving the Infidels
Step6:  Solving the Sliding Puzzle
Step7:  The next line is needed to enable the %memit magic command.
<ASSISTANT_TASK:>
Python Code:
def search(start, goal, next_states):
    Frontier = { start }
    Visited  = set()
    Parent   = { start: start }
    while Frontier:
        NewFrontier = set()
        for s in Frontier:
            for ns in next_states(s):
                if ns not in Visited and ns not in Frontier:
                    NewFrontier.add(ns)
                    Parent[ns] = s
                    if ns == goal:
                        print(len(Visited) + len(Frontier) + len(NewFrontier))
                        return path_to(goal, Parent)
        Visited |= Frontier
        Frontier = NewFrontier
Explanation: Breadth First Search
The function search takes three arguments to solve a search problem:
- start is the start state of the search problem,
- goal is the goal state, and
- next_states is a function with signature $\texttt{next_states}:Q \rightarrow 2^Q$, where $Q$ is the set of states.
   For every state $s \in Q$, $\texttt{next_states}(s)$ is the set of states that can be reached from $s$ in one step.
If successful, search returns a path from start to goal that is a solution of the search problem
$$ \langle Q, \texttt{next_states}, \texttt{start}, \texttt{goal} \rangle. $$
The implementation of search uses the algorithm breadth first search to find a path from start to goal.
At the start of the $n^\textrm{th}$ iteration of the while loop, the following invariants are satisfied:
* Frontier contains exactly those states that have distance of $n-1$ from start.
* Visited  contains those states that have distance from start that is less than n-1.
* Parent is a dictionary. The keys of this dictionaries are all states from the sets Visited, Frontier, and NewFrontier.  
If $x = \texttt{Parent}[y]$, then $y \in \texttt{next_states}(x)$.
End of explanation
def path_to(state, Parent):
    p = Parent.get(state)
    if p == state:
        return [state]
    return path_to(p, Parent) + [state]
Explanation: Given a state and a parent dictionary Parent, the function path_to returns a path leading to the given state.
End of explanation
import graphviz as gv
Explanation: Display Code
End of explanation
def toDot(source, goal, Edges, Frontier, Visited, Parent=None):
    V = set()
    for x, L in Edges.items():
        V.add(x)
        for y in L:
            V.add(y)
    dot = gv.Digraph(node_attr={'shape': 'record', 'style': 'rounded'})
    dot.attr(rankdir='LR')
    for x in V:
        if x == source:
            dot.node(str(x), color='blue', shape='doublecircle')
        elif x in Frontier and x == goal:
            dot.node(str(x), label=str(x), color='magenta')
        elif x in Frontier:
            dot.node(str(x), label=str(x), color='red')
        elif x in Visited:
            dot.node(str(x), label=str(x), color='blue')
        else:
            dot.node(str(x), label=str(x))
    if Parent:        
        Path = path_to(goal, Parent)
    for u in V:
        if Edges.get(u):
            for v in Edges[u]:
                if Parent and v in Path and Parent[v] == u:
                    dot.edge(str(u), str(v), color='brown', style='bold')                    
                else:
                    dot.edge(str(u), str(v))
    return dot
Explanation: The function $\texttt{toDot}(\texttt{source}, \texttt{Edges}, \texttt{Fringe}, \texttt{Visited})$ takes a graph that is represented by 
its Edges, a set of nodes Fringe, and set Visited of nodes that have already been visited.
End of explanation
def next_states_test(node):
    x, y = node
    return { (x+1, y), (x, y+1) }
def create_edges(n):
    Edges = {}
    for row in range(n):
        for col in range(n):
            if (row, col) != (n-1, n-1):
                Edges[(row, col)] = list(next_states_test((row, col)))
    for k in range(n-1):
        Edges[(k, n-1)] = [(k+1, n-1)]
        Edges[(n-1, k)] = [(n-1, k+1)]
    return Edges
def search_show(start, goal, next_states, Edges):
    Visited  = set()
    Frontier = { start }
    Parent   = { start: start }
    while len(Frontier) > 0:
        display(toDot(start, goal, Edges, Frontier, Visited))
        NewFrontier = set()
        Visited    |= Frontier
        for s in Frontier:
            for ns in next_states(s):
                if not (ns in Visited):
                    NewFrontier.add(ns)
                    Parent[ns] = s
                    if ns == goal:
                        display(toDot(start, goal, Edges, NewFrontier, Visited, Parent))
                        return 
        Frontier = NewFrontier
def main(n):
    Edges = create_edges(n)
    search_show((0,0), (n-1, n -1), next_states_test, Edges)
main(6)
Explanation: Testing
End of explanation
%run Missionaries.ipynb
dot_graph(createRelation(start))
%%time
Path = search(start, goal, next_states)
printPath(Path)
Explanation: Saving the Infidels
End of explanation
%run Sliding-Puzzle.ipynb
Explanation: Solving the Sliding Puzzle
End of explanation
%load_ext memory_profiler
%%time
%memit Path = search(start, goal, next_states)
animation(Path)
Explanation: The next line is needed to enable the %memit magic command.
End of explanation
<END_TASK>