Write a program that animates the move of a knight in a chess board from any source to any destination with the minimum number of steps. You may need to use Breadth First Search (BFS) with Queue data structure.

Source Code:

import turtle
import time
import sys

turtle.setup(800,800)
turtle.setworldcoordinates(-250,-250,250,250)
turtle.title("Knight's Minimum Moves - PythonTurtle.Academy")

def draw_square(x,y,size,color):
    turtle.up()
    turtle.goto(x,y)
    turtle.seth(0)
    turtle.down()
    turtle.begin_fill()
    turtle.fillcolor(color)
    for i in range(4):
        turtle.fd(size)
        turtle.left(90)
    turtle.end_fill()
        
def draw_board(src=(-2,-2),dest=(-2,-2), mlist=[]):
    turtle.pencolor("black")
    y = -200
    piecesize = 50
    startpiececolor = "darkgray"
    for i in range(8):
        x = -200
        piececolor = startpiececolor
        for j in range(8):
            if (j+1,i+1)==src:
                draw_square(x,y,piecesize,'light blue')
            elif (j+1,i+1)==dest:
                draw_square(x,y,piecesize,'pink')
            elif (j+1,i+1) in mlist:
                draw_square(x,y,piecesize,'light green')                
            else:   
                draw_square(x,y,piecesize,piececolor)
            x += piecesize
            if piececolor == "darkgray":
                piececolor = "lightgray"
            else:
                piececolor = "darkgray"
        y += piecesize
        if startpiececolor == "darkgray":
            startpiececolor = "lightgray"
        else:
            startpiececolor = "darkgray"
    
def draw_knight(pos):
    xpos = 50*(pos[0]-1) - 175
    ypos = 50*(pos[1]-1) - 195
    turtle.up()
    turtle.goto(xpos,ypos)
    turtle.write('\u265e',align='center',font=('Arial',40,'normal'))

class node:
    def __init__(self,val,nxt=None):
        self.value=val
        self.next=nxt

class LinkedList:
    def __init__(self,it=None):
        self.head = None
        self.tail = None
        self.length = 0
        if it is None: return
        for x in it:
            self.insert_at_tail(x)

    def insert_at_head(self,k):
        if self.head is None:
            self.head = node(k)
            self.tail = self.head
        else:
            p = node(k,self.head)
            self.head = p
        self.length += 1

    def insert_after(self,p,k):
        if self.length < p or p < 0:
            raise Exception('Linked List doesn\'t have position '+str(p))
        if p==0:
            self.insert_at_head(k)
            return
        q = self.head
        for _ in range(p-1):
            q = q.next
        q.next = node(k,q.next)
        
    def insert_at_tail(self,k):
        if self.tail is None:
            self.head = node(k)
            self.tail = self.head
        else:
            self.tail.next = node(k)
            self.tail = self.tail.next
        self.length += 1

    def __iter__(self):
        p = self.head
        while p is not None:
            yield p.value
            p = p.next
            
    def __len__(self):
        return self.length
    
    def __str__(self):
        s = ""
        p = self.head
        while p is not None:
            s += str(p.value) + '->'
            p = p.next
        s += 'None'
        return s

    def delete_from_head(self):
        if self.head is None: return
        self.length -= 1
        self.head = self.head.next
        if self.head is None:
            self.tail = None

    def delete_from_tail(self):
        if self.head is None: return
        self.length -= 1
        if self.head == self.tail: self.head = self.tail = None
        p = self.head
        while p.next != self.tail:
            p = p.next
        p.next = None
        self.tail = p

class Queue:
    def __init__(self):
        self.ll = LinkedList()
        self.length = len(self.ll)

    def push(self,k):
        self.ll.insert_at_tail(k)

    def pop(self):
        if len(self.ll)==0:
            raise Exception('Queue is empty')
        self.ll.delete_from_head()

    def top(self):
        if len(self.ll)==0:
            raise Exception('Queue is empty')
        return self.ll.head.value;
        
    def empty(self):
        return len(self.ll)==0

    def __len__(self):
        return len(self.ll)

class position:
    def __init__(self,pos,dist,parent):
        self.pos = pos
        self.dist = dist
        self.parent = parent

moves = [ (1,2), (1,-2), (-1,2),(-1,-2), (2,-1), (2,1), (-2,1), (-2,-1) ]

def valid_position(pos):
    if pos[0] < 1 or pos[0] > 8 or pos[1] < 1 or pos[1] > 8: return False
    return True

def minimum_knight_move(src, dest):
    q = Queue()
    s = set()
    q.push(position(src,0,None))
    s.add(src)
    while not q.empty():
        current = q.top()
        pos = current.pos
        dist = current.dist
        q.pop()
        # try all possible moves from here
        for m in moves:
            new_pos = (pos[0]+m[0],pos[1]+m[1])
            if valid_position(new_pos) and new_pos not in s:
                if new_pos == dest: return current
                s.add(new_pos)
                q.push(position(new_pos,dist+1,current))
    return -1
    
if __name__=='__main__':
    turtle.speed(0)
    turtle.hideturtle()
    turtle.tracer(0)
    while True:
        turtle.clear()
        draw_board()
        src = (-1,-1)
        dest = (-1,-1)
        while src[0] < 0 or src[0] > 8 or src[1] < 0 or src[1] > 8:
            srctext=turtle.textinput("Begin Position","Please enter the starting position (e.g. 2 4):")
            if srctext is None: sys.exit(0)
            try:
                src = tuple(map(int,srctext.split()))
            except:
                src = (-1,-1)
        draw_board(src)
        draw_knight(src)
        while dest[0] < 0 or dest[0] > 8 or dest[1] < 0 or dest[1] > 8:
            desttext=turtle.textinput("End Position","Please enter the target position (e.g. 8 5):")
            if desttext is None: sys.exit(0)
            try:
                dest = tuple(map(int,desttext.split()))
            except:
                dest = (-1,-1)
        draw_board(src,dest)
        draw_knight(dest)
        current = minimum_knight_move(src,dest)
        s = LinkedList()
        s.insert_at_head(dest)
        mlist = list()
        while current is not None:
            s.insert_at_head(current.pos)
            current = current.parent
        for pos in s:
            turtle.clear()
            mlist.append(pos)
            draw_board(src,dest,mlist)
            draw_knight(pos)
            time.sleep(1)
            turtle.update()