Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
from collections import deque
class Square:
def __init__(self, col, row, prev=None, moves=9999):
self.col = col
self.row = row
self.prev = prev
self.moves = moves
def set_moves(self, moves):
self.moves = moves
def equals(self, other):
return isinstance(other, Square) and self.col == other.col and self.row == other.row
def __repr__(self):
return "(%d, %d)" % (self.row, self.col)
class CaptureThemAll:
visited = []
def is_valid_square(self, c, r):
""" Square is valid if row, col is in range [0, 8) and
square hasn't been visited before """
return r >= 0 and r < 8 and c >= 0 and c < 8 and not self.visited[r][c]
def gen_all_neighbours(self, s):
neighbours = []
moves = s.moves + 1
for k in range(2):
for i in [-2, 2]:
for j in [-1, 1]:
if k:
r, c = s.row + i, s.col + j
else:
c, r = s.col + i, s.row + j
if self.is_valid_square(c, r):
neighbours.append(Square(c, r, s, moves))
return neighbours
def fastKnight(self, knight, rook, queen):
self.visited = [[0]*8 for i in range(8)]
queue = deque()
k = Square(ord(knight[0]) - 97, int(knight[1]) - 1, None, 0)
r = Square(ord( rook[0]) - 97, int( rook[1]) - 1)
q = Square(ord( queen[0]) - 97, int( queen[1]) - 1)
queue.append(k)
found = 0
while queue:
s = queue.popleft()
self.visited[s.row][s.col] = 1
if r.equals(s) or q.equals(s):
if not found:
# The first of rook/queen was found
found += 1
self.visited[s.prev.row][s.prev.col] = 0
queue.clear()
else:
# The second of rook/queen was found
return s.moves
neighbours = self.gen_all_neighbours(s)
queue.extend(neighbours)
return -1
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.