Skip to content

Instantly share code, notes, and snippets.

@mmis1000
Created November 6, 2019 09:52
Show Gist options
  • Save mmis1000/5ac15519ddbea5e3aafb9631b0c945be to your computer and use it in GitHub Desktop.
Save mmis1000/5ac15519ddbea5e3aafb9631b0c945be to your computer and use it in GitHub Desktop.
Bitwise magic 8 queen problem resolver
/**
* @param {number} n
* @return {number}
*/
var totalNQueens = function(n) {
var width = n
var total = 0
function run(x, ltu, ltr, ltd) {
if (x >= width) {
total++
return
}
for (let i = 0; i < width; i++) {
const ltuMask = 1 << (x + i)
const ltrMask = 1 << i
const ltdMask = 1 << (x - i + width)
if (
(ltu & ltuMask) ||
(ltr & ltrMask) ||
(ltd & ltdMask)
) {
continue
}
run(
x + 1,
ltu | ltuMask,
ltr | ltrMask,
ltd | ltdMask
)
}
}
run(0, 0, 0, 0)
return total
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment