Solve the Knight Tour in Python (Breadth First Search Algorithm)

This is an actual technical exercise before interview (my friend asked me for help). The PDF requirement could be accessed [here]. The problem statement is simple and clear, in short words, you are given a starting position and ending position, find out the shortest route (a knight jumps with offset power square equal to five) between them. Print the moves (only 1 route is required).

Interview Question: The Knight’s Travel Problem

I provide the following Python implementation, which can be accessed in github.

The implementation is straightforward, using Python list as a Queue, which expands the current location with its next moves. In each iteration, a node is popped from the queue until the destination is arrived. The repeated-moves are abandoned by using a list to record the previous history moves. To simplify the implementation, every time, the current move history array is also pushed into the queue. This is clearly a BFS (Breadth First Search) algorithm, which will guarantee the first route found is a shortest one.

We might use Depth First Search, but DFS is not providing an optimal solution (shortest) unless we exhausts all the paths. We may use the Iterative Deepening Search (IDS) here – a combination of Depth First Search and Breadth First Search.

#!/usr/bin/env python

class Knight:
    """
        Knight Tour
        https://helloacm.com
    """

    """
        private attributes
    """
    __sizex  = 8
    __sizey  = 8
    __startx = 1
    __starty = 1
    __endx   = __sizex
    __endy   = __sizey

    """
        get properties wrappers
    """
    def __getsizex(self):
        return self.__sizex

    def __getsizey(self):
        return self.__sizey

    def __getsx(self):
        return self.__startx

    def __getsy(self):
        return self.__starty

    def __getendx(self):
        return self.__endx

    def __getendy(self):
        return self.__endy

    """
        set properties wrappers
    """
    def __setsizex(self, v):
        self.__sizex = v

    def __setsizey(self, v):
        self.__sizey = v

    def __setsx(self, v):
        self.__startx = v

    def __setsy(self, v):
        self.__starty = v

    def __setendx(self, v):
        self.__endx = v

    def __setendy(self, v):
        self.__endy = v

    """
        properties
    """
    StartX = property(__getsx, __setsx)
    StartY = property(__getsy, __setsy)
    EndX   = property(__getendx, __setendx)
    EndY   = property(__getendy, __setendy)
    SizeX  = property(__getsizex, __setsizex)
    SizeY  = property(__getsizey, __setsizey)

    """
        constructor
    """
    def __init__(self, start, end):
        x1 = ord(start[0]) - 64
        y1 = 9 - int(start[1])
        x2 = ord(end[0]) - 64
        y2 = 9 - int(end[1])
        self.StartX = x1
        self.StartY = y1
        self.EndX   = x2
        self.EndY   = y2

    """
        check if (x, y) is a valid position
    """
    def Check(self, x, y):
        if x <= 0 or x > self.SizeX:
            return False
        if y <= 0 or y > self.SizeY:
            return False
        return True

    """
        convert (x, y) to string representation
        e.g. (1, 1) to a1
    """
    @staticmethod
    def ConvertPosition(x, y):        
        return chr(64 + x) + str(9 - y)

    """
        print the moves
    """
    @staticmethod
    def Print(moves):
        for xy in moves:
            print Knight.ConvertPosition(xy[0], xy[1]),

    def Solve(self):
        if self.SizeX <= 0:
            raise Exception("SizeX <= 0")
        if self.SizeY <= 0:
            raise Exception("SizeY <= 0")
        if not self.Check(self.StartX, self.StartY):
            raise Exception("Start Position Invalid")
        if not self.Check(self.EndX, self.EndY):
            raise Exception("End Position Invalid")
        # offsets for next knight positions
        offset = [(1, 2), (-1, -2), (1, -2), (-1, 2),
                  (2, 1), (-2, -1), (2, -1), (-2, 1)]
        # add init position
        q = deque((self.StartX, self.StartY, []))
        history = [(self.StartX, self.StartY)]
        while q: # or len(q) # or len(q) > 0
            # pop from the queue
            cur = q.popleft()
            if cur == (self.EndX, self.EndY): # cur[0] == self.EndX and cur[1] == self.EndY:
                Knight.Print(cur[2])
                break
            for xy in offset:
                curx = xy[0] + cur[0]
                cury = xy[1] + cur[1]
                if self.Check(curx, cury) and (not (curx, cury) in history):
                    history.append((curx, cury))
                    curmove = [_ for _ in cur[2]]
                    curmove.append((curx, cury))
                    q.append((curx, cury, curmove))

if __name__ == "__main__":
    obj = Knight("A8", "B7")
    obj.Solve()

The sample output:

B6 C4 D6 B7

Another interesting problem: Teaching Kids Programming – Back Tracking Algorithm to Find the The Knight’s Tour Path (Recursive Depth First Search)

–EOF (The Ultimate Computing & Technology Blog) —