

In [ ]:

    
%%HTML
<style>
.container { width:100% !important }
</style>

Breadth First Search, Queue Based Implementation



In [ ]:

    
from collections import deque



In [ ]:

    
def search(start, goal, next_states):
    Frontier   = deque([start])
    Visited = set()
    Parent  = { start: start }
    while len(Frontier) > 0:
        state = Frontier.popleft()
        if state == goal:
            return path_to(state, Parent)
        Visited.add(state)
        newStates = next_states(state)
        for ns in newStates:
            if ns not in Visited and ns not in Parent:
                Parent[ns] = state
                Frontier.append(ns)

Given a state and a parent dictionary Parent, the function path_to returns a path leading to the given state.



In [ ]:

    
def path_to(state, Parent):
    p = Parent[state]
    if p == state:
        return [state]
    return path_to(p, Parent) + [state]



In [ ]:

    
%run Sliding-Puzzle.ipynb



In [ ]:

    
%%time
Path = search(start, goal, next_states)
print(len(Path)-1)



In [ ]:

    
animation(Path)



In [ ]: