Write a function that will find all possible solutions to the N queens problem for a given N.

- [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)

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);

});

export default function(n) {

//Keeps track of the # of valid solutions

var count = 0;

//Helps identify valid solutions

var done = Math.pow(2,n) - 1;

//Checks all possible board configurations

var innerRecurse = function(ld, col, rd) {

//All columns are occupied,

//so the solution must be complete

if (col === done) {

count++;

return;

}

//Gets a bit sequence with "1"s

//whereever there is an open "slot"

var poss = ~(ld | rd | col);

//Loops as long as there is a valid

//place to put another queen.

while ( poss & done ) {

var bit = poss & -poss;

poss -= bit;

innerRecurse((ld|bit)>>1, col|bit, (rd|bit)<<1);

}

};

innerRecurse(0,0,0);

return count;