<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 The Sliding Puzzle
<img src="8-puzzle.png">
The picture above shows an instance of the $3 \times 3$ 
<a href="https
Step1:  Since breadth first search stores the set of states that have been visited, we have to represent states by immutable objects and hence we represent the states as tuples of tuples.  In order to be able to change these states, we have to transform these tuples of tuples into lists of lists.
The function to_list transforms a tuple of tuples into a list of lists.
Step2:  The function to_tuple transforms a list of lists into a tuple of tuples.
Step3:  Given a State that satisfies 
State[row][col] == 0
and a direction (dx, dy) that is an element from the set 
$\bigl{ (1, 0), (-1, 0), (0, 1), (0, -1) \bigr}$,
the function move_dir moves the empty tile in the direction (dx, dy).
Step4:  Given a State of the sliding puzzle, the function next_states(State) computes all those states that can be reached from State in one step.
Step5:  Below, we have defined the start state, which is the state shown in the figure above on the left.
Step6:  Below is an instance of the $4 \times 4$ puzzle that can be solved in 36 steps.
Step7:  For informed search we need to implement a 
heuristic that estimates to distance between two states.
The function manhattan implemented below takes as argument two states of the sliding puzzle and computes the Manhattan distance between these states.
Basically, the manhattan distance measure the number of moves that it would take to transform stateA into stateB if we were allowed to slide different tiles on top of each other.
Step8:  Animation
The package ipycanvas, which is imported below, can be installed using the following command
Step9:  The module time is part of the standard library, so it is preinstalled.  We have imported it because we need the function time.sleep(secs) to pause the animation for a specified time.
Step10:  The global variable Colors specifies the colors of the tiles.
Step11:  The global variable size specifies the size of one tile in pixels.
Step12:  The function draw(State, canvas, dx, dy, tile, x) draws a given State of the sliding puzzle, where tile has been moved by offset pixels into the direction (dx, dy).
Step13:  The global variable delay controls the speed of the animation.
Step14:  The function call tile_and_direction(state, next_state) takes a state and the state that follows this state and returns a triple (tile, dx, dy) where tile is the tile that is moved to transform state into next_state and (dx, dy) is the direction in which this tile is moved.
Step15:  Given a list of states representing a solution to the sliding puzzle, the function call 
animation(Solution) animates the solution.
<ASSISTANT_TASK:>
Python Code:
def find_tile(tile, State):
    n = len(State)
    for row in range(n):
        for col in range(n):
            if State[row][col] == tile:
                return row, col
Explanation: The Sliding Puzzle
<img src="8-puzzle.png">
The picture above shows an instance of the $3 \times 3$ 
<a href="https://en.wikipedia.org/wiki/Sliding_puzzle">sliding puzzle</a>:
There is a board of size $3 \times 3$ with 8 tiles on it. These tiles are numbered with digits from the set ${1,\cdots, 8}$.  As the $3 \times 3$ board has an area of $9$, but there are only $8$ tiles, there is an empty square on the board.  Tiles adjacent to the empty square can be moved into the square, thereby emptying the space that was previously occupied by these tiles.  The goal of the $3 \times 3$ puzzle is to transform the state shown on the left of the picture above into the state shown on the right.  We represent states as tuples of tuples.  For example, the state shown above on the left side is represented as the following tuple:
( (8, 0, 6),
          (5, 4, 7),
          (2, 3, 1)
        )
If we represent states this way, given a state s, the expression s[row][col] returns the tile in the specified row and col.  
In order to get an idea of the sliding puzzle, you can play it online at https://www.helpfulgames.com/subjects/brain-training/sliding-puzzle.html.
The function call find_tile(tile, State) finds the coordinates of the given tile in State.  The tile is represented as a number from the set ${0,1,\cdots,8}$, where $0$ represents the empty tile.  The parameter State is a tuple of tuples that specifies the positions of the tiles.  If (row, col) is the result returned by find_tile, then we have:
State[row][col] == tile
End of explanation
to_list = lambda State: [list(row) for row in State]
Explanation: Since breadth first search stores the set of states that have been visited, we have to represent states by immutable objects and hence we represent the states as tuples of tuples.  In order to be able to change these states, we have to transform these tuples of tuples into lists of lists.
The function to_list transforms a tuple of tuples into a list of lists.
End of explanation
to_tuple = lambda State: tuple(tuple(row) for row in State)
Explanation: The function to_tuple transforms a list of lists into a tuple of tuples.
End of explanation
def move_dir(State, row, col, dx, dy):
    State = to_list(State)
    State[row     ][col     ] = State[row + dx][col + dy]
    State[row + dx][col + dy] = 0
    return to_tuple(State)
Explanation: Given a State that satisfies 
State[row][col] == 0
and a direction (dx, dy) that is an element from the set 
$\bigl{ (1, 0), (-1, 0), (0, 1), (0, -1) \bigr}$,
the function move_dir moves the empty tile in the direction (dx, dy).
End of explanation
def next_states(State):
    n          = len(State)
    row, col   = find_tile(0, State)
    New_States = set()
    Directions = [ (1, 0), (-1, 0), (0, 1), (0, -1) ]
    for dx, dy in Directions:
        if row + dx in range(n) and col + dy in range(n):
            New_States.add(move_dir(State, row, col, dx, dy))
    return New_States
Explanation: Given a State of the sliding puzzle, the function next_states(State) computes all those states that can be reached from State in one step.
End of explanation
start = ( (8, 0, 6),
          (5, 4, 7),
          (2, 3, 1)
        )
next_states(start)
goal = ( (0, 1, 2), 
         (3, 4, 5), 
         (6, 7, 8)
       )
Explanation: Below, we have defined the start state, which is the state shown in the figure above on the left.
End of explanation
start2 = ( (  0,  1,  2,  3 ),
           (  4,  5,  6,  8 ),
           ( 14,  7, 11, 10 ),
           (  9, 15, 12, 13 )
         )
goal2  = ( (  0,  1,  2,  3 ),
           (  4,  5,  6,  7 ),
           (  8,  9, 10, 11 ),
           ( 12, 13, 14, 15 )
         )
Explanation: Below is an instance of the $4 \times 4$ puzzle that can be solved in 36 steps.
End of explanation
def manhattan(stateA, stateB):
    n = len(stateA)
    PositionsB = {}
    for row in range(n):
        for col in range(n): 
            tile = stateB[row][col]
            PositionsB[tile] = (row, col)
    result = 0
    for rowA in range(n):
        for colA in range(n): 
            tile = stateA[rowA][colA]
            if tile != 0:
                rowB, colB = PositionsB[tile]
                result += abs(rowA - rowB) + abs(colA - colB)
    return result
manhattan(start, goal)
Explanation: For informed search we need to implement a 
heuristic that estimates to distance between two states.
The function manhattan implemented below takes as argument two states of the sliding puzzle and computes the Manhattan distance between these states.
Basically, the manhattan distance measure the number of moves that it would take to transform stateA into stateB if we were allowed to slide different tiles on top of each other.
End of explanation
import ipycanvas as cnv
Explanation: Animation
The package ipycanvas, which is imported below, can be installed using the following command:
conda install -c conda-forge ipycanvas
This package is useful for drawings and animations.  Its documentation can be found at:
  https://ipycanvas.readthedocs.io/en/latest/.
End of explanation
import time
Explanation: The module time is part of the standard library, so it is preinstalled.  We have imported it because we need the function time.sleep(secs) to pause the animation for a specified time.
End of explanation
Colors = ['white', 'lightblue', 'pink', 'magenta', 'orange', 'red', 'yellow', 'lightgreen', 'gold',
          'CornFlowerBlue', 'Coral', 'Cyan', 'orchid', 'DarkSalmon', 'DeepPink', 'green'
         ] 
Explanation: The global variable Colors specifies the colors of the tiles.
End of explanation
size = 100
Explanation: The global variable size specifies the size of one tile in pixels.
End of explanation
def draw(State, canvas, dx, dy, tile, offset):
    canvas.text_align    = 'center'
    canvas.text_baseline = 'middle'
    with cnv.hold_canvas(canvas):
        canvas.clear()
        n = len(State)
        for row in range(n):
            for col in range(n):
                tile_to_draw = State[row][col]
                color = Colors[tile_to_draw]
                canvas.fill_style = color
                if tile_to_draw not in (0, tile):
                    x = col * size
                    y = row * size
                    canvas.fill_rect(x, y, size, size)
                    canvas.line_width = 3.0
                    x += size // 2
                    y += size // 2
                    canvas.stroke_text(str(tile_to_draw), x, y)
                elif tile_to_draw == tile:
                    x = col * size + offset * dx
                    y = row * size + offset * dy
                    canvas.fill_rect(x, y, size, size)
                    canvas.line_width = 3.0
                    x += size // 2
                    y += size // 2
                    if tile_to_draw != 0:
                        canvas.stroke_text(str(tile_to_draw), x, y)
def create_canvas(n): 
    canvas = cnv.Canvas(size=(size * n, size * n))
    canvas.font = '100px serif'
    return canvas
Explanation: The function draw(State, canvas, dx, dy, tile, x) draws a given State of the sliding puzzle, where tile has been moved by offset pixels into the direction (dx, dy).
End of explanation
delay = 0.002
Explanation: The global variable delay controls the speed of the animation.
End of explanation
def tile_and_direction(state, next_state):
    row0, col0 = find_tile(0, state)
    row1, col1 = find_tile(0, next_state)
    return state[row1][col1], col0-col1, row0-row1
Explanation: The function call tile_and_direction(state, next_state) takes a state and the state that follows this state and returns a triple (tile, dx, dy) where tile is the tile that is moved to transform state into next_state and (dx, dy) is the direction in which this tile is moved.
End of explanation
def animation(Solution):
    start = Solution[0]
    n = len(start)
    canvas = create_canvas(n)
    draw(start, canvas, 0, 0, 0, 0)
    m = len(Solution)
    display(canvas)
    for i in range(m-1):
        state = Solution[i]
        tile, dx, dy = tile_and_direction(state, Solution[i+1])
        for offset in range(size+1):
            draw(state, canvas, dx, dy, tile, offset)
            time.sleep(delay)
Explanation: Given a list of states representing a solution to the sliding puzzle, the function call 
animation(Solution) animates the solution.
End of explanation
<END_TASK>