3

kedebug · kedebug · commit 832edfaa74e7 · 2013-07-04T14:09:07.000+08:00
diff --git a/N-QueensII/N-QueensII.cpp b/N-QueensII/N-QueensII.cpp
@@ -0,0 +1,27 @@
+class Solution {
+public:
+    int queens;
+    int mask;
+    int totalNQueens(int n) {
+        // Start typing your C/C++ solution below
+        // DO NOT write int main() function
+        
+        mask = (1 << n) - 1;
+        queens = 0;
+        totalNQueensHelper(0, 0, 0);
+        return queens;
+    }
+    
+    void totalNQueensHelper(int col, int ld, int rd) {
+        if (col != mask) {
+            int valid_pos = mask & (~(col | ld | rd));
+            while (valid_pos) {
+                int p = valid_pos & (-valid_pos);
+                valid_pos -= p;
+                totalNQueensHelper(col + p, (ld + p) << 1, (rd + p) >> 1);
+            }
+        }
+        else
+            queens += 1;
+    }
+};
