Backtracking Algorithm

Backtracking is a general algorithmic technique for solving problems that involve searching for a solution among a large set of possibilities. It works by incrementally building a solution and undoing previous choices when they lead to a dead-end until a valid solution is found. In C language, backtracking can be implemented using recursion.

Here’s an example of a backtracking algorithm in C language:

#include <stdio.h>
#define N 4

int board[N][N]; // N x N chess board

// Function to print the solution
void printSolution() {
    int i, j;
    for (i = 0; i < N; i++) {
        for (j = 0; j < N; j++)
            printf(" %d ", board[i][j]);
        printf("\n");
    }
}

// Function to check if it is safe to place the queen at board[row][col]
int isSafe(int row, int col) {
    int i, j;

    // Check this row on the left side
    for (i = 0; i < col; i++)
        if (board[row][i])
            return 0;

    // Check upper diagonal on the left side
    for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
        if (board[i][j])
            return 0;

    // Check lower diagonal on the left side
    for (i = row, j = col; j >= 0 && i < N; i++, j--)
        if (board[i][j])
            return 0;

    return 1;
}

// Recursive function to solve the N-Queen problem
int solveNQUtil(int col) {
    if (col == N) {
        printSolution();
        return 1;
    }

    int row, res = 0;
    for (row = 0; row < N; row++) {
        if (isSafe(row, col)) {
            board[row][col] = 1;
            res = solveNQUtil(col + 1) || res;
            board[row][col] = 0;
        }
    }

    return res;
}

// Function to solve the N-Queen problem
void solveNQ() {
    if (solveNQUtil(0) == 0)
        printf("Solution does not exist");
}

int main() {
    solveNQ();
    return 0;
}

This program solves the N-Queen problem using backtracking. The goal is to place N queens on an NxN chess board so that no two queens threaten each other. In other words, no two queens should share the same row, column, or diagonal.

The program uses a recursive function solveNQUtil() to place queens on the board one by one. The function tries all possible positions for a queen in the current column, and then recursively calls itself to solve the subproblem of placing the remaining queens. If a solution is found, the function returns 1 and prints the solution. If no solution is found, the function backtracks and tries a different position for the queen in the current column.

The program also includes a isSafe() function to check if it is safe to place a queen at a given position on the board. This function checks the current row, column, and diagonals for any other queens.

Backtracking is a powerful algorithmic technique that can solve many problems, but it can be slow for large problems due to the exponential search space. However, it is a useful technique to have in your toolkit as it can be used to solve many other problems, such as finding all possible paths in a maze or generating all permutations.