Backtracking
Backtracking is a general algorithm for finding solutions to computational problems, notably constraint satisfaction problems, by incrementally building candidates and abandoning a candidate as soon as it is determined that it cannot lead to a valid solution.
Common Backtracking Problems
- N-Queens Problem: Placing N queens on a chessboard such that no two queens threaten each other.
- Sudoku Solver: Solving a partially filled Sudoku grid.
- Subset Sum Problem: Finding subsets of a set that sum to a given number.
- Permutations of a String: Generating all permutations of a string.
1: N-Queens Problem
#include <stdio.h>
#define N 4
bool isSafe(int board[N][N], int row, int col) {
for (int i = 0; i < col; i++) {
if (board[row][i]) {
return false;
}
}
for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
if (board[i][j]) {
return false;
}
}
for (int i = row, j = col; j >= 0 && i < N; i++, j--) {
if (board[i][j]) {
return false;
}
}
return true;
}
bool solveNQUtil(int board[N][N], int col) {
if (col >= N) {
return true;
}
for (int i = 0; i < N; i++) {
if (isSafe(board, i, col)) {
board[i][col] = 1;
if (solveNQUtil(board, col + 1)) {
return true;
}
board[i][col] = 0; // Backtrack
}
}
return false;
}
void solveNQ() {
int board[N][N] = {0};
if (!solveNQUtil(board, 0)) {
printf("Solution does not exist");
return;
}
printf("Solution exists:n");
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
printf(" %d ", board[i][j]);
}
printf("\n");
}
}
int main() {
solveNQ();
return 0;
}Output
Explanation
The N-Queens Problem is a classic backtracking problem where you need to place N queens on an N×N chessboard such that no two queens can attack each other. This code uses backtracking to explore all possible placements of queens and backtracks when it finds an invalid position. It prints one solution for placing the queens on the board.
2 : Sudoku Solver
#include <stdio.h>
#include <stdbool.h>
#define N 9
bool isSafe(int board[N][N], int row, int col, int num) {
for (int x = 0; x < 9; x++) {
if (board[row][x] == num || board[x][col] == num || board[row - row % 3 + x / 3][col - col % 3 + x % 3] == num) {
return false;
}
}
return true;
}
bool solveSudoku(int board[N][N]) {
for (int row = 0; row < N; row++) {
for (int col = 0; col < N; col++) {
if (board[row][col] == 0) {
for (int num = 1; num <= 9; num++) {
if (isSafe(board, row, col, num)) {
board[row][col] = num;
if (solveSudoku(board)) {
return true;
}
board[row][col] = 0; // Backtrack
}
}
return false;
}
}
}
return true;
}
void printGrid(int board[N][N]) {
for (int r = 0; r < N; r++) {
for (int d = 0; d < N; d++) {
printf("%d ", board[r][d]);
}
printf("\n");
}
}
int main() {
int board[N][N] = { {5, 3, 0, 0, 7, 0, 0, 0, 0},
{6, 0, 0, 1, 9, 5, 0, 0, 0},
{0, 9, 8, 0, 0, 0, 0, 6, 0},
{8, 0, 0, 0, 6, 0, 0, 0, 3},
{4, 0, 0, 8, 0, 3, 0, 0, 1},
{7, 0, 0, 0, 2, 0, 0, 0, 6},
{0, 6, 0, 0, 0, 0, 2, 8, 0},
{0, 0, 0, 4, 1, 9, 0, 0, 5},
{0, 0, 0, 0, 8, 0, 0, 7, 9} };
if (solveSudoku(board)) {
printGrid(board);
} else {
printf("No solution exists");
}
return 0;
}Output
Explanation
The Sudoku Solver uses backtracking to fill in the empty cells of a 9x9 Sudoku grid. The code checks if a number can be safely placed in a cell. If not, it backtracks by removing the number and trying a different one. The program outputs the fully solved Sudoku board if a solution exists.