Teaching Kids Programming – Multi-source Breadth First Search Algorithm (Minimum Number of Moves to Capture the King)

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given a two-dimensional integer matrix board containing 0s, 1s and 2s representing some n x n chessboard. Each 0 represents an empty cell, 1 represents the knight and 2 represents the king. There is at least one knight but exactly one king.

Given that the king stays still, return the minimum number of moves it would take for some knight to land on the king. If there’s no solution, return -1. A knight can’t land on another knight.

Constraints
2 ≤ n ≤ 500 where n is the number of rows and columns in board
1 ≤ t < n * n where t is the number of knights
k = 1 where k is the number of kings.

Example 1
Input

1 2 3 4 5 6 7

board = [     [1, 0, 0, 0, 0],     [0, 0, 0, 0, 0],     [0, 0, 0, 0, 2],     [1, 0, 0, 0, 0],     [0, 0, 0, 0, 0] ]

board = [
    [1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 2],
    [1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0]
]

Output
2

Explanation
The knight on top left corner can jump twice to land on the king.

Example 2
Input

1 2 3 4

board = [     [1, 2],     [1, 1] ]

board = [
    [1, 2],
    [1, 1]
]

Output
-1
Explanation
There is no way to land on the king here.

Try Traversing all the knights simultaneously.
Start with king.
Don’t let a knight touch the square touched by another knight. A knight is a knight and if one has been there before no need for others to follow in its footsteps and give less optimal solution.

Multi-source Breadth First Search Algorithm (Minimum Number of Moves to Capture the King)

We have multiple Knights and we can append them to the queue initially which is the essential of multi-source Breadth First Search Algorithm. Assuming N positions in the board, and the number of maximum edges are (we can visualize the Board as undirectional Graph, each position is a vertex and each valid move forms an edge):

which is

Note that the actual number of edges is way smaller considering invalid edges such as the Knight traverses in a shape of offset (1, 2), (2, 1) …

For a knight, next move could be maximum 8 positions if those are still valid within the board. If a position is occupied with another knight, there is no point in pushing it to the queue as it will be always quicker to start from that knight instead.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Solution:
    def solve(self, board):
        EMPTY = 0
        KNIGHT = 1
        KING = 2
 
        rows = len(board)
        cols = len(board[0])
 
        q = deque()
        for r in range(rows):
            for c in range(cols):
                if board[r][c] == KNIGHT:
                    q.append((r, c))
 
        ans = -1
        seen = set()
        while q:
            ans += 1
            n = len(q)
            for _ in range(n):
                r, c = q.popleft()
                if board[r][c] == KING:
                    return ans
                for dr, dc in ((1, -2), (1, 2), (2, -1), (2, 1), (2, -1), \
                                (-1, 2), (-1, -2), (-2, 1), (-2, -1)):
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in seen\
                        and board[nr][nc] != KNIGHT:
                        seen.add((nr, nc))
                        q.append((nr, nc))
 
        return -1

class Solution:
    def solve(self, board):
        EMPTY = 0
        KNIGHT = 1
        KING = 2

        rows = len(board)
        cols = len(board[0])

        q = deque()
        for r in range(rows):
            for c in range(cols):
                if board[r][c] == KNIGHT:
                    q.append((r, c))

        ans = -1
        seen = set()
        while q:
            ans += 1
            n = len(q)
            for _ in range(n):
                r, c = q.popleft()
                if board[r][c] == KING:
                    return ans
                for dr, dc in ((1, -2), (1, 2), (2, -1), (2, 1), (2, -1), \
                                (-1, 2), (-1, -2), (-2, 1), (-2, -1)):
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in seen\
                        and board[nr][nc] != KNIGHT:
                        seen.add((nr, nc))
                        q.append((nr, nc))

        return -1

The space complexity is O(N) as we are using a hash set to remember the positions that we have visited and also we use a queue (aka deque) to implement the multi-source Breadth First Search Algorithm.

The time complexity is where M is the number of the knights, and since the time complexity is .

There is only 1 king i.e. the number of Kings is smaller than the number of Knights, and thus we can reverse the process, start the search from the King instead:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Solution:
    def solve(self, board):
        EMPTY = 0
        KNIGHT = 1
        KING = 2
 
        rows = len(board)
        cols = len(board[0])
 
        q = deque()
        for r in range(rows):
            for c in range(cols):
                if board[r][c] == KING:
                    q.append((r, c))
                    # if there is only 1 king - we can break here
                    break
 
        ans = -1
        seen = set()
        while q:
            ans += 1
            n = len(q)
            for _ in range(n):
                r, c = q.popleft()
                if board[r][c] == KNIGHT:
                    return ans
                for dr, dc in ((1, -2), (1, 2), (2, -1), (2, 1), (2, -1), \
                                (-1, 2), (-1, -2), (-2, 1), (-2, -1)):
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in seen:
                        seen.add((nr, nc))
                        q.append((nr, nc))
 
        return -1

class Solution:
    def solve(self, board):
        EMPTY = 0
        KNIGHT = 1
        KING = 2

        rows = len(board)
        cols = len(board[0])

        q = deque()
        for r in range(rows):
            for c in range(cols):
                if board[r][c] == KING:
                    q.append((r, c))
                    # if there is only 1 king - we can break here
                    break

        ans = -1
        seen = set()
        while q:
            ans += 1
            n = len(q)
            for _ in range(n):
                r, c = q.popleft()
                if board[r][c] == KNIGHT:
                    return ans
                for dr, dc in ((1, -2), (1, 2), (2, -1), (2, 1), (2, -1), \
                                (-1, 2), (-1, -2), (-2, 1), (-2, -1)):
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in seen:
                        seen.add((nr, nc))
                        q.append((nr, nc))

        return -1

The time complexity is as we at most visit each edge once. The space complexity is O(N).

–EOF (The Ultimate Computing & Technology Blog) —