Teaching Kids Programming – Back Tracking Algorithm to Find the The Knight’s Tour Path (Recursive Depth First Search)

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given two positive integers m and n which are the height and width of a 0-indexed 2D-array board, a pair of positive integers (r, c) which is the starting position of the knight on the board. Your task is to find an order of movements for the knight, in a manner that every cell of the board gets visited exactly once (the starting cell is considered visited and you shouldn’t visit it again). Return the array board in which the cells’ values show the order of visiting the cell starting from 0 (the initial place of the knight).

Note that a knight can move from cell (r1, c1) to cell (r2, c2) if 0 <= r2 <= m – 1 and 0 <= c2 <= n – 1 and min(abs(r1 – r2), abs(c1 – c2)) = 1 and max(abs(r1 – r2), abs(c1 – c2)) = 2.

Example 1:
Input: m = 1, n = 1, r = 0, c = 0
Output: [[0]]
Explanation: There is only 1 cell and the knight is initially on it so there is only a 0 inside the 1×1 grid.

Example 2:
Input: m = 3, n = 4, r = 0, c = 0
Output: [[0,3,6,9],[11,8,1,4],[2,5,10,7]]
Explanation: By the following order of movements we can visit the entire board.
(0,0)->(1,2)->(2,0)->(0,1)->(1,3)->(2,1)->(0,2)->(2,3)->(1,1)->(0,3)->(2,2)->(1,0)

Constraints:
1 <= m, n <= 5
0 <= r <= m – 1
0 <= c <= n – 1
The inputs will be generated such that there exists at least one possible order of movements with the given condition

Back Tracking Algorithm to Find the The Knight’s Tour Path (Recursive Depth First Search)

The Knight’s Tour is a classic problem in chess that involves finding a sequence of moves that allows a knight to visit every square on a chessboard exactly once. This problem has fascinated mathematicians and computer scientists for centuries, and has been studied extensively in both fields. In this blog post, we’ll look at the problem: The Knight’s Tour, which asks us to implement a (backtracking or Depth First Search) algorithm to solve the Knight’s Tour problem. We’ll examine the given Python code and explain how it works.

The Knight’s Tour Problem

Below are the problem description:
“Given a chessboard of size m x n, starting at the position (r, c), find a sequence of moves by a knight on a chessboard that visits every square exactly once.”

The input to the function tourOfKnight consists of the following parameters:
rows: an integer representing the number of rows in the chessboard
cols: an integer representing the number of columns in the chessboard
r: an integer representing the row of the starting position
c: an integer representing the column of the starting position

The output of the function is a two-dimensional list of integers representing the sequence of moves made by the knight. Each element of the list corresponds to a square on the chessboard, and its value represents the order in which that square was visited by the knight.

The Algorithm: Back Tracking / Depth First Search

The following Python code implements a backtracking algorithm to solve the Knight’s Tour problem. It implements the Back tracking (using Recursive Depth First Search) to solve the Knight’s Tour problem:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def tourOfKnight(self, rows: int, cols: int, r: int, c: int) -> List[List[int]]:        
        self.ans = [[-1] * cols for _ in range(rows)]
 
        def dfs(rr, cc, n):
            if n == rows * cols:
                return True
            d = ((1, 2), (1, -2), (-1, 2), (-1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1))            
            for dr, dc in d:
                nr, nc = dr + rr, dc + cc
                if 0 <= nr < rows and 0 <= nc < cols and self.ans[nr][nc] == -1:
                    self.ans[nr][nc] = n
                    if dfs(nr, nc, n + 1):
                        return True
                    self.ans[nr][nc] = -1
            return False
 
        self.ans[r][c] = 0
        dfs(r, c, 1)
        return self.ans

class Solution:
    def tourOfKnight(self, rows: int, cols: int, r: int, c: int) -> List[List[int]]:        
        self.ans = [[-1] * cols for _ in range(rows)]

        def dfs(rr, cc, n):
            if n == rows * cols:
                return True
            d = ((1, 2), (1, -2), (-1, 2), (-1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1))            
            for dr, dc in d:
                nr, nc = dr + rr, dc + cc
                if 0 <= nr < rows and 0 <= nc < cols and self.ans[nr][nc] == -1:
                    self.ans[nr][nc] = n
                    if dfs(nr, nc, n + 1):
                        return True
                    self.ans[nr][nc] = -1
            return False

        self.ans[r][c] = 0
        dfs(r, c, 1)
        return self.ans

The algorithm works as follows:

Initialize a two-dimensional list ans of size rows x cols to -1. This 2D array/list will be used to keep track of the sequence of moves made by the knight.

Define a recursive function dfs (Depth First Search) that takes three parameters: the row and column of the current position on the chessboard, and the current move number. If the current move number is equal to the total number of squares on the chessboard, return True to indicate that a valid solution (path) has been found. Otherwise, try each of the eight possible knight moves from the current position. If a move leads to a valid square that has not been visited yet (equals to -1), mark that square with the current move number and recursively call dfs with the new position and move number. If dfs returns True, return True to propagate the solution up the call stack. Otherwise, undo the move by resetting the value of the current square to -1 and continue with the next move.

Mark the starting square with move number 0 and call dfs with the starting position and move number 1.

Return the final ans list.

Let’s take a closer look at the implementation of Depth First Search. The function first checks whether the current move number is equal to the total number of squares on the chessboard. If so, it returns True to indicate that a valid solution has been found. Otherwise, it defines a list d of all eight possible knight moves from the current position. For each move, it calculates the new row and column indices nr and nc and checks whether they are valid indices on the chessboard and whether the corresponding square has not been visited yet (i.e., its value in ans is still -1). If these conditions are met, it marks the new square with the current move number, recursively calls dfs with the new position and move number, and checks whether the recursive call returns True. If so, it returns True to propagate the solution up the call stack. Otherwise, it undoes the move by resetting the value of the new square to -1 and continues with the next move.

The given Python code correctly implements the backtracking algorithm for the Knight’s Tour problem. It initializes the ans list to -1, marks the starting square with move number 0, and calls dfs with the starting position and move number 1. Finally, it returns the ans list, which now contains the sequence of moves made by the knight.

Let’s now analyze the time and space complexity of the algorithm. The time complexity of the algorithm is O(8^(n^2)), where n is the maximum dimension of the chessboard. This is because there are 8 possible knight moves from each square on the chessboard, and the number of squares on the chessboard is n^2. Therefore, the worst-case scenario is when the algorithm must try all possible moves from all squares on the chessboard. The space complexity of the algorithm is also O(n^2), since we need to maintain the ans list of size n^2 to keep track of the sequence of moves made by the knight.

In conclusion, The Knight’s Tour asks us to implement a backtracking algorithm to solve the Knight’s Tour problem. The given Python code correctly implements this algorithm, initializing a two-dimensional list to -1, defining a recursive function to try all possible moves from each square on the chessboard, and returning the sequence of moves made by the knight. The time and space complexity of the algorithm are O(8^n)) and O(n^2), respectively.

The time complexity of the algorithm is indeed O(8^n), where n is the total number of squares on the chessboard. Each square on the chessboard can have up to 8 possible moves, so the number of possible moves from a given square is constant (i.e., independent of the size of the chessboard). Therefore, the total number of recursive calls made by the algorithm is proportional to the total number of squares on the chessboard.

Another interesting problme: Knight Tour in Python

–EOF (The Ultimate Computing & Technology Blog) —