"""
Knight's Path Problem with DFS
"""

def available_moves(position):
    # Returns a list of available knight moves
    # given a square in the form 'a2' or 'd8'.
    # Only works for 8x8 board.
    horizontal_nums = {'a': 1, 'b': 2, 'c': 3, 'd': 4, 'e': 5, 'f': 6,\
                       'g': 7, 'h': 8}
    h_nums_rv = {v: k for k, v in horizontal_nums.items()}
    h_pos = int(horizontal_nums[position[0]])
    v_pos = int(position[1])
    final_moves = []
    moves = [[h_pos + 1, v_pos + 2], [h_pos + 1, v_pos - 2],\
             [h_pos - 1, v_pos + 2], [h_pos - 1, v_pos - 2],\
             [h_pos + 2, v_pos + 1], [h_pos + 2, v_pos - 1],\
             [h_pos - 2, v_pos + 1], [h_pos - 2, v_pos - 1]]
    for move in moves:
        if move[0] >=1 and move[1] >= 1 and move[0] <= 8 and move[1] <= 8 :
            temp_h_move = move[0]
            v_move = str(move[1])
            h_move = h_nums_rv[move[0]]
            final_moves.append(h_move + v_move)
    return final_moves

def build_matrix():
    # Builds an adjacency matrix dictionary by calling
    # available_moves and storing the legal moves in the dict.
    squares = []
    for letter in "abcdefgh":
        for num in range(1,9):
            squares.append(letter+str(num))
    adjacency_matrix = {}
    for item in squares:
        adjacency_matrix[item] = available_moves(item)
    return adjacency_matrix


def dfs(s, path):
    # Depth First Search algorithm that builds a path
    # around the board hitting every node possible.
    adj_matrix = build_matrix()
    if s not in path:
        path += [s]
        for item in adj_matrix[s]:
            dfs(item, path)
    return path

def find_path(s, t):
    # Finds a path for a knight to travel from
    # square s to square t. Returns it as a list.
    final_path = dfs(s,[])
    knights_path = []
    for item in final_path:
        knights_path.append(item)
        if item == t:
            break
    return knights_path
