Start = ( (  '0', '14',  '8', '12' ),
          ( '10', '11', '13',  '9' ),
          (  '6',  '2',  '4', '15' ),
          (  '3',  '5',  '7',  '1' )
        )

Goal  = ( (  '0',  '1',  '2',  '3' ),
          (  '4',  '5',  '6',  '7' ),
          (  '8',  '9', '10', '11' ),
          ( '12', '13', '14', '15' )
        )

"""
Explanation: Taoistic Search
The holy book of Taoism, the <a href="https://en.wikipedia.org/wiki/Tao_Te_Ching">Tao Te Ching</a>, contains the following wisdom:
<p>
<center style="color:blue; background-color:yellow; font-family: Brush Script MT, cursive; font-size:40px; padding: 12px">
    <a href="https://en.wikipedia.org/wiki/A_journey_of_a_thousand_miles_begins_with_a_single_step">
        A yourney of a thousand miles begins but with a single step.</a>
</center>
</p>

Taoistic search is based on this principle: 
- Split the search problem into subproblems that can be readily solved.
- Solve these problems one by one.
- Combine the solutions of the subproblems to a solution of the given search problem.
We will use taoistic search to solve the search problem for the 15-puzzle where the states Start and Goal are defined
as follows.
End of explanation
"""


import ipycanvas as cnv

"""
Explanation: In order to view these states more conveniently, we define a number of auxiliary functions in the following subsection.
Animation
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]
                if tile_to_draw != '*':
                    color = Colors[int(tile_to_draw)]
                else:
                    color = 'lightyellow'
                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.stroke_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.stroke_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 = '60px serif'
    return canvas

def draw_state(State):
    n = len(State)
    canvas = create_canvas(n)
    draw(State, canvas, 0, 0, '+', 0)
    display(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.
<b style="color:red; background-color:lightyellow">If the animation is jerky on your computer, try increasing the value of the variable delay below.</b>
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
"""


draw_state(Start)

draw_state(Goal)

"""
Explanation: Taoistc Search: Detailed Explanation
Let us begin by our explanation by drawing both the states Start and Goal of our search problem.
End of explanation
"""


Start1 = ( ( '0', '14',  '*',  '*' ),
           ( '*',  '*',  '*',  '*' ),
           ( '*',  '*',  '*', '15' ),
           ( '*',  '*',  '*',  '*' )
         )
draw_state(Start1)

Goal1 = ( ( '*', '*',  '*',  '*' ),
          ( '*', '*',  '*',  '*' ),
          ( '*', '*',  '*',  '*' ),
          ( '*', '*', '14', '15' )
        )
draw_state(Goal1)

"""
Explanation: In order to solve this instance of the 15-puzzle we could start by moving the tiles 14 and 15 into their final destination 
without caring for the other tiles.  To this end we define two new <em style="color:blue">extended states</em> Start1 and Goal1 as shown below.  In these <em style="color:blue">extended states</em> we have replaced all those tiles that are not important for moving 14 and 15 into their final destination by <em style="color:blue">wildcard tiles</em> defined as '*'.
<em style="color:blue">Extended states</em> are also known as <em style="color:blue">patterns</em>.
End of explanation
"""


State = ( ('10',  '8', '13', '12'),
          ('11',  '5',  '2',  '9'),
          ( '6',  '7',  '0',  '4'),
          ( '3',  '1', '14', '15')
        )
draw_state(State)

"""
Explanation: It should be noted that we have replaced the tile numbered '0' by a wildcard tile '*' when creating the state Goal1, but 
not when creating the state Start1.  The reason is explained below.
The search problem specified by Start1 and Goal1 is quite easy to solve.  We remember the set of 
<em style="color:blue">actions</em>, i.e. movements 
of the empty tile that we had to perform to transform Start1 into Goal1.  Next, we apply these actions to the state Start.  The resulting state might look like the state State shown below. 
Now we can explain the reason for not replacing the empty tile with '*' in Start1 since otherwise we would not be able to
use the actions found when transforming Start1 to Goal1 to transform the state Start1 into the state State.
End of explanation
"""


Start2 = ( ( '*', '*', '13', '12' ),
           ( '*', '*',  '*',  '*' ),
           ( '*', '*',  '0',  '*' ),
           ( '*', '*', '14', '15' )
        )
draw_state(Start2)

Goal2 = ( ( '*',  '*',  '*',  '*'),
          ( '*',  '*',  '*',  '*'),
          ( '*',  '*',  '*',  '*'),
          ('12', '13', '14', '15')
        )
draw_state(Goal2)

"""
Explanation: Our next goal is to move the tiles numbered with 12 and 13 into their final position.  To this end we define the 
<em style="color:blue">extended states</em> Start2 and Goal2 as shown below.
End of explanation
"""


State = ( ('10',  '5',  '8',  '9'),
          ( '6', '11',  '7',  '4'),
          ( '1',  '3',  '0',  '2'),
          ('12', '13', '14', '15')
        )
draw_state(State)

"""
Explanation: Again, we solve the resulting search problem and remember the actions that transformed Start2 into Goal2.  We apply these actions to the state State and end up with State being transformed into the state shown below.
End of explanation
"""


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: Proceeding in this way we can solve the given instance of the 15-puzzle.  The solution that we find will not be optimal, but it won't be too far from the optimal solution.
Auxiliary Functions for the Sliding Puzzle
The function call find_tile(tile, State) finds the coordinates of the given tile in State.  The tile is represented as a string from the set 
{'0', '1', ..., '15'},
where '0' represents the empty tile.  
Nota bene: 
We have to represent the tiles as strings instead of numbers as we will later replace some of these tiles by the wildcard 
character '*'.  The class Set that we use to represent sets of states does not permit inhomogeneous sets, i.e. sets that 
contain both numbers and strings.  
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 A$^*$-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 + dy][col + dx]
    State[row + dy][col + dx] = '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)
    NewStates  = set()
    Directions = [ (1, 0), (-1, 0), (0, 1), (0, -1) ]
    for dx, dy in Directions:
        if row + dy in range(n) and col + dx in range(n):
            NewStates.add(move_dir(State, row, col, dx, dy))
    return NewStates

"""
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
"""


def matches(Pattern, State):
    "your code here"

"""
Explanation: The function matches(Pattern, State) checks, whether the pattern Pattern matches the state State.  A pattern is like a state but instead of numbers, some entries of the list of lists have the form '*'.  The idea is that the string '*' is a wildcard that matches anything.
Note that State can also be an extended state.
End of explanation
"""


def manhattan(State1, State2):
    "your code here"

"""
Explanation: The function manhattan implemented below takes as argument two extended states State1 and State2 
possibly containing wildcards and computes the Manhattan distance between these 
extended 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.
When computing these distances,  tiles that are numbered with a wildcard are ignored.
End of explanation
"""


def find_tiles(Pattern):
    Result = []
    n = len(Pattern)
    for row in range(n):
        for col in range(n):
            tile = Pattern[row][col]
            if tile != '*':
                Result.append(tile)
    return Result

"""
Explanation: The function find_tiles takes a <em style="color:blue">pattern</em> Pattern as input and returns the
list of all tiles in Pattern that are labeled with a number.
End of explanation
"""


def replace_numbers(Pattern, Tiles):
    "your code here"

"""
Explanation: The function replace_numbers takes two arguments:
- Pattern is an extended state,
- Tiles is a list of numbered tiles.
The state Pattern is transformed by replacing all tiles that are not a member of the list Tiles
with the wildcard character *.
End of explanation
"""


def intermediate_goals(Goal, TilesList):
    "your code here"

"""
Explanation: The function intermediate_goals is called with two parameters:
- Goal is a state of the 15-puzzle,
- TilesList is a list of list of numbers.
   For example, TilesList could be the list [ [14, 15], [12, 13] ].
   This list would specify that we want to create two intermediate 
   goals.
   - The first goal would only have the tiles numbered 14 and 15,
     while all other tiles would be replaced by wildcards.
   - The second goal would only have the tiles numbered 12, 13, 14,
     and 15, while all other tiles would be replaced by wildcards.
The function returns the list of intermediate goals.
End of explanation
"""


def extract_move(Pattern1, Pattern2):
    "your code here"

"""
Explanation: Given two extended states Pattern1 and Pattern2 the function extract_move returns a pair (dx, dy) such that we have:
(row, col) = find_tile('0', Pattern1) -&gt; move_dir(Pattern1, row, col, dx, dy) == Pattern2
Hence extract_move(Pattern1, Pattern2) computes the action that is necessary to transform Pattern1 into 
Pattern2.  This action is encoded as a direction (dx, dy).  This is the direction to move the empty tile in Pattern1 to reach Pattern2.
End of explanation
"""


def extract_move_list(PatternList):
    "your code here"

"""
Explanation: Given a list of extended states PatternList of the form
$$ \texttt{PatternList} = [P_1, P_2, \cdots, P_n] $$
the function extract_move_list computes a list of actions $[a_1, a_2, \cdots, a_{n-1}]$ such that
applying action $(a_i)$ to state $P_i$ results in state $P_{i+1}$.
The actions are pairs of the form (dx, dy) that specify how the empty tile is to be moved.
End of explanation
"""


def apply_move_list(State, MoveList):
    "your code here"

"""
Explanation: Given the list of actions MoveList of the form $[a_1, a_2, \cdots, a_{n-1}]$, the function
apply_move_list takes a state State and applies these action to State one by one.  The list of all
states produced this way is returned.  This list starts with the given state State.
End of explanation
"""


def stateToString(state):
    n      = len(state)
    indent = " " * 4;
    line   = indent + "+---" * n + "+\n"
    result = line
    for row in range(n):
        result += indent + "|"
        for col in range(n):
            cell = state[row][col]
            if isinstance(cell, str) and cell != '*':
                cell = int(cell)
            if cell == "*":
                result += " * "
            elif cell >= 10:
                result += str(cell) + " "
            elif cell > 0 and cell < 10:
                result += " " + str(cell) + " "
            else: 
                result += "   "
            result += "|"
        result += "\n"
        result += line
    return result

"""
Explanation: The function stateToString is useful for debugging purposes to transform a given state into a string.
End of explanation
"""


import heapq

"""
Explanation: A$^*$ Search
End of explanation
"""


def search(start, goal, next_states, heuristic):
    Visited   = set()
    PrioQueue = [ (heuristic(start, goal), [start]) ]
    while PrioQueue:
        _, Path = heapq.heappop(PrioQueue)
        state   = Path[-1]
        if state in Visited:
            continue
        if matches(goal, state):
            print(f'Number of states visited: {len(Visited)}')
            return Path
        for ns in next_states(state):           
            if ns not in Visited:
                prio = heuristic(ns, goal) + len(Path)
                heapq.heappush(PrioQueue, (prio, Path + [ns]))
        Visited.add(state)

"""
Explanation: 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.  This might be an extended state.
- 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.
- heuristic is a function that takes two states as arguments.  It returns an estimate of the 
  length of the shortest path between these states.
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. $$
Basically, the function search implements A$^$ search, but instead of checking whether a state is identical to Goal, this function only tests whether a state matches* goal.
The parameter Goal is not a state, but only a pattern.
End of explanation
"""


def main():
    TilesList   = [['14', '15'], 
                   ['12', '13'], 
                   ['10', '11'], 
                   [ '8',  '9'], 
                   [ '3',  '7'], 
                   [ '2',  '6'], 
                   ['0', '1', '4', '5']
                  ]
    PatternList = intermediate_goals(Goal, TilesList)
    State       = Start
    Solution    = []
    print('Start state:')
    draw_state(Start)
    for Pattern in PatternList:
        print('Trying to reach the following pattern:')
        draw_state(Pattern)
        Tiles = find_tiles(Pattern)
        ExtendedState = replace_numbers(State, Tiles + ['0'])
        Path = search(ExtendedState, Pattern, next_states, manhattan)
        MoveList = extract_move_list(Path)
        Path = apply_move_list(State, MoveList)
        print(f'The following state is reached after {len(Path)-1} steps:');
        State = Path[-1]
        draw_state(State)
        Solution += Path[:-1]
    Solution += [ Goal ]
    return Solution

%%time
Path = main()
print(len(Path)-1)

animation(Path)

def shorten(Solution):
    shorterSolution = []
    k = 0
    while k < len(Solution) - 1:
        shorterSolution.append(Solution[k])
        if k + 2 < len(Solution) and Solution[k] == Solution[k + 2]:
            k += 3
        else: 
            k += 1
    shorterSolution += [Solution[-1]]
    return shorterSolution

animation(shorten(Path))

len(shorten(Path))-1

"""
Explanation: Putting It All Together
Let's draw the start state and animate the solution that has been found.
End of explanation
"""


