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
Example 2:
Input: n = 1
Output: [["Q"]]
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();
}
}
}
Top comments (0)