Add N queens problem bitwise solution (trekhleb#15)

juffalow · trekhleb · commit 18ba3a4db35b · 2018-08-20T15:57:01.000+03:00
* Add N queens problem bitwise solution

* Update code to corespond with eslint
diff --git a/src/algorithms/uncategorized/n-queens-bitwise/README.md b/src/algorithms/uncategorized/n-queens-bitwise/README.md
@@ -0,0 +1,9 @@
+# N-Queens Problem with Bitwise Solution
+
+Write a function that will find all possible solutions to the N queens problem for a given N.
+
+## References
+
+- [Wikipedia](https://en.wikipedia.org/wiki/Eight_queens_puzzle)
+- [GREG TROWBRIDGE](http://gregtrowbridge.com/a-bitwise-solution-to-the-n-queens-problem-in-javascript/)
+- [Backtracking Algorithms in MCPL using Bit Patterns and Recursion](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.51.7113&rep=rep1&type=pdf)
diff --git a/src/algorithms/uncategorized/n-queens-bitwise/__test__/nQeensBitwise.test.js b/src/algorithms/uncategorized/n-queens-bitwise/__test__/nQeensBitwise.test.js
@@ -0,0 +1,26 @@
+import nQueensBitwise from '../nQueensBitwise';
+
+describe('nQueensBitwise', () => {
+  it('should have solutions for 4 to N queens', () => {
+    const solutionFor4 = nQueensBitwise(4);
+    expect(solutionFor4).toBe(2);
+
+    const solutionFor5 = nQueensBitwise(5);
+    expect(solutionFor5).toBe(10);
+
+    const solutionFor6 = nQueensBitwise(6);
+    expect(solutionFor6).toBe(4);
+
+    const solutionFor7 = nQueensBitwise(7);
+    expect(solutionFor7).toBe(40);
+
+    const solutionFor8 = nQueensBitwise(8);
+    expect(solutionFor8).toBe(92);
+
+    const solutionFor9 = nQueensBitwise(9);
+    expect(solutionFor9).toBe(352);
+
+    const solutionFor10 = nQueensBitwise(10);
+    expect(solutionFor10).toBe(724);
+  });
+});
diff --git a/src/algorithms/uncategorized/n-queens-bitwise/nQueensBitwise.js b/src/algorithms/uncategorized/n-queens-bitwise/nQueensBitwise.js
@@ -0,0 +1,33 @@
+export default function (n) {
+  // Keeps track of the # of valid solutions
+  let count = 0;
+
+  // Helps identify valid solutions
+  const done = (2 ** n) - 1;
+
+  // Checks all possible board configurations
+  const innerRecurse = (ld, col, rd) => {
+    // All columns are occupied,
+    // so the solution must be complete
+    if (col === done) {
+      count += 1;
+      return;
+    }
+
+    // Gets a bit sequence with "1"s
+    // whereever there is an open "slot"
+    let poss = ~(ld | rd | col);
+
+    // Loops as long as there is a valid
+    // place to put another queen.
+    while (poss & done) {
+      const bit = poss & -poss;
+      poss -= bit;
+      innerRecurse((ld | bit) >> 1, col | bit, (rd | bit) << 1);
+    }
+  };
+
+  innerRecurse(0, 0, 0);
+
+  return count;
+}
