Backtracking

Backtracking is a technique used to solve problems recursively by trying out all possible solutions.

If a solution is found, it proceeds, otherwise, it backs up and tries a different approach.

This method is often used in constraint satisfaction problems, such as puzzles like Sudoku, as well as in other optimization and search problems.

pseudocode:

procedure Backtrack(state):
    if state is a solution:
        return state
    else:
        for each possible choice for the next step:
            if the choice is valid:
                make the choice
                result = Backtrack(new_state)
                if result is not None:
                    return result
                undo the choice
        return None

initial_state = initial_state_of_the_problem
solution = Backtrack(initial_state)
if solution is not None:
    // Process solution
else:
    // No solution found

Example of backtracking algorithm to solve the N-Queens problem using JavaScript:

function isSafe(board, row, col, N) {
    // Check if there is a queen in the same row to the left
    for (let i = 0; i < col; i++) {
        if (board[row][i]) {
            return false;
        }
    }

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

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

    return true;
}

function solveNQueensUtil(board, col, N, result) {
    // Base case: If all queens are placed, return true
    if (col >= N) {
        result.push([...board.map(row => row.join(''))]);
        return;
    }

    // Consider this column and try placing this queen in all rows one by one
    for (let i = 0; i < N; i++) {
        if (isSafe(board, i, col, N)) {
            board[i][col] = 1;

            // Recur to place rest of the queens
            solveNQueensUtil(board, col + 1, N, result);

            // If placing queen in board[i][col] doesn't lead to a solution then remove queen from board[i][col]
            board[i][col] = 0; // Backtrack
        }
    }
}

function solveNQueens(N) {
    const board = Array.from({ length: N }, () => Array(N).fill(0));
    const result = [];

    solveNQueensUtil(board, 0, N, result);

    return result;
}

// Example usage:
const N = 4;
const solutions = solveNQueens(N);
console.log("Solutions for N =", N);
solutions.forEach(solution => console.log(solution));

This code solves the N-Queens problem recursively using backtracking.

It finds all possible placements of N queens on an NxN chessboard such that no two queens attack each other.