52. N-Queens II

N-Queens II

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 the number of distinct solutions to the n-queens puzzle.

 

Example 1:

Input: n = 4
Output: 2

Explanation: There are two distinct solutions to the 4-queens puzzle as shown.

Example 2:

Input: n = 1
Output: 1

 

Constraints:

• 1 <= n <= 9

Approach) BackTracking

/**
 * @param {number} n
 * @return {number}
 */
var totalNQueens = function(n) {
    const cols = new Set(),
          hills = new Set(),
          dales = new Set();
    /**
     * @param {number} row
     * @param {number} col
     * @return {boolean}
     */
    const isSafe = (row, col) => !(cols.has(col) || hills.has(row - col) || dales.has(row + col));
    
    /**
     * @param {number} row
     * @param {number} col
     * @return {void}
     */
    const placeQueen = (row, col) => {
        cols.add(col), hills.add(row - col), dales.add(row + col);
    }
    
    /**
     * @param {number} row
     * @param {number} col
     * @return {void}
     */
    const removeQueen = (row, col) => {
        cols.delete(col), hills.delete(row - col), dales.delete(row + col);
    }
    
    /**
     * @param {number} row
     * @param {number} count
     * @return {number}
     */
    const backtrackQueen = (row, count) => {
        if (row === n) {
            return ++count;
        }
        for (let col = 0; col < n; col++) {
            if (isSafe(row, col)) {
                placeQueen(row, col);
                count = backtrackQueen(row + 1, count);
                removeQueen(row, col);
            }
        }
        return count;
    }
    return backtrackQueen(0, 0);
};

Approach) Concise 

var totalNQueens = function(n) {
    function h(i, col, diag, anti) {
        if (i === n) return 1;
        let ans = 0;
        for (let j = 0; j < n; j++) {
            if (col[j]) continue;
            if (diag[i+j]) continue;
            if (anti[n-1+i-j]) continue;
            col[j] = true;
            diag[i+j] = true;
            anti[n-1+i-j] = true;
            ans += h(i+1, col, diag, anti);
            col[j] = false;
            diag[i+j] = false;
            anti[n-1+i-j] = false;
        }
        return ans;
    }
    return h(0, [], [], [], []);
};

Approach) Bitwise

ltu means left to top
ltr means left to right
ltd means left to down

each bit represents a row is clear or not

For example, 8 queen:

ltu was computed as (x + y)
01234567
12345678
23456789
3456789a
456789ab
56789abc
6789abcd
789abcde

ltr was computed as y
00000000
11111111
22222222
33333333
44444444
55555555
66666666
77777777

ltd was computed as (x - i + width)

89abcdef
789abcde
6789abcd
56789abc
456789ab
3456789a
23456789
12345678

And you can't have two item share same the bit position for obvious reasons.
A bitwise & will do the job test the all bits at same time for you.
And
A bitwise | will mark the bit as dirty.

In this way, you skip the whole table search completely with two bitop

/**
 * @param {number} n
 * @return {number}
 */
var totalNQueens = function(n) {
    var width = n
    var total = 0

    function run(x, ltu, ltr, ltd) {
        if (x >= width) {
            total++
            return
        }

        for (let i = 0; i < width; i++) {
            const ltuMask = 1 << (x + i)
            const ltrMask = 1 << i
            const ltdMask = 1 << (x - i + width)

            if (
                (ltu & ltuMask) ||
                (ltr & ltrMask) ||
                (ltd & ltdMask)
            ) {
                continue
            }

            run(
                x + 1,
                ltu | ltuMask,
                ltr | ltrMask,
                ltd | ltdMask
            )
        }
    }

    run(0, 0, 0, 0)
    return total
};

Approach) Canonic Solution with backtracking

/**
 * @param {number} n
 * @return {number}
 */
var totalNQueens = function(n) {
    const cols = new Set();
    const posDiag = new Set();
    const negDiag = new Set();
    let solutionCount = 0;
    
    function computePositionForRow(row) {
        if (row === n) {
            solutionCount += 1;
            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);
            
            computePositionForRow(row + 1);
            
            cols.delete(col);
            posDiag.delete(row + col);
            negDiag.delete(row - col);
        }
    }
    
    computePositionForRow(0);
    
    return solutionCount;
};

Conclusion

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

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!