Public
Edited
Apr 28, 2024
function isDiagonal(r1, c1, r2, c2) {
let dr = r2 - r1;
let dc = c2 - c1;
return dr == dc || dr == -dc;
}
isDiagonal(1,1,3,3)
isDiagonal(0,3,3,0)
function queens(n) {
let res = [];
function place(indexes) {
let m = indexes.length;
if (m == n) {
res.push(indexes);
return;
}
const hasDiagonal = (i) => {
for (let j = 0; j < m; j++) {
if (isDiagonal(m, i, j, indexes[j])) return true
}
return false
}
for (let i = 0; i < n; i++) {
if (indexes.includes(i)) continue;
if (hasDiagonal(i)) continue;
place([...indexes, i]);
}
}
place([]);
return res;
}
queens(2)
queens(3)
queens(4)
queens(5)
queens(6)
queens(7)
queens(8)
function queensN(n) {
function place(indexes) {
let m = indexes.length;
if (m == n) return 1
const hasDiagonal = (i) => {
for (let j = 0; j < m; j++) {
if (isDiagonal(m, i, j, indexes[j])) return true
}
return false
}
let res = 0;
for (let i = 0; i < n; i++) {
if (indexes.includes(i)) continue;
if (hasDiagonal(i)) continue;
res += place([...indexes, i]);
}
return res;
}
return place([]);
}
queensN(12)
queensN(13)
queensN(10)
queensN(11)
function queensM(n) {
const cache = {}
const mirror = (indexes) => indexes.map(i => n - 1 - i);
function place(indexes) {
let m = indexes.length;
if (m == n) return 1
const hasDiagonal = (i) => {
for (let j = 0; j < m; j++) {
if (isDiagonal(m, i, j, indexes[j])) return true
}
return false
}
const key = `${indexes}`
const mirrorKey = `${mirror(indexes)}`
if (key in cache) return cache[key]
if (mirrorKey in cache) return cache[mirrorKey]
let res = 0;
for (let i = 0; i < n; i++) {
if (indexes.includes(i)) continue;
if (hasDiagonal(i)) continue;
res += place([...indexes, i]);
}
cache[key] = res;
cache[mirrorKey] = res;
return res;
}
return place([]);
}
queensM(12)
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
