Backtracking

Backtracking:

Backtracking is a problem-solving technique where the solution is built incrementally, but if at some point it’s determined that the current partial solution cannot be completed to a valid solution, the algorithm discards it and backtracks to the previous step.

For example, consider the N-Queens problem where you aim to place N chess queens on an N×N chessboard in a way that no two queens threaten each other. A backtracking algorithm would explore possible placements, backtrack if conflicts arise, and continue until a valid solution is found or all possibilities are exhausted.

Here’s a simple Python code snippet for solving the N-Queens problem using backtracking.

#include<iostream>
#include<vector>
using namespace std;
bool isSafe(const vector<vector>& board, int row, int col, int n) {
for (int i = 0; i < row; ++i) { if (board[i][col] == 1) { return false; } if (col - i >= 0 && board[row - i][col - i] == 1) {
return false;
}
if (col + i < n && board[row - i][col + i] == 1) {
return false;
}
}
return true;
}
void printBoard(const vector<vector>& board) {
for (const auto& row : board) {
for (int cell : row) {
cout << cell << " ";
}
cout << endl;
}
cout << endl;
}

void solveNQueensUtil(vector<vector>& board, int row, int n) {
if (row == n) {
// Reached the end, print the solution
printBoard(board);
return;
}

for (int col = 0; col < n; ++col) {
if (isSafe(board, row, col, n)) {
// Place queen and move to the next row
board[row][col] = 1;
solveNQueensUtil(board, row + 1, n);
// Backtrack
board[row][col] = 0;
}
}
}
void solveNQueens(int n) {
// Initialize the chessboard
vector<vector> board(n, vector(n, 0));
solveNQueensUtil(board, 0, n);
}
int main() {
// Example usage:
solveNQueens(4);

return 0;
}