http://community.topcoder.com/stat?c=problem_statement&pm=2915&rd=5853

CaptureThemAll.py

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