Coding Exercise – N Queen Problem – C++ – Bit Logics – Shortest and Fastest Solution – Online Judge

Well, I have a detailed post [here] that presents two solutions to solve the classic n-queen problem. The problem asks you to find the number of solutions to put n queens in a board (size n X n) so that none of the queens attack each other (vertically, horizontally and diagonally) . One of the solutions is like this:

The first solution can usually be found at text-books. The backtracing algorithm (recursively or iteratively) finds the next valid positions (depth ++) if not, try next valid position until it can’t find one, in which case, rewind (depth –) and move forward by trying the next position in the current level.

The fastest implementation (through the same algorithm), would be via big logics. Just a few lines of code and it finds the solution within a shorter amount of time.

The problem, apparently becomes one of the most frequently-asked programming tasks for software companies: http://oj.leetcode.com/problems/n-queens-ii/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    int ans, lim;
 
    void solve(int row, int ld, int rd) {
        if (row == lim) { // have placed row queens
            ans ++;  // we have a solution
            return;
        }
        int pos = lim & (~(row | ld | rd)); // valid positions
        while (pos != 0) {
            int p = pos & (-pos); // rightmost position
            pos -= p; // have tried this
            solve(row + p, (ld + p) << 1, (rd + p) >> 1);
        }
    }
 
    int totalNQueens(int n) {
        ans = 0;
        lim = (1 << n) - 1;
        solve(0, 0, 0);
        return ans;
    }
};

class Solution {
public:
    int ans, lim;

    void solve(int row, int ld, int rd) {
        if (row == lim) { // have placed row queens
            ans ++;  // we have a solution
            return;
        }
        int pos = lim & (~(row | ld | rd)); // valid positions
        while (pos != 0) {
            int p = pos & (-pos); // rightmost position
            pos -= p; // have tried this
            solve(row + p, (ld + p) << 1, (rd + p) >> 1);
        }
    }

    int totalNQueens(int n) {
        ans = 0;
        lim = (1 << n) - 1;
        solve(0, 0, 0);
        return ans;
    }
};

The above represents the current valid positions just using integers. Thus, one of the limitation is n cannot be larger than 32. If larger inputs are required, we may use unsigned long long which is 64-bit integer.

A 32-bit int has 32-bit boolean values. It is like defining bool row[32] but only handled faster. The implementation is also recursive, which searches valid positions row by row, and until it finds one (if (row == lim)).

Want more explanations on this? See this post, in Python.

Also, you might find the classic backtracking implementations for N queen problem here: Using Recursive Backtracking Algorithm to Solve Classic N Queen Problem

–EOF (The Ultimate Computing & Technology Blog) —