DEV Community

Cover image for LeetCode 51. N-Queens
codingpineapple
codingpineapple

Posted on

LeetCode 51. N-Queens

Description:

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.

Example 1:

Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above
Enter fullscreen mode Exit fullscreen mode

Example 2:

Input: n = 1
Output: [["Q"]]
Enter fullscreen mode Exit fullscreen mode

Solution:

Time complexity :
Space complexity :

var solveNQueens = function(n) {
    const output = [];
    backtrack(output, n);
    return output;
};

function backtrack(output, n, board = [], r = 0) {
    // If we have placed n queens on the board, create board as a string
    // and push it into our output
    if (r === n) {
        output.push(board.map(c => '.'.repeat(c) + 'Q' + '.'.repeat(n - c - 1)));
        return;
    }
    // Find the column to saftely place a queen in the current row (r)
    for (let c = 0; c < n; c++) {
        // Check if the current column is safe from a vertical, horizontal, or diagonal attack
        // from previously placed queens on the board
        if (!board.some((bc, br) => bc === c || bc === c + r - br || bc === c - r + br)) {
            // place a queen in the current column (c)
            board.push(c);
            // move to the next row
            backtrack(output, n, board, r + 1);
            // remove column from the board
            board.pop();
        }
    }
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)