> For the complete documentation index, see [llms.txt](https://zedive.gitbook.io/project-l/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zedive.gitbook.io/project-l/part-2/graph-search/search-in-a-grid/shortest-knight-path.md).

# 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
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## 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, and the optional `goal` query parameter:

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

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

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.