Backtracking- N Queens Problem
Backtracking
Backtracking is an important algorithm design technique used for solving problems where we have to make a sequence of choices and find a solution satisfying a set of constraints.
A very simple way to think about backtracking is:
Make a choice → continue with that choice → if it leads to a dead end, undo the choice and try another choice.
The N-Queens problem is one of the best examples for understanding backtracking.
1. What is Backtracking?
Suppose you are solving a problem and at every step you have several choices.
For example:
Start / | \ A B C / \ / \ D E F G
Suppose we choose:
Start → A → E
but later discover that E cannot lead to a valid solution.
Instead of starting the entire problem again, we:
- Go back to the previous decision.
- Undo the choice.
- Try another possibility.
This process is called backtracking.
2. Basic Idea
The general pattern is:
Make a choice ↓ Is it promising? / \ YES NO ↓ ↓ Continue Reject ↓ Solution found? / \ YES NO ↓ ↓ Return Backtrack ↓ Try another choice
The important word is backtrack.
It means:
Go back to the previous decision point and try another choice.
3. Backtracking and Brute Force
Backtracking is related to brute-force search, but it is usually more efficient because it can stop exploring a choice as soon as it knows that choice cannot produce a valid solution.
For example, suppose we are trying to construct:
A → B → C → ?
and at this point we know that no possible choice can satisfy the constraints.
A brute-force method may continue exploring possibilities.
Backtracking says:
"This partial solution cannot work. Stop exploring this branch."
This is called pruning the search space.
4. Backtracking as a State-Space Tree
A useful way to visualize backtracking is using a state-space tree.
Each node represents a partial solution.
For example:
Start / | \ A B C / \ | D E F
Each path from the root represents a sequence of choices.
Some branches eventually produce a solution.
Other branches are rejected because they violate a constraint.
So the backtracking algorithm performs a depth-first search of the state-space tree.
5. Control Abstraction of Backtracking
A control abstraction is a general framework that describes the structure of a backtracking algorithm without depending on a particular problem.
A simple recursive form is:
BACKTRACK(k) if a complete solution is obtained process the solution else generate possible choices for each choice if choice is promising make the choice BACKTRACK(k + 1) undo the choice
The important steps are:
1. Generate a choice 2. Check whether it is promising 3. Make the choice 4. Recursively continue 5. Undo the choice if necessary
The undo step is what gives backtracking its name.
6. What Does "Promising" Mean?
A choice is called promising if it still has the possibility of producing a valid solution.
For example, in the N-Queens problem:
Place a queen ↓ Does it attack an already placed queen? ↓ YES → Reject ↓ NO ↓ Continue
If a queen attacks another queen, there is no point continuing with that arrangement.
Therefore, we prune that branch.
7. N-Queens Problem
The N-Queens problem asks:
Place N queens on an N × N chessboard such that no two queens attack each other.
A queen can attack another queen if they are in:
- the same row,
- the same column, or
- the same diagonal.
Therefore, the final arrangement must satisfy:
No two queens in the same row No two queens in the same column No two queens on the same diagonal
8. Example: 4-Queens Problem
For:
we need to place 4 queens on a 4 × 4 chessboard.
One valid solution is:
. Q . . . . . Q Q . . . . . Q .
Here:
Q = Queen . = Empty square
The queen positions are:
Row 1 → Column 2 Row 2 → Column 4 Row 3 → Column 1 Row 4 → Column 3
So we can represent the solution as:
[2,4,1,3]This means:
Row 1 → column 2 Row 2 → column 4 Row 3 → column 1 Row 4 → column 3
9. Why Backtracking Is Suitable for N-Queens
We can place queens one row at a time.
For every row:
Try column 1 Try column 2 Try column 3 Try column 4
Whenever we place a queen, we check whether it is safe.
If it is safe:
Continue to next row
If it is not safe:
Reject this position Try another column
If we reach a row where no column is possible, we backtrack to the previous row.
10. Example
11. Backtracking in Action
Suppose our partial solution is:
Q . . . . . . Q . Q . .
Now we try to place the fourth queen.
If every possible position in row 4 is unsafe:
No valid position ↓ Backtrack ↓ Remove queen from row 3 ↓ Try another position in row 3
This is the key idea.
We don't discard everything.
We simply go back to the most recent decision and try another possibility.
12. N-Queens Algorithm
A simple recursive algorithm is:
N-QUEENS(row) if row > N print solution return for column = 1 to N if position(row, column) is safe place queen at (row, column) N-QUEENS(row + 1) remove queen from (row, column)
The important part is:
place queen ↓ recursive call ↓ remove queen
The last operation is the backtracking step.
13. Checking Whether a Position Is Safe
Suppose we want to place a queen at:
(row,column)We need to check three conditions.
1. Same column
There must not already be a queen in the same column.
2. Same diagonal
Two positions:
(row1,column1)and
(row2,column2)are on the same diagonal if:
Therefore, a position is safe if:
No queen in same column AND No queen in same diagonal
Because we place one queen per row, we don't need to check the same row.
14. Simple Pseudocode
NQUEENS(row) if row > N print the solution return for col = 1 to N if SAFE(row, col) board[row] = col NQUEENS(row + 1) board[row] = 0
Here:
board[row] = col
means:
Place the queen in this row and column.
And:
board[row] = 0
means:
Remove the queen because we are backtracking.
15. How the Search Looks
For the 4-Queens problem, conceptually:
Row 1 / | | \ C1 C2 C3 C4 × ↓ ↓ × Row 2 / | \ ... ... ... ↓ Row 3 ↓ No choice ↑ BACKTRACK | Try another choice ↓ Row 4 ↓ SOLUTION
The × branches are eliminated because they are not promising.
16. Why Backtracking Is Better Than Trying Every Arrangement
For N queens, each row has approximately N possible columns.
A simple brute-force approach could consider approximately:
N^Narrangements.
Backtracking avoids exploring many of these arrangements because it rejects a partial arrangement as soon as it violates a constraint.
Therefore:
Backtracking does not necessarily reduce the worst-case exponential nature of the problem, but it can greatly reduce the amount of search in practice by pruning invalid partial solutions early.
17. Complexity of N-Queens
The exact running time depends on how the algorithm checks whether a position is safe and how much pruning occurs.
For a simple backtracking implementation, the worst-case search is exponential.
A commonly used upper-bound description is:
O(N^N)for the straightforward formulation where each of the N rows considers N columns.
With better organization—such as ensuring one queen per row and column—the search space can be reduced substantially, but the problem remains exponential in the worst case.
The main point to remember is:
N-Queens using backtracking has exponential worst-case complexity.18. Backtracking vs Dynamic Programming
This comparison is useful when teaching algorithm design.
| Backtracking | Dynamic Programming |
|---|---|
| Explores possible choices | Solves overlapping subproblems |
| Uses a state-space tree | Uses a table/memoization |
| Rejects invalid choices early | Stores previously solved subproblems |
| Usually uses recursion | Often uses bottom-up tables |
| Example: N-Queens | Example: Matrix Chain Multiplication |
| Worst case often exponential | Often polynomial |
19. Important Terms
State
The current partial solution.
Example:
[2,4,1]
means queens have been placed in the first three rows.
Choice
A possible next decision.
Example:
Place queen in column 3 of row 4
Promising
The current partial solution does not violate the constraints.
Non-promising
The current partial solution cannot lead to a valid solution.
Backtrack
Undo the most recent choice and try another choice.
Pruning
Stop exploring a branch once it is known that the branch cannot produce a solution.
20. Summary
Backtracking is a systematic trial-and-error technique. We build a solution step by step. At each step, we try one possible choice and check whether the partial solution is promising. If it is promising, we continue recursively. If it is not promising, we reject that choice immediately. If we reach a dead end, we undo the previous choice and try another one. The N-Queens problem is a classic example. We place one queen in each row and check whether the new queen conflicts with any previously placed queen. If no safe position exists in a row, we backtrack to the previous row and move its queen to another column.
The core pattern
Choose ↓ Check ↓ Is it safe? / \ Yes No ↓ ↓ Continue Reject ↓ Dead end? / \ No Yes ↓ ↓ Continue Backtrack ↓ Try again
In one sentence:
Backtracking = Try → Check → Continue → Undo → Try another
Comments
Post a Comment