def search(start, goal, next_states):
    limit = 36
    while True:
        Path = depth_limited_search(start, goal, next_states, [start], { start }, limit)
        if Path is not None:
            return Path
        limit += 1
        print(f'limit = {limit}')

"""
Explanation: Iterative Deepening
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 procedure search tries to find a solution to the search problem by first trying to find a solution that has a length of $1$, then of length $2$, then of length $3$, etc. 
The search only stops when a solution is found.
End of explanation
"""


def depth_limited_search(state, goal, next_states, Path, PathSet, limit):
    if state == goal:
        return Path
    if len(Path) == limit:
        return None
    for ns in next_states(state):
        if ns not in PathSet:
            Path   .append(ns)
            PathSet.add(ns)
            Result = depth_limited_search(ns, goal, next_states, Path, PathSet, limit)
            if Result is not None:
                return Result
            Path   .pop()
            PathSet.remove(ns)
    return None

"""
Explanation: The function depth_limited_search tries to find a solution to the search problem
$$ \langle Q, \texttt{next_states}, \texttt{start}, \texttt{goal} \rangle $$
that has a length of at most limit.  The algorithm used is depth first search.
End of explanation
"""


%run Sliding-Puzzle.ipynb

%load_ext memory_profiler

%%time
Path=search(start, goal, next_states)

len(Path)

animation(Path)

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


