function isDiagonal(r, c, r2, c2) {
let dr = r2 - r;
let dc = c2 - c;
return dr == dc || dr == -dc;
}
isDiagonal(1,1,3,3)
isDiagonal(3,0,0,3)
isDiagonal(0,0,1,2)
function queens(n) {
let ways = [];
function place(positions) {
let m = positions.length;
if (m == n) {
ways.push(positions);
return;
}
const hasDiagonal = (i) => {
for (let j = 0; j < m; j++) {
if (isDiagonal(m, i, j, positions[j])) return true
}
return false
}
for (let i = 0; i < n; i++) {
if (positions.includes(i)) continue;
if (hasDiagonal(i)) continue;
place([...positions, i]);
}
}
place([]);
return ways;
}
queens(2)
queens(3)
queens(4)
queens(5)
queens(6)
queens(7)
queens(8)
function plot(positions) {
const n = positions.length;
const empty = new Array(n).fill("·");
let res = [];
for (let i = 0; i < n; i++) {
let line = empty.slice();
line[positions[i]] = "Q";
res.push(line.join(""));
}
return res.join("\n");
}
plot([1,3,0,2])
plot([2,0,3,1])
plot([0,4,7,5,2,6,1,3])
function queensT(n) {
let ways = [];
let c = 0;
function place(positions) {
c++;
let m = positions.length;
if (m == n) {
ways.push(positions);
return;
}
const hasDiagonal = (i) => {
for (let j = 0; j < m; j++) {
if (isDiagonal(m, i, j, positions[j])) return true
}
return false
}
for (let i = 0; i < n; i++) {
if (positions.includes(i)) continue;
if (hasDiagonal(i)) continue;
place([...positions, i]);
}
}
place([]);
return c;
}
queensT(3)
queensT(4)
queensT(5)
queensT(6)
queensT(7)
queensT(8)
queensT(9)
queensT(10)
queensT(11)
queensT(12)
function queensM(n) {
const ways = [];
const col = {}
const left = {}
const right = {}
function place(positions) {
let m = positions.length;
if (m == n) {
ways.push(positions);
return;
}
for (let i = 0; i < n; i++) {
if (col[i]) continue;
if (left[m + i]) continue;
if (right[m - i]) continue;
col[i] = true
left[m+i] = true
right[m-i] = true
place([...positions, i]);
col[i] = false
left[m+i] = false
right[m-i] = false
}
}
place([]);
return ways;
}
queensM(8)
queensM(12)
function queensL(n) {
const ways = [];
const stack = [[[], {}, {}, {}]]
let current
while (current = stack.pop()) {
const [positions, col, left, right] = current
let m = positions.length;
if (m == n) {
ways.push(positions);
continue;
}
for (let i = 0; i < n; i++) {
if (col[i]) continue;
if (left[m+i]) continue;
if (right[m-i]) continue;
stack.push([
[...positions, i],
{...col, [i]: true },
{...left, [m+i]: true },
{...right, [m-i]: true }
])
}
}
return ways;
}
queensL(5)
queensL(6)
queensL(7)
queensL(8)
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.
