58. Backtracking Algorithms: N-Queens Problem Concept

Backtracking is an algorithmic technique used for solving constraint satisfaction problems (CSPs). It systematically searches for a solution by attempting to extend a partial solution incrementally.

Core Mechanism

1. Build: Start with an empty solution.
2. Test: If the current partial solution is invalid or violates constraints, stop (pruning).
3. Recurse: If the partial solution is valid, try to extend it further.
4. Backtrack: If no extension works, undo the last choice and try the next alternative.

Example: N-Queens Problem

Goal: Place N chess queens on an N x N chessboard such that no two queens attack each other.

• Approach: Place one queen per row.
• Process: Place a queen in the first column of the first row. Check if it's safe. If safe, move to the next row. If unsafe, or if all options in the next row fail, backtrack and move the queen in the current row to the next column, trying again.