We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

The Knight’s Tour

Number: 2823

Difficulty: Medium

Paid? Yes

Companies: Microsoft

Problem Description

Given the dimensions m x n of a board and a starting position (r, c) for a knight, find a sequence of moves by which the knight visits every cell on the board exactly once (the starting cell is counted as visited and must not be revisited). The board must be returned with each cell’s value indicating the order in which it was visited (starting from 0).

Key Insights

  • This is a typical knight’s tour problem, solved using a backtracking/DFS approach.
  • The knight’s valid moves are defined such that the smaller absolute difference in coordinates is 1 and the larger is 2.
  • The board is small (m, n are at most 5), so an exhaustive backtracking solution is feasible.
  • Mark each visited cell with the step count and backtrack if no valid moves are available.
  • When all cells are filled, the path represents a valid knight tour.

Space and Time Complexity

Time Complexity: O(8^(mn)) in the worst case (exponential backtracking search, acceptable due to small board size). Space Complexity: O(mn) for the recursion stack and board storage.

Solution

We solve this problem using a DFS backtracking algorithm. We initiate an m x n board filled with a marker (e.g., -1) to indicate unvisited cells and mark the starting cell with 0. At each step, we try all possible knight moves. A move is valid if it lands within board boundaries and the cell is still unvisited.

We recursively explore each valid move, marking the cell with the current move number. If we eventually fill all cells (i.e., the move number reaches m * n), we have found a valid tour. If a move leads to a dead-end, we backtrack by resetting the cell’s value and trying a different move.

Key data structures and techniques:

  • A 2D array (list or vector) for the board.
  • A list (or array) that stores the eight possible moves of the knight.
  • Recursive DFS with backtracking to explore potential move sequences.
  • Boundary-checking and visited-checking logic to prune invalid moves.

Code Solutions

# Python implementation of the Knight's Tour solution
def knightsTour(m, n, r, c):
    # Initialize board with -1 indicating unvisited cells
    board = [[-1 for _ in range(n)] for _ in range(m)]
    # All 8 possible knight moves: (row_change, col_change)
    moves = [(-2, -1), (-2, 1), (-1, -2), (-1, 2),
             (1, -2), (1, 2), (2, -1), (2, 1)]
    
    # Recursive function for DFS backtracking
    def dfs(x, y, move_count):
        # Base case: if all cells are visited, return True
        if move_count == m * n:
            return True
        
        # Explore all possible knight moves
        for dx, dy in moves:
            new_x = x + dx
            new_y = y + dy
            # Check if new position is within bounds and unvisited
            if 0 <= new_x < m and 0 <= new_y < n and board[new_x][new_y] == -1:
                board[new_x][new_y] = move_count  # Mark the cell with current move number
                # Recurse from new cell with increased move count
                if dfs(new_x, new_y, move_count + 1):
                    return True
                # Backtrack: reset the cell value if no progress is made
                board[new_x][new_y] = -1
        return False

    # Starting cell marked as move 0
    board[r][c] = 0
    # Start DFS from the starting position
    dfs(r, c, 1)
    return board

# Example usage:
# m, n, r, c = 3, 4, 0, 0
# result = knightsTour(m, n, r, c)
# print(result)
← Back to All Questions