BackTrackingProblem 9 of 19

The Knights tour problem

Brute Force
Time: O(8^(n²))
Space: O(n²)
Optimal
Time: O(8^(n²))
Space: O(n²)

Problem Statement

Given an N×N chessboard, a knight starts from a given position and must visit every square exactly once. Print the order in which the knight visits each square, or determine that no solution exists.

Example:

Input: N = 8, starting position = (0, 0) Output: A sequence showing the order of visits (0 to 63) For N = 5, one possible solution: 0 11 16 21 6 17 22 7 12 15 8 1 10 5 20 23 18 3 14 9 2 13 4 19 4

Approach 1: Brute Force (Simple Backtracking)

Intuition

From each position, try all 8 possible knight moves. If a move leads to an unvisited square, mark it and recurse. If stuck, backtrack.

Algorithm

  1. Start from given position, mark it as visited (move 0)
  2. Try all 8 knight moves
  3. For each valid unvisited square, mark it and recurse
  4. If all squares visited, solution found
  5. If stuck, backtrack by unmarking
java
import java.util.*;

class Solution {
    // Knight's possible moves
    private int[] dx = {2, 1, -1, -2, -2, -1, 1, 2};
    private int[] dy = {1, 2, 2, 1, -1, -2, -2, -1};
    
    public boolean isValid(int x, int y, int n, int[][] board) {
        return x >= 0 && x < n && y >= 0 && y < n && board[x][y] == -1;
    }
    
    public boolean solve(int x, int y, int move, int n, int[][] board) {
        // All squares visited
        if (move == n * n) {
            return true;
        }
        
        // Try all 8 moves
        for (int i = 0; i < 8; i++) {
            int nextX = x + dx[i];
            int nextY = y + dy[i];
            
            if (isValid(nextX, nextY, n, board)) {
                board[nextX][nextY] = move;
                
                if (solve(nextX, nextY, move + 1, n, board)) {
                    return true;
                }
                
                board[nextX][nextY] = -1;  // Backtrack
            }
        }
        
        return false;
    }
    
    public void printBoard(int[][] board, int n) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print(board[i][j] + "\t");
            }
            System.out.println();
        }
    }
    
    public boolean knightsTour(int n, int startX, int startY) {
        int[][] board = new int[n][n];
        for (int[] row : board) Arrays.fill(row, -1);
        board[startX][startY] = 0;
        
        if (solve(startX, startY, 1, n, board)) {
            printBoard(board, n);
            return true;
        }
        
        System.out.println("No solution exists");
        return false;
    }
}

Complexity Analysis

  • Time Complexity: O(8^(n²)) - 8 choices at each of n² squares
  • Space Complexity: O(n²) - For the board

Approach 2: Optimal (Warnsdorff's Heuristic)

Intuition

Always move to the square with the fewest onward moves (most constrained). This greedy heuristic dramatically reduces backtracking.

Algorithm

  1. From current position, calculate onward moves for each possible next square
  2. Sort moves by number of onward moves (ascending)
  3. Try moves in this order
  4. This ensures we don't paint ourselves into a corner
java
import java.util.*;

class Solution {
    private int[] dx = {2, 1, -1, -2, -2, -1, 1, 2};
    private int[] dy = {1, 2, 2, 1, -1, -2, -2, -1};
    
    public boolean isValid(int x, int y, int n, int[][] board) {
        return x >= 0 && x < n && y >= 0 && y < n && board[x][y] == -1;
    }
    
    public int countOnwardMoves(int x, int y, int n, int[][] board) {
        int count = 0;
        for (int i = 0; i < 8; i++) {
            if (isValid(x + dx[i], y + dy[i], n, board)) {
                count++;
            }
        }
        return count;
    }
    
    public boolean solve(int x, int y, int move, int n, int[][] board) {
        if (move == n * n) {
            return true;
        }
        
        // Get all valid moves with their onward move counts
        List<int[]> moves = new ArrayList<>();
        for (int i = 0; i < 8; i++) {
            int nextX = x + dx[i];
            int nextY = y + dy[i];
            if (isValid(nextX, nextY, n, board)) {
                int onward = countOnwardMoves(nextX, nextY, n, board);
                moves.add(new int[]{onward, nextX, nextY});
            }
        }
        
        // Sort by number of onward moves (Warnsdorff's heuristic)
        moves.sort((a, b) -> a[0] - b[0]);
        
        // Try moves in order of least onward moves
        for (int[] m : moves) {
            int nextX = m[1];
            int nextY = m[2];
            
            board[nextX][nextY] = move;
            
            if (solve(nextX, nextY, move + 1, n, board)) {
                return true;
            }
            
            board[nextX][nextY] = -1;
        }
        
        return false;
    }
    
    public boolean knightsTour(int n, int startX, int startY) {
        int[][] board = new int[n][n];
        for (int[] row : board) Arrays.fill(row, -1);
        board[startX][startY] = 0;
        
        if (solve(startX, startY, 1, n, board)) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    System.out.print(board[i][j] + "\t");
                }
                System.out.println();
            }
            return true;
        }
        
        return false;
    }
}

Complexity Analysis

  • Time Complexity: O(8^(n²)) worst case, but practically much faster
  • Space Complexity: O(n²) - For the board

Key Takeaways

  1. Warnsdorff's Heuristic: Visit most constrained square first
  2. 8 Possible Moves: Knight moves in L-shape (2+1 or 1+2)
  3. Hamiltonian Path: Knight's tour is finding a Hamiltonian path
  4. Closed vs Open Tour: Closed tour returns to start, open doesn't
  5. Existence: For n ≥ 5, a tour always exists
  6. No Tour for n < 5: Except for n = 1 (trivial case)
Previous
Subset Sum Problem
Next
Tug of War