---

📘 Example Problem on Backtracking: N-Queens Problem

1️⃣ Introduction

The N-Queens problem is a classical problem used to explain the Backtracking algorithm design technique.

🔹 Problem Statement

Place N queens on an N × N chessboard such that:

• No two queens attack each other
• That means:
  • No two queens in the same row
  • No two queens in the same column
  • No two queens on the same diagonal

---

2️⃣ Why N-Queens Uses Backtracking

• Each queen placement is a decision
• If a conflict occurs, we undo (backtrack) the decision
• The solution is built incrementally
• Exhaustive search is avoided by pruning invalid states

---

3️⃣ Basic Idea of Backtracking in N-Queens

1. Place one queen in a row
2. Check if the position is safe
3. If safe, move to the next row
4. If not safe, try next column
5. If no column works, backtrack to previous row

---

4️⃣ Representation of the Solution

• Use a 1-D array board[]
• board[i] = j means
  Queen is placed in row i, column j

---

5️⃣ Safety Condition (Key Logic)

A queen at position (row, col) is safe if:

• No queen is in the same column
• No queen is on the left diagonal
• No queen is on the right diagonal

🔹 Mathematical Conditions

For all previous rows i < row:

• board[i] ≠ col
• |board[i] − col| ≠ |i − row|

---

6️⃣ Algorithm for N-Queens (Backtracking)

🔹 Pseudocode

NQueen(row):
   if row == N:
       print solution
       return

   for col = 0 to N-1:
       if isSafe(row, col):
           board[row] = col
           NQueen(row + 1)
           board[row] = -1   // backtrack

---

🔹 isSafe Function

isSafe(row, col):
   for i = 0 to row-1:
       if board[i] == col
          or |board[i] - col| == |i - row|:
           return false
   return true

---

7️⃣ Example: 4-Queens Problem

🔹 One Valid Solution

Row	Column
0	1
1	3
2	0
3	2

🔹 Board Representation

. Q . .
. . . Q
Q . . .
. . Q .

✔ No queens attack each other

---

8️⃣ State Space Tree (Concept)

• Each level represents a row
• Each branch represents a column choice
• Invalid branches are pruned early

This drastically reduces search space compared to brute force.

---

9️⃣ Time and Space Complexity

🔹 Time Complexity

• Worst case: O(N!)
• Practical performance is much better due to pruning

🔹 Space Complexity

• Board array: O(N)
• Recursion stack: O(N)

---

🔟 Advantages of Using Backtracking

✔ Avoids unnecessary computations
✔ Systematic exploration
✔ Efficient compared to brute force

---

1️⃣1️⃣ Limitations

✖ High time complexity for large N
✖ Recursive overhead

---

1️⃣2️⃣ Applications of N-Queens / Backtracking

• Sudoku solver
• Graph coloring
• Hamiltonian paths
• Puzzle solving

---

🔚 Conclusion

The N-Queens problem is a classic example that demonstrates the power of backtracking in solving constraint-satisfaction problems.

Backtracking explores all possibilities but abandons paths that violate constraints early.

---