N-Queens Problem with Backtracking Algorithm

The N-Queens Problem is a combinatorial problem with applications in chessboard layout design, scheduling, and constraint satisfaction. The goal is to place N queens on an N×N chessboard so that no two queens attack each other.

The backtracking algorithm is a common approach to solve the N-Queens Problem. It systematically explores all possible placements of queens on the chessboard, backtracking when a placement leads to a conflict.

function isSafe(board, row, col) {
    // Check if there's a queen in the same column
    for (let i = 0; i < row; i++) {
        if (board[i][col] === 1) {
            return false;
        }
    }

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

    // Check upper right diagonal
    for (let i = row, j = col; i >= 0 && j < board.length; i--, j++) {
        if (board[i][j] === 1) {
            return false;
        }
    }

    return true;
}

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

    function backtrack(row) {
        if (row === n) {
            results.push(board.map(row => row.join('')));
            return;
        }

        for (let col = 0; col < n; col++) {
            if (isSafe(board, row, col)) {
                board[row][col] = 1;
                backtrack(row + 1);
                board[row][col] = 0; // Backtrack
            }
        }
    }

    backtrack(0);
    return results;
}

// Example usage:
const n = 4;
console.log("Solutions for N-Queens Problem (N = 4):", solveNQueens(n));

The N-Queens Problem has practical applications in designing efficient board layouts, scheduling tasks, and optimizing resource allocation in various domains.

GAZAR

N-Queens Problem with Backtracking Algorithm

Comments