In our journey through algorithmic design paradigms, we've explored strategies for efficiency and elegance. Now, we delve into techniques that systematically explore potential solutions, particularly when faced with complex problems that don't yield to straightforward greedy or dynamic programming approaches. These techniques are Backtracking and Branch and Bound, powerful tools for navigating vast solution spaces.
Imagine you're trying to find your way through a maze. Backtracking is akin to exploring one path at a time. If you hit a dead end, you 'backtrack' to the last junction where you had a choice and try a different path. This systematic exploration ensures you don't miss any potential solutions, even if it means trying many routes.
Formally, backtracking is an algorithmic technique for solving problems recursively by trying to build a solution incrementally, one piece at a time, removing those solutions that fail to satisfy the constraints of the problem at any point in time. This is often visualized as traversing a search tree. Each node in the tree represents a partial solution, and we explore branches of this tree. If a partial solution cannot lead to a valid complete solution, we prune that branch and backtrack.
graph TD
A[Start] --> B{Choose an option?}
B -- Yes --> C[Add to partial solution]
C --> D{Is partial solution valid?}
D -- Yes --> E{Is it a complete solution?}
E -- No --> B
E -- Yes --> F[Solution found!]
D -- No --> G[Backtrack]
B -- No --> G
G --> H{Are there other options at previous step?}
H -- Yes --> B
H -- No --> I[No solution or explored all]
A classic example of backtracking is the N-Queens problem. The goal is to place N chess queens on an N×N chessboard so that no two queens threaten each other. We can try placing queens row by row. In each row, we iterate through all columns. If a column is safe (i.e., not attacked by any previously placed queens), we place a queen there and recursively try to place queens in the next row. If we can't place a queen in the current row, we backtrack to the previous row and try a different column for the queen there.
function solveNQueens(n) {
const board = Array(n).fill(0).map(() => Array(n).fill('.'));
const solutions = [];
function isSafe(row, col) {
// Check row and column
for (let i = 0; i < n; i++) {
if (board[row][i] === 'Q' || board[i][col] === 'Q') return false;
}
// Check diagonals
for (let i = row, j = col; i >= 0 && j >= 0; i--, j--) if (board[i][j] === 'Q') return false;
for (let i = row, j = col; i >= 0 && j < n; i--, j++) if (board[i][j] === 'Q') return false;
for (let i = row, j = col; i < n && j >= 0; i++, j--) if (board[i][j] === 'Q') return false;
for (let i = row, j = col; i < n && j < n; i++, j++) if (board[i][j] === 'Q') return false;
return true;
}
function backtrack(row) {
if (row === n) {
solutions.push(board.map(r => r.join('')));
return;
}
for (let col = 0; col < n; col++) {
if (isSafe(row, col)) {
board[row][col] = 'Q';
backtrack(row + 1);
board[row][col] = '.'; // Backtrack
}
}
}
backtrack(0);
return solutions;
}