I'm a professor of mathematics at the University of North Carolina Asheville. I've also done a fair amount of consulting work over the years focusing on scientific and data visualization.
I'm happy to be part of the first Observable Ambassador's cohort.
Public
Edited
Nov 14, 2022
16 stars
board_cnt = math.multiply(
math.ones(55),
math.pow(math.matrix(kings_matrix(8)), 7),
math.ones(55)
)
1.34 ** (8 * 9) / board_cnt
// Construct the adjacency matrix for the set of legal rows
// of length m with non-attacking kings.
function kings_matrix(m) {
let A = [
[1, 1, 1],
[1, 0, 0],
[1, 0, 0]
];
let B = [
[1, 1],
[1, 0]
];
if (m == 1) {
return B;
} else if (m == 2) {
return A;
} else {
for (let i = 0; i < m - 2; i++) {
let C = assemble(A, B);
B = Object.assign([], A);
A = Object.assign([], C);
}
return A;
}
function assemble(A, B) {
let a = Object.assign([], A);
let b1 = Object.assign([], B);
let b2 = Object.assign([], B);
let an = A.length;
let bn = B.length;
let z1 = d3.range(an - bn).map(() => d3.range(bn).map(() => 0));
b1 = b1.concat(z1);
let z2 = d3.range(bn).map(() => d3.range(an - bn).map(() => 0));
b2 = d3.zip(b2, z2).map((aa) => aa.flat());
let z = d3.range(bn).map(() => d3.range(bn).map(() => 0));
let top = d3.zip(a, b1).map((aa) => aa.flat());
let bot = d3.zip(b2, z).map((aa) => aa.flat());
return top.concat(bot);
}
}
// The kings matrix for a standard chessboard with rows of length 8
A8 = kings_matrix(8)
// Recursive construction of the set of all legal rows of length 8
rows = {
let extend1 = (s) => s + "1";
let extend2 = (s) => s + "1K";
let rows = [
["K", "1"],
["1K", "K1", "11"]
];
for (let i = 0; i < 6; i++) {
rows.push([rows[0].map(extend2), rows[1].map(extend1)].flat());
rows.shift();
}
return rows[1].reverse();
}
// A Map object that allows us to quickly grab how many kings are in
// row i of our list of rows.
king_count = new Map(
rows.map((s, i) => [i, s.match(/K/g) ? s.match(/K/g).length : 0])
)
// Function to compute the kings rows that may be placed
// adjacency to the ith kings row.
function adjacencies(i) {
let row = A8[i];
return row.map((v, i) => (v == 1 ? i : [])).flat();
}
function fibonacci(n) {
let a = 0;
let b = 1;
let c;
for (let i = 0; i < n; i++) {
c = a;
a = a + b;
b = c;
}
return a;
}
// The list of dominant eigenvalues of the kings matrices A_m
// for a few values of m
eigenvalues = d3.range(1, 12).map(eigs)
// Function to compute the dominant eigenvalues of the kings matrices
// using power iteration
function eigs(n) {
let A = kings_matrix(n);
let eigenvector = d3.range(A.length).map(() => 1);
for (let i = 0; i < 30; i++) {
eigenvector = math.multiply(A, eigenvector);
eigenvector = eigenvector.map((x) => x / eigenvector[0]);
}
eigenvector = math.multiply(A, eigenvector);
let eigenvalue = eigenvector[0];
return eigenvalue;
}
// Count vertices by valence
d3
.sort(
Array.from(
d3
.group(
A8.map((r) => d3.sum(r)),
(x) => x
)
.values()
).map((a, i) => ({
cnt: a.length,
valence: a[0]
})),
(a) => a.valence
)
.reverse()
// Number of adjacencies in the Kings graph
1 +
(A8.flat(2)
.map((i) => (i == 0 ? [] : 1))
.flat().length -
1) /
2
// Raster plot of the kings matrix A_m
function kings_matrix_plot(m, size = 400) {
let pts = kings_matrix(m)
.map((r, i) => r.map((v, j) => (v == 1 ? [j, i] : [])))
.flat()
.filter((a) => a.length > 0);
return Plot.plot({
x: { domain: [0, fibonacci(m + 2)], ticks: 0 },
y: { domain: [fibonacci(m + 2), 0] },
width: size,
height: size,
marks: [
Plot.rect(pts, {
x1: (d) => d[0],
y1: (d) => d[1],
x2: (d) => d[0] + 1,
y2: (d) => d[1] + 1
})
]
});
}
// Generate an image of the nth legal kings row of length 8
function row_pic(n) {
let row_pic = Plot.plot({
width: 800,
height: 100,
margin: 0,
x: { domain: [0, 8] },
y: { domain: [0, 1] },
marks: [
Plot.rect(d3.range(1, 10, 2), {
x1: (d) => d,
x2: (d) => d + 1,
y1: 0,
y2: 1,
fill: "#ddd",
stroke: "#ddd"
}),
Plot.line(
[
[0, 0],
[8, 0],
[8, 1],
[0, 1],
[0, 0]
],
{ stroke: "#ccc" }
)
]
});
let matches = rows[n].matchAll(/K/g);
let match_result = matches.next();
while (!match_result.done) {
d3.select(row_pic)
.append("g")
.attr(
"transform",
`translate(${row_pic
.scale("x")
.apply(match_result.value.index)}) scale(2.2)`
)
.append(() => svg`${king}`);
match_result = matches.next();
}
return row_pic;
}
// Use the main algorithm described here to generate a random, legal,
// 8x8 chessboard and return it in Forsyth–Edwards notation.
function random_kings_board_fen() {
let v = d3.randomInt(0, 55)();
let path = [v];
for (let i = 0; i < 7; i++) {
let choices = A8[v].map((x, i) => (x == 1 ? i : [])).flat();
v = choices[d3.randomInt(0, choices.length)()];
path.push(v);
}
return path.map((i) => rows[i]).join("/");
}
// Generate the image of a kings board, given its Forsyth–Edwards notation
function kings_board(fen, size) {
return chessboard(fen, {
size: size,
theme: {
labelColor: "white",
lightSquareFill: "#FFF",
darkSquareFill: "#DDD",
borderStroke: "#DDD"
}
});
}
// The custom thumbnail
{
let div = d3
.create("div")
.style("width", "640px")
.style("height", "400px")
.style("padding-top", "50px");
// .style("border", "solid 1px black");
let kb = await kings_board(random_kings_board_fen(), 320);
div
.append("div")
.style("display", "inline-block")
.append(() => kb);
div
.append("div")
.style("display", "inline-block")
.append(() => kings_matrix_plot(12, 320));
return div.node();
}
// Image from WikiMedia
// https://commons.wikimedia.org/wiki/Category:SVG_chess_pieces
king = (await (await FileAttachment("King.svg")).text()).slice(55)
// The images of the 8x8 chessboards are generated using Haris Lapiroff's chessboard function
import { chessboard } from "@harrislapiroff/chessboard"
math = require("mathjs")
tippy = require("tippy.js")
tippy_style = html`<link rel="stylesheet" href="${await require.resolve(
`tippy.js/themes/light-border.css`
)}">`
d3 = require("d3@7", "d3-graphviz@2")
One platform to build and deploy the best data apps
Experiment and prototype by building visualizations in live JavaScript notebooks. Collaborate with your team and decide which concepts to build out.
Use Observable Framework to build data apps locally. Use data loaders to build in any language or library, including Python, SQL, and R.
Seamlessly deploy to Observable. Test before you ship, use automatic deploy-on-commit, and ensure your projects are always up-to-date.