# Shortest Knight Path

## Question ([LI.611](https://www.lintcode.com/problem/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.  <br>

## Code&#x20;

```python
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&#x20;

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

```python
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&#x20;

* Wikipedia - [Geometric hashing](https://en.wikipedia.org/wiki/Geometric_hashing) &#x20;
* Stack Overflow - [How does python compute the hash of a tuple](https://stackoverflow.com/questions/49722196/how-does-python-compute-the-hash-of-a-tuple)&#x20;


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://zedive.gitbook.io/project-l/part-2/graph-search/search-in-a-grid/shortest-knight-path.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.