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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 | #!/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() |
#!/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) —
loading...
Last Post: Codeforces: B. Squares
Next Post: Codeforces: 263D Cycle of Graph
