A more readable bitwise solution without too much hacks.


  • 1
    J
    class Solution {
    public:
        int totalNQueens(int n) {
            unsigned int queens, dd, du;
            queens = dd = du = UINT_MAX;
            return solve(n-1, queens, dd, du, 0);
        }
        int solve(int n, unsigned int &queens, unsigned int &dd, unsigned int &du, int col) {
            if (col > n) return 1;
            int result = 0;
            for (int row = 0; row <= n; row++) {
                int x = row + n - col;
                int y = row + col;
                if (queens&(1<<row) && dd&(1<<x) && du&(1<<y)) {
                    queens ^= (1 << row); dd ^= (1 << x); du ^= (1 << y);
                    result += solve(n, queens, dd, du, col+1);
                    queens ^= (1 << row); dd ^= (1 << x); du ^= (1 << y);
                }
            }
            return result;
       }
    };
    

    Please read another solution for details: https://oj.leetcode.com/discuss/15333/o-n-n-time-c-dfs-solution


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.