Solving N-Queens with Backtracking

1. Understanding the N-Queens Problem with Backtracking

At its heart, the N-Queens problem is about finding a valid arrangement. We can try to build a solution incrementally. A simple and effective strategy is to place one queen in each row, starting from row 0.

This approach fits our backtracking template perfectly:

1. Choose: In the current row, pick a column and place a queen in that cell.
2. Explore: If the placement is valid (doesn't conflict with previously placed queens), recursively move to the next row to place the next queen.
3. Unchoose: If we can't place a queen in the next row (a dead end), we backtrack to the previous row, remove the queen we placed, and try placing it in the next column.

This process systematically explores all possible placements, pruning entire branches of the search tree as soon as a conflict is detected.

The best way to understand this is to see it in action. The following video provides an excellent animated walkthrough for the 4-Queens problem.

As you saw, the algorithm explores a state-space tree, where each level of the tree corresponds to a row on the chessboard.

2. The isSafe Function: The Core Constraint

The new challenge in this problem, compared to generating combinations, is the validity check. Before placing a queen at (row, col), we must verify that it is not attacked by any queen already placed in previous rows (from 0 to row - 1).

Since our strategy is to place one queen per row, we don't need to check for horizontal attacks in the same row. We only need to check three directions for attacks from queens in previous rows:

1. Vertical Attack: Is there a queen in the same column col in any previous row?
2. Upper-Left Diagonal Attack: Is there a queen on the main diagonal extending upwards and to the left?
3. Upper-Right Diagonal Attack: Is there a queen on the anti-diagonal extending upwards and to the right?

The takeuforward article provides a very clear explanation and implementation of this logic. While it processes the board column by column, the isSafe logic for checking previous placements is identical.

Let's adapt that logic for our row-by-row traversal. To check if (row, col) is safe, we iterate i from 0 to row - 1 and check for queens at (i, j):

• Vertical: j == col
• Diagonals: The key property of diagonals is that the absolute difference of row and column indices is constant. So, Math.abs(row - i) == Math.abs(col - j).

3. Java Implementation

Now we can assemble the complete Java solution. The structure will be very familiar to you from our previous lessons.

import java.util.ArrayList;
import java.util.List;

public class NQueensSolution {

    public List<List<String>> solveNQueens(int n) {
        List<List<String>> allSolutions = new ArrayList<>();
        char[][] board = new char[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] = '.';
            }
        }
        solve(0, board, allSolutions);
        return allSolutions;
    }

    private void solve(int row, char[][] board, List<List<String>> allSolutions) {
        // Base Case: If we have successfully placed a queen in every row from 0 to n-1
        if (row == board.length) {
            allSolutions.add(constructSolution(board));
            return;
        }

        // Iterate through all columns in the current row
        for (int col = 0; col < board.length; col++) {
            if (isSafe(board, row, col)) {
                // 1. Choose: Place the queen
                board[row][col] = 'Q';

                // 2. Explore: Recurse to the next row
                solve(row + 1, board, allSolutions);

                // 3. Unchoose (Backtrack): Remove the queen to explore other possibilities
                board[row][col] = '.';
            }
        }
    }

    private boolean isSafe(char[][] board, int row, int col) {
        // Check for queens in the same column (upwards)
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 'Q') {
                return false;
            }
        }

        // Check for queens in the upper-left diagonal
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }

        // Check for queens in the upper-right diagonal
        for (int i = row - 1, j = col + 1; i >= 0 && j < board.length; i--, j++) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }

        return true;
    }

    // Helper function to convert the char[][] board to a List<String>
    private List<String> constructSolution(char[][] board) {
        List<String> solution = new ArrayList<>();
        for (int i = 0; i < board.length; i++) {
            solution.add(new String(board[i]));
        }
        return solution;
    }
}

This code directly maps to our backtracking template and the logic we've discussed. The solve function manages the recursion, and the isSafe function enforces the rules of the puzzle.

4. Optimization & Complexity Analysis

For an interview, it's crucial to discuss performance. The isSafe function in our current implementation takes O(N) time because it iterates up the board. We can do better.

Optimization

We can optimize the safety check to O(1) by using extra space. We can use boolean arrays or hash sets to keep track of which columns and diagonals are currently under attack.

• usedCols[col]: A boolean array to mark attacked columns.
• upperLeftDiag[row - col + n - 1]: Marks attacked main diagonals. The row - col value is constant for each main diagonal. We add n-1 to shift the index to be non-negative.
• upperRightDiag[row + col]: Marks attacked anti-diagonals. The row + col value is constant for each anti-diagonal.

The takeuforward article discusses this exact optimization in its "Optimal Approach" section.

This optimization significantly improves performance and is an excellent point to bring up in an interview to demonstrate a deeper understanding of the problem.

Complexity Analysis

• Time Complexity: O(N!)
  • This is a loose upper bound. In the first row, we have N choices, in the second, we have at most N-1, and so on. The algorithm explores a search space that is a subset of all permutations of N queens in N columns.
  • Because backtracking prunes the search tree whenever a conflict is found, the actual number of operations is much less than N!, but it remains exponential.
• Space Complexity: O(N^2)
  • O(N^2) is required to store the chessboard itself.
  • The recursion depth is O(N), so the call stack uses O(N) space.
  • If you use the optimized approach, you'll need O(N) extra space for the tracking arrays.

The designgurus.io resource has a good summary of complexities for different approaches.

Conclusion

Congratulations! You've successfully applied the backtracking template to solve a classic constraint satisfaction problem. You've seen how a complex problem can be broken down into a recursive structure with a clear validation rule.

Key Takeaways:

• The N-Queens problem is solved by placing queens row-by-row and backtracking when a placement leads to a conflict.
• The core logic is encapsulated in the isSafe function, which checks for column and diagonal attacks from previously placed queens.
• The standard backtracking template (choose, explore, unchoose) works perfectly here, with the "choose" step being guarded by the isSafe check.
• For interview purposes, knowing the O(1) optimization for the safety check using hashing is a major plus.

Preview of the Next Lesson:
We will continue our journey with grid-based backtracking puzzles. In the next lesson, we will implement a backtracking algorithm to solve a Sudoku puzzle. You'll see once again how the same fundamental principles of choosing a value for a cell, checking its validity against puzzle rules, and backtracking on failure can be used to solve another complex problem.