Problem Statement
Explain the backtracking technique with the N-Queens problem as an example. How does it differ from brute force?
Explanation
Backtracking is an algorithmic technique for solving problems by trying to build a solution incrementally and abandoning candidates as soon as it determines they cannot lead to a valid solution. This pruning of the search space makes it more efficient than brute force.
The backtracking approach follows a general pattern. Start with an empty solution. At each step, try to extend the partial solution by adding one more element. Check if the current partial solution is valid using constraint checking. If valid, recursively continue building the solution. If the partial solution violates constraints or cannot lead to a complete solution, backtrack by removing the last added element and try a different choice. If a complete valid solution is found, record it. Continue until all possibilities are explored.
The N-Queens problem asks to place N queens on an N by N chessboard such that no two queens attack each other. Queens attack horizontally, vertically, and diagonally. The backtracking solution works row by row. For each row, try placing the queen in each column. Check if placing the queen in current position is safe by verifying no queen in previous rows attacks this position. If safe, mark this position and recursively solve for the next row. If recursive call returns false meaning no solution found, unmark this position and try next column. If all columns tried without success, backtrack to previous row. If all N queens are placed successfully, a solution is found.
The safe check verifies three conditions. First, check the column to ensure no queen in the same column in previous rows. Second, check the left diagonal by verifying positions where row minus column is constant. Third, check the right diagonal by verifying positions where row plus column is constant. We only check previous rows because we place queens row by row.
Comparing backtracking to brute force shows significant efficiency gains. Brute force would try all possible placements of N queens on N squared positions and then check if valid. This gives C of N squared choose N possibilities, which is astronomical even for small N. For N equals 8, this is over 4 billion combinations. Backtracking prunes invalid partial solutions early. If placing a queen makes position invalid, we do not explore any completions of that partial solution. For 8-Queens, backtracking explores around 15,000 nodes compared to billions in brute force.
The time complexity of backtracking is O of N factorial in worst case for N-Queens, as we have N choices for first row, N minus 1 for second row after pruning, and so on. However, practical performance is much better due to pruning. Space complexity is O of N for the recursion stack and the board representation.
Backtracking is applicable to many problems including Sudoku solver where we try numbers 1 to 9 in empty cells and backtrack if invalid, generating all permutations or combinations by building them element by element, solving constraint satisfaction problems, maze solving where we try paths and backtrack if we hit dead ends, and the knapsack problem with constraints. The key advantage is pruning the search space by abandoning partial solutions that violate constraints, making it far more efficient than exhaustive brute force.