Shortest Knight Path

Question (LI.611)

Find the length of the shortest path for a knight to travel from the source point to the destination point in a chessboard. Return -1 if no path can be found.

Example

I: board = # 0 is open 1 is blocked 
[[0,0,0],
 [0,0,0],
 [0,0,0]]
source = [2, 0] 
destination = [2, 2]

O: 2 because (2, 0) -> (0, 1) -> (2, 2) 

I: board = 
[[0,1,0],
 [0,0,1],
 [0,0,0]]
source = [2, 0] destination = [2, 2] 
Output: -1 because no possible path 

Analysis

A simple bidirectional graph where the vertex is the position and the edge is a possible knight move from one position to another position. Searching for length on a simple graph is just BFS. A check in pre visit has to determine the next position is in-bound and open.

Code

from typing import Deque, List, Set, Tuple 
from collections import deque 

def shortestPath(
    grid: List[List[bool]], source: Point, destination: Point
) -> int:
    queue: Deque[Point] = deque()
    # hash(Point) is the memory address 
    # hash(Tuple) computes the hash of each element then combine (XOR) them 
    visited_set: Set[Tuple[int, int]] = set()

    queue.append(source)
    visited_set.add((source.x, source.y))

    levels = 0

    while len(queue) > 0:
        
        level_size = len(queue)

        for i in range(level_size):
            cur_point = queue.popleft()

            if cur_point.x == destination.x and cur_point.y == destination.y:
                return levels

            for step in find_next_steps(cur_point):
                if not is_in_bound(grid, step):
                    continue
                if grid[step.x][step.y]:
                    continue
                if (step.x, step.y) in visited_set:
                    continue
                queue.append(step)
                visited_set.add((step.x, step.y))
        levels += 1 

    return -1

def find_next_steps(pt: Point) -> List[Point]:

    return [
        Point(pt.x + 1, pt.y + 2),
        Point(pt.x + 1, pt.y - 2),
        Point(pt.x - 1, pt.y + 2),
        Point(pt.x - 1, pt.y - 2),
        Point(pt.x + 2, pt.y + 1),
        Point(pt.x + 2, pt.y - 1),
        Point(pt.x - 2, pt.y + 1),
        Point(pt.x - 2, pt.y - 1),
    ]


def is_in_bound(grid: List[List[bool]], pt: Point) -> bool:
    boundary_m = len(grid)
    boundary_n = len(grid[0])
    return pt.x >= 0 and pt.y >= 0 and pt.x < boundary_m and pt.y < boundary_n

Code

CPython default hash function for custom class is its memory address. You have to write a custom hash to dedup the equivalent values.

def shortestPath( 
    grid: List[List[bool]], source: Point, destination: Point
) -> int:
    queue: Deque[Point] = deque()
    visited_set: Set[Point] = set()

    queue.append(source)
    visited_set.add(custom_hash(source))

    levels = 0

    while len(queue) > 0:
        
        level_size = len(queue)

        for i in range(level_size):
            cur_point = queue.popleft()

            if cur_point.x == destination.x and cur_point.y == destination.y:
                return levels

            for step in find_next_steps(cur_point):
                if not is_in_bound(grid, step):
                    continue
                if grid[step.x][step.y]:
                    continue
                if custom_hash(step) in visited_set:
                    continue

                queue.append(step)
                visited_set.add(custom_hash(step))
        levels += 1 

    return -1

def custom_hash(pt: Point) -> int:
    return pt.x * 13 ** 1 + pt.y * 29 ** 2

Reference

• Wikipedia - Geometric hashing

• Stack Overflow - How does python compute the hash of a tuple