51. N-Queens

N-Queens

Problem 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. You may return the answer in any order.

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"]]

 

Constraints:

• 1 <= n <= 9

Approach) Basic

1. We create a board matrix and fill it with 0 ( for 3 dimension board it would be like [ [0,0,0], [0,0,0], [0,0,0] ]
2. We start to paste the queens in the first column first row
3. We mark queen's move by incrementing our sales. So now our board becomes:

[
	[Q,1,1]
	[1,1,0],
	[1,0,1]
]

4. We move through rows ( we have DFS here, so we move through row first ), skipping cells, which are marked as queens moves ( these cells have a value > 0 )
5. Now we have our board look like this:

[
	[Q,2,2]
	[2,2,Q],
	[1,1,2]
]

6. notice that all cells are already filled with a positive value, so there isn't any way to place a queen on the last row. We loop through rest cells and then come back to first. But to come back, we need to remove our queen from the first row. That's why we use digits here. We remove queen moves marking on pos row = 1, col = 2. That's why we need digits. Our board now:

[
	[Q,1,1]
	[1,1,Q],
	[1,0,1]
]

7. As we prevent queen intersections, the queen spot now becomes 0. Our board:

[
	[Q,1,1]
	[1,1,0],
	[1,0,1]
]

8. Now, we perform the same removal for a queen with pos r = 0, c = 0

That we place a queen on r = 0, c = 1, and repeat this until we get all solutions

class ChessBoard extends Array {
    constructor(n) {
        super();
        this.boardDimension = n;
        const arr = [];
        for (let i = 0; i < n; i++) {
            let row = [];
            for (let j = 0; j < n; j++) {
                row.push(0);
            }
            this.push(row);
         }

        return this;
    }
    
    removeQueenFromRow(r) {
        for (let c = 0; c < this.length; c++) {
            if (this[r][c] === 'Q') {
                this.markQueenMoves([r,c], 'DECREASE');
                this[r][c] = 0;
                break;
            }
        }
    }
    
    markQueenMoves([r,c], op = 'INCREASE') {
        const marker = (r,c) => {
            switch (op) {
                case 'INCREASE':
                    this[r][c]++;
                    break;
                case 'DECREASE':
                    this[r][c]--;
                    break;
            }
        }
        
        // horizontal
        for (let cc = 0; cc < this.length; cc++) {
            if (this[r][cc] !== 'Q') {
                 marker(r, cc);
            }
        }
        
        // vertical
        for (let cr = 0; cr < this.length; cr++) {
            if (this[cr][c] !== 'Q') {
                marker(cr, c);
            }
        }
        
        
        // left diagonal
        let cr = r;
        let cc = c;
        while (this[cr] !== undefined && this[cr][cc] !== undefined) {
            if (this[cr][cc] !== 'Q') {
                marker(cr, cc);
            }
            cr++;
            cc++;
           
        }
        
        cr = r;
        cc = c;
        while (this[cr] !== undefined && this[cr][cc] !== undefined) {
            if (this[cr][cc] !== 'Q') {
                 marker(cr, cc);
            }
            cr--;
            cc--;
        }
        
        cr = r;
        cc = c;
        while (this[cr] !== undefined && this[cr][cc] !== undefined) {
            if (this[cr][cc] !== 'Q') {
                marker(cr, cc);
            }
            cr++;
            cc--;
        }
        
        cr = r;
        cc = c;
        while (this[cr] !== undefined && this[cr][cc] !== undefined) {
            if (this[cr][cc] !== 'Q') {
                marker(cr, cc);
            }
            cr--;
            cc++;
        }
        // for ()
        
    }
    
    convertBoardToResultForm() {
        const resultBoard = [];
        for (let r = 0; r < this.length; r++) {
            let row = '';
            for (let c = 0; c < this.length; c++) {
                if (this[r][c] === 'Q') {
                    row += 'Q';
                } else {
                    row += '.'
                }
            }
            
            resultBoard.push(row);
        }
        
        return resultBoard;
    }
}

const solveNQueens = n => {
    const possibleBoards = [];
    let board = new ChessBoard(n);
    
    const dfs = (r = 0) => {
        if (r === n) {
            possibleBoards.push(board.convertBoardToResultForm());
            return;
        }
        
        for (let c = 0; c < board.length; c++) {
            if (board[r][c] > 0) {
                continue;
            }
            
            board[r][c] = 'Q';
            board.markQueenMoves([r,c]);
            dfs(r + 1);
            board.removeQueenFromRow(r);
        }
        

    }
    
    dfs(0);
    return possibleBoards;
};

Approach) Intuitive

/**
 * @param {number} n
 * @return {string[][]}
 */
var solveNQueens = function(n, start = 0 , mat) {
    var mat = [...new Array(n)].map( ele => new Array(n).fill(".") );
    var len = mat.length
    var result = [];
    var count = 0
    helper(0, mat);
    return result
    
    function helper(row , mat ){
        if(row == n){
            result.push([...mat].map(ele => ele.join("")));
            return
        }
        for(let j=0; j<len; j++){
            if(checkDigonal(row , j ,mat, n) ){
                mat[row][j] = 'Q';
                helper(row + 1 , mat)
                mat[row][j] = '.';
            }   
        } 
    }
};

function checkDigonal(i , j ,mat, len){
    
    var x = i-1;
    var y = j-1;
    
        while(x>= 0 && x < len && y>=0 && y<len){
            if(mat[x][y] == 'Q')return false
            x = x-1;
            y = y-1;
        }
        x = i-1;
        y = j+1;
    
        while(x>= 0 && x < len && y>=0 && y<len){
            if(mat[x][y] == 'Q')return false
            x = x-1;
            y = y+1;
        }
        x = i-1;
        y = j
        while(x>= 0 && x < len && y>=0 && y<len){
            if(mat[x][y] == 'Q')return false
            x--
        }
    return true
}


Approach) DFS

let res;
const solveNQueens = (n) => {
    res = [];
    let cur = initialize2DArrayNew(n, n);
    dfs(cur, 0);
    return res;
};

const dfs = (cur, row) => {
    if (row == cur.length) return res.push(cur.map(x => x.join("")));
    for (let col = 0; col < cur.length; col++) {
        if (ok(cur, row, col)) {
            cur[row][col] = 'Q';
            dfs(cur, row + 1);
            cur[row][col] = '.';
        }
    }
};

const ok = (cur, row, col) => {
    for (let i = 0; i < row; i++) { // check if current column valid by comparing other rows
        if (cur[i][col] == 'Q') return 0;
    }
    for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) { // check right diagonal
        if (cur[i][j] == 'Q') return 0;
    }
    for (let i = row - 1, j = col + 1; i >= 0 && j < cur.length; i--, j++) { // check left diagonal
        if (cur[i][j] == 'Q') return 0;
    }
    return 1;
};

const initialize2DArrayNew = (m, n) => {
    let data = [];
    for (let i = 0; i < m; i++) {
        let tmp = Array(n).fill('.');
        data.push(tmp);
    }
    return data;
};

Approach) Canonic Solution with Backtracking

/**
 * @param {number} n
 * @return {string[][]}
 */
var solveNQueens = function(n) {
    const solutions = [];
    
    const cols = new Set();
    const posDiag = new Set();
    const negDiag = new Set();
    
    const board = Array.from({ length: n }, () => new Array(n).fill('.'));
  
    function backtrack (row) {
        if (row === n) {
            solutions.push(board.map(a => a.join('')));
            return;
        }
        
        for (let col = 0; col < n; col += 1) {
            if (cols.has(col) || posDiag.has(row + col) || negDiag.has(row - col)) {
                continue;
            }
            
            cols.add(col);
            posDiag.add(row + col);
            negDiag.add(row - col);
            board[row][col] = 'Q';
            
            backtrack(row + 1);
            
            cols.delete(col);
            posDiag.delete(row + col);
            negDiag.delete(row - col);
            board[row][col] = '.';
        }   
    }
    
    backtrack(0);
    
    return solutions;
};

Conclusion

That’s all folks! In this post, we solved LeetCode problem 51. N-Queens

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!