2b:null 2c:["$","title",null,{"children":"The Kings Problem | Mark McClure | Observable"}] 31:T502,{ let plot = Plot.plot({ x: { domain: [0, 8] }, y: { domain: [-0.5, 3] }, width: 800, height: 350, margin: 1, marks: [ Plot.rect([0], { x1: 1, x2: 2, y1: 0, y2: 1, fill: "#ddd", stroke: "#bbb" }), Plot.line( [ [0, 0], [3, 0], [3, 1], [0, 1], [0, 0] ], { stroke: "#bbb", strokeWidth: 0.5 } ), Plot.rect([0], { x1: 1, x2: 2, y1: 1.5, y2: 2.5, fill: "#ddd", stroke: "#bbb" }), Plot.line( [ [0, 1.5], [3, 1.5], [3, 2.5], [0, 2.5], [0, 1.5] ], { stroke: "#bbb", strokeWidth: 0.5 } ), Plot.line( [ [1, 3], [1, -0.5] ], { stroke: "black", strokeDasharray: [3, 5] } ) ] }); d3.select(plot) .selectAll("g.new") .data([ [0, 1], [2, 1], [2, 2.5] ]) .join("g") .attr( "transform", (d) => `translate(${plot.scale("x").apply(d[0])}, ${plot .scale("y") .apply(d[1])}) scale(2.2)` ) .append(() => svg`${king}`); return plot; }32:T672,{ let plot = Plot.plot({ x: { domain: [0, 8] }, y: { domain: [-0.5, 4.5] }, width: 800, height: 500, margin: 1, marks: [ // Bottom row Plot.rect([0], { x1: 1, x2: 2, y1: 0, y2: 1, fill: "#ddd", stroke: "#bbb" }), Plot.line( [ [0, 0], [3, 0], [3, 1], [0, 1], [0, 0] ], { stroke: "#bbb", strokeWidth: 0.5 } ), // Middle row Plot.rect([0], { x1: 1, x2: 2, y1: 1.5, y2: 2.5, fill: "#ddd", stroke: "#bbb" }), Plot.line( [ [0, 1.5], [3, 1.5], [3, 2.5], [0, 2.5], [0, 1.5] ], { stroke: "#bbb", strokeWidth: 0.5 } ), // Top row Plot.rect([0], { x1: 1, x2: 2, y1: 3, y2: 4, fill: "#ddd", stroke: "#bbb" }), Plot.line( [ [0, 3], [3, 3], [3, 4], [0, 4], [0, 3] ], { stroke: "#bbb", strokeWidth: 0.5 } ), Plot.line( [ [2, 4.5], [2, -0.5] ], { stroke: "black", strokeDasharray: [3, 5] } ) ] }); d3.select(plot) .selectAll("g.new") .data([ [0, 2.5], [1, 1] ]) .join("g") .attr( "transform", (d) => `translate(${plot.scale("x").apply(d[0])}, ${plot .scale("y") .apply(d[1])}) scale(2.2)` ) .append(() => svg`${king}`); return plot; }33:T633,Thus, there are five rows of length three. Furthermore, the construction suggests a recursive approach to generating all the rows of length ${tex`n`}. The rows of length ${tex`n`} could be constructed from the rows of length ${tex`n-2`} and the rows of length ${tex`n-1`}: - We construct a row of length ${tex`n`} from a row of length ${tex`n-2`} by appending an empty square and then a king. - We construct a row of length ${tex`n`} from a row of length ${tex`n-1`} by appending an empty square. This yields all the rows of length ${tex`n`} and is exactly how the boards of length 8 were constructed above. Furthermore, if we let ${tex`K_n`} denote the number of ways to place kings on a row of length ${tex`n`}, this construction shows that ${tex.block`K_n = K_{n-1} + K_{n-2}.`} This makes it easy to count the number of ways to place kings on a row of length ${tex`n`}.

Length of the row	1	2	3	4	5	6	7	8
Number of ways	2	3	5	8	13	21	34	55

Note that each term in the second row is the sum of the previous two terms. This is the same recursive formula for the famous Fibonacci sequence: ${tex.block`F_1 = 1, \: F_2 = 1, \: F_n = F_{n-1} + F_{n-2},`} which yields ${tex.block`(1,1,2,3,5,8,\ldots).`} Note that our sequence ${tex`K_n`} is shifted two steps from the Fibonacci sequence. Thus, another way to write write the solution to our simpler problems is as ${tex`F_{10} = 55`}.34:Tbe6,### Adjacency matrices The ideas above, can be generalized to the level of an ${tex`n\times m`} board, that can be generated by stringing together ${tex`n`} rows of length ${tex`m`} together. We'll keep track of which rows may be placed next to one another using an adjacency matrix ${tex`A_m`}. The rows and columns of ${tex`A_m`} will be indexed by the set of all legal kings rows of length ${tex`m`}. Thus, ${tex`A_8`} will have 55 rows and columns since there are 55 legal kings rows of length 8. When we say that ${tex`A_m`} is an *adjacency matrix*, we mean that the entry in row ${tex`i`} and column ${tex`j`} will be ${tex`1`} if the ${tex`i^{\text{th}}`} row of kings may be placed next to ${tex`j^{\text{th}}`} row of kings and ${tex`0`} otherwise. The examples in the previous section show that the entry in row ${tex`11`} and column ${tex`22`} of ${tex`A_8`} is a ${tex`1`}. It turns out the matrices ${tex`A_m`} can also be generated with a recursive procedure. For ${tex`m=1`} note that the empty square may be placed next to itself or the occupied square, but the occupied square may only be placed next to the empty square. Thus ${tex`A_1`} is the following matrix: ${tex.block`A_1 = \begin{bmatrix}1&1\\1&0\end{bmatrix}.`} Similarly for ${tex`m=2`}, the empty row may be placed next to either of two rows containing a king but those may not be placed next to one another. Thus, ${tex.block`A_2 = \begin{bmatrix}1&1&1\\1&0&0\\1&0&0\end{bmatrix}.`} The recursive formula for ${tex`A_m`} is then ${tex.block`A_m = \begin{bmatrix} A_{m-1} & A_{m-2} \\ A_{m-2} & 0\end{bmatrix}.`} In this formula, we assume that ${tex`0`} represents a zero matrix of size ${tex`F_m`} and the copies of ${tex`A_{m-2}`} are padded appropriately with zeros to make the result a square matrix of size ${tex`F_{m+2}`}. The recurrence may be derived as follows. Recall that there are ${tex`F_{m+2} = F_{m+1} + F_m`} possible rows of length ${tex`m`}. We'll denote that set of rows by ${tex`R_m`}. Furthermore, the first ${tex`F_{m+1}`} elements in ${tex`R_m`} are exactly the rows in ${tex`C_{m-1}`} with an empty square at the end and these rows of length ${tex`m`} have the exact same adjacency conditions as the corresponding rows in ${tex`C_{m-1}`} . This leads to the copy of ${tex`A_{m-1}`} in the upper left hand corner of the recurrence. Similarly, the last ${tex`F_m`} rows in ${tex`R_m`} are exactly the rows in ${tex`R_{m-2}`} with two empty squares appended and the last ${tex`F_{m}`} rows in ${tex`R_m`} are exactly the rows in ${tex`R_{m-2}`} with an empty square and then a king. These rows have the adjacency relationships described by the copy of ${tex`A_{m-2}`} in the upper right of the recurrence. The copy of ${tex`A_{m-2}`} in the lower left appears by symmetry. Of course, the final ${tex`F_{m}`} rows in ${tex`R_m`} all have a king in the last square so no two of these may appear next to one another. This leads to the zero block in the lower right. Using this construction, we obtain the next two matrices in the sequence:35:T4ef,Often, the graph representation is nice conceptually, while the matrix representation is useful computationally. In the context of the Kings Problem, it's fairly easy to see that: > An ${tex`n\times m`} board can be generated by a walk of length ${tex`n-1`} steps through ${tex`G_m`}, where ${tex`G_m`} represents the adjacency graph for the set of Kings rows of length ${tex`m`}. We can compute the number of these walks using the following general property of adjacency matrices: > Let ${tex`G`} be a network graph and let ${tex`A`} be the corresponding adjacency matrix. Then, the entry in row ${tex`i`} and column ${tex`j`} of ${tex`A^{k}`} represents the number of walks of length ${tex`k`} in ${tex`G`} from node ${tex`i`} to node ${tex`j`}. Thus, if ${tex`A_8`} represents the kings matrix for rows of length ${tex`8`}, then the number of ways to place kings on a standard ${tex`8\times8`} chessboard is the sum of the entries in the matrix ${tex`A_8^7`}. A natural way to do this in the context of linear algebra is with the following computation: ${tex.block`\mathbf{1}^T A_8^7 \mathbf{1},`} where ${tex`\mathbf{1}`} is the vector of all ones. We can compute that with the following line of code that uses the [math.js](https://mathjs.org/) library:36:T9db,kings_graph = { // Group the nodes by number of kings and place them at the same rank. let group_code = []; let king_count_groups = d3.group(d3.range(55), (v) => king_count.get(v)); group_code.push(`{ rank=source; ${king_count_groups.get(4).join(";")} }`); group_code.push(`{ rank=same; ${king_count_groups.get(1).join(";")} }`); group_code.push(`{ rank=same; ${king_count_groups.get(2).join(";")} }`); group_code.push(`{ rank=sink; ${king_count_groups.get(3).join(";")} }`); // Use the adjacency matrix to form the edges let edges = []; for (let i = 0; i < A8.length; i++) { for (let j = i; j < A8.length; j++) { if (A8[i][j] == 1) { edges.push(`${i} -- ${j} [id="edge${i}--${j}"]`); } } } // Generate the dot source let source = `graph{ ratio=0.625 size=12 rankdir=TB nodesep=0.011 ${group_code.join("\n")} ${edges.join(";\n")}; }`; // Render the graph with dot let div = d3.create("div"); d3.graphviz(div.node()).engine("dot").renderDot(source); // Set up groovier tooltips on hover. div .selectAll("g.node") .nodes() .forEach(function (node) { let d3Node = d3.select(node); let n = d3Node.select("title").text(); d3Node.attr("data-v", n); let svg_code = row_pic(n).outerHTML; d3Node.select("ellipse").attr("fill", "white"); d3Node .select("text") .attr("cursor", "default") .style("pointer-events", "none"); tippy(node, { content: svg_code, theme: "light-border", maxWidth: 500, allowHTML: true }); }); div .selectAll("g.node") .on("pointerenter", function (_, b) { d3.select(this).style("stroke-width", 4); let a = adjacencies(b.key); div .selectAll("g.node") .nodes() .forEach(function (node) { let v = parseInt(node.getAttribute("data-v")); if (a.indexOf(v) > -1) { d3.select(node).select("ellipse").attr("fill", "lightblue"); div.select(`#edge${v}--${b.key}`).style("stroke-width", 4); div.select(`#edge${b.key}--${v}`).style("stroke-width", 4); } }); }) .on("pointerout", function () { d3.select(this).style("stroke-width", 1); div.selectAll("g.node").select("ellipse").attr("fill", "white"); div.selectAll(".edge").style("stroke-width", 1); }); div.selectAll("title").remove(); return div.node(); }37:T41f,// 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); } }38:[{"id":"c8f12879777b50467675cf920a5e8830504d729214019445ec42eade538b546298e7aa732c0128c97d775061e6bdac8c27454b29b90c675c707e0babb93c1667","href":"https://static.observableusercontent.com/files/c8f12879777b50467675cf920a5e8830504d729214019445ec42eade538b546298e7aa732c0128c97d775061e6bdac8c27454b29b90c675c707e0babb93c1667","name":"King.svg","type":"image/svg+xml","lastModified":1663349048793.126,"size":700}] 2f:{"id":"9afa987e26b27cf6","slug":"the-kings-problem","title":"The Kings Problem","thumbnail":"3797233fbf371141ad731089dddd45a981b5ae8e9dbeb4978b136face3aeb7b1","access_level":"public","create_time":"$D2022-09-13T20:33:58.224Z","update_time":"$D2022-11-14T15:32:18.839Z","view_time":null,"first_public_time":"$D2022-09-20T15:03:53.376Z","fork":false,"stars":16,"starred":false,"owner":{"type":"team","id":"d771c8ae812d5130","login":"mcmcclur","name":"Mark McClure","avatar_url":"https://avatars-next.observableusercontent.com/e615e819ce83d43faef607e48c53c5ff63943aa0ba9f5848499bd02fef7396f4","tier":"starter_2024"},"version":2233,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"c3301e515dd08a41","login":"mcmcclur","name":"Mark McClure","avatar_url":"https://avatars-next.observableusercontent.com/e615e819ce83d43faef607e48c53c5ff63943aa0ba9f5848499bd02fef7396f4","tier":null}],"members":[{"type":"individual","id":"c3301e515dd08a41","login":"mcmcclur","name":"Mark McClure","avatar_url":"https://avatars-next.observableusercontent.com/e615e819ce83d43faef607e48c53c5ff63943aa0ba9f5848499bd02fef7396f4","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":true,"trashed":false,"subscribed":null,"forks":6,"collection":{"id":"690a783fef281f79","slug":"math","title":"Math","owner":{"id":"d771c8ae812d5130","login":"mcmcclur","name":"Mark McClure"}},"type":"notebook","body":{"title":"The Kings Problem","cells":[{"id":0,"value":"# The Kings Problem\n\nThe Kings Problem asks:\n\n> How many ways are there to place some number of non-attacking kings on a chessboard?\n\nThe animation below shows some randomly generated boards with non-attacking kings. Each board is generated via a random walk through a graph that can be used to prove that the answer to the Kings Problem is ${d3.format(',')(board_cnt)}.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":384,"value":"viewof stop = Inputs.toggle({ label: \"Pause:\" })","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":381,"value":"kings_board_anim = {\n while (!stop) {\n await Promises.delay(1000);\n yield kings_board(random_kings_board_fen(), 800);\n }\n yield kings_board(random_kings_board_fen(), 800);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":683,"value":"## Solving the Kings Problem\n\nWe present here a solution to the Kings Problem that takes us through some nice mathematics, uses a little computer programming, and suggests an approach to the generalized the problem for larger chessboards.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":819,"value":"### A simpler problem\n\nWe begin with a simpler problem that will actually become the first step toward a recursive solution: How many ways are there to place non-attacking kings on a single row of a chessboard? You can use the slider below to visualize all the solutions.\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":648,"value":"viewof n = {\n let n = Inputs.range([0, 54], { step: 1, value: 0 });\n d3.select(n).select(\"input\").remove();\n return n;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":655,"value":"**Solution ${n+1}**: ${n == 0 ? 'No' : rows[n].match(/K/g).length} King${n>0 && rows[n].match(/K/g).length == 1 ? \"\" : \"s\"} ${n==0 ? \" is a solution!\" : \"\"}","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":617,"value":"row_pic(n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":698,"value":"### Solution to the simpler problem\n\nWe solve this simpler problem recursively, beginning with a ${tex`1\\times1`} board - also called a row of length one. There are two solutions for a ${tex`1\\times1`} board, you either leave the single square empty or you put a king on it:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":704,"value":"{\n let plot = Plot.plot({\n x: { domain: [0, 8] },\n width: 800,\n height: 100,\n margin: 1,\n marks: [\n Plot.rect([0], { x1: 0, x2: 1, y1: 0, y1: 1, stroke: \"#bbb\" }),\n Plot.rect([0], { x1: 3, x2: 4, y1: 2, y1: 1, stroke: \"#bbb\" })\n ]\n });\n\n d3.select(plot)\n .append(\"g\")\n .attr(\"transform\", `translate(${plot.scale(\"x\").apply(3)}) scale(2.2)`)\n .append(() => svg`${king}`);\n\n return plot;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":743,"value":"It's also pretty easy to see the solution for a row of length two, i.e. a ${tex`1\\times2`} board. You can leave the board empty or you could place a king on either of the two squares. This leads to three solutions:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":727,"value":"{\n let plot = Plot.plot({\n width: 800,\n height: 100,\n margin: 1,\n marks: [\n Plot.rect([0, 3, 6], {\n x1: (d) => d + 1,\n x2: (d) => d + 2,\n y1: 0,\n y1: 1,\n fill: \"#ddd\",\n stroke: \"#bbb\"\n }),\n Plot.rect([0, 3, 6], {\n x1: (d) => d,\n x2: (d) => d + 2,\n y1: 0,\n y1: 1,\n stroke: \"#ccc\"\n })\n ]\n });\n\n d3.select(plot)\n .selectAll(\"g.new\")\n .data([3, 7])\n .join(\"g\")\n .attr(\n \"transform\",\n (d) => `translate(${plot.scale(\"x\").apply(d)}) scale(2.2)`\n )\n .append(() => svg`${king}`);\n\n return plot;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":802,"value":"To construct a row of length three we consider two possibilities:\n\n - There's a king in the last spot or\n - There's not a king in the last spot.\n\nNote that we can construct all the ${tex`1\\times3`} boards with a king in the last spot by appending an empty square and then a king to a ${tex`1\\times1`} board:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":746,"value":"$31","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":809,"value":"Similarly, we can construct all the ${tex`1\\times3`} without a king in the last spot by appending an empty square to a ${tex`1\\times2`} board:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":794,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":812,"value":"$33","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":843,"value":"## From rows to boards\n\nWe can generate a board by stringing rows together. For example, here's the ${tex`11^{\\text{th}}`} row in our list of ${tex`1\\times8`} boards:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":916,"value":"row_pic(10)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":921,"value":"And, here's the ${tex`22^{\\text{nd}}`} row in our list of ${tex`1\\times8`} boards:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":924,"value":"row_pic(21)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":934,"value":"We could create a full ${tex`8\\times8`} board by alternating between these two:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":913,"value":"chessboard(\n [\n rows[10],\n rows[21],\n rows[10],\n rows[21],\n rows[10],\n rows[21],\n rows[10],\n rows[21]\n ].join(\"/\"),\n {\n size: 500,\n theme: {\n labelColor: \"white\",\n lightSquareFill: \"#FFF\",\n darkSquareFill: \"#DDD\",\n borderStroke: \"#DDD\"\n }\n }\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":938,"value":"Of course, we'll need to be careful not to place rows together that introduce attacking kings, like so:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":902,"value":"chessboard(\n [\n rows[10],\n rows[21],\n rows[10],\n rows[21],\n rows[10],\n rows[21],\n rows[10],\n rows[8]\n ].join(\"/\"),\n {\n size: 500,\n theme: {\n labelColor: \"white\",\n lightSquareFill: \"#FFF\",\n darkSquareFill: \"#DDD\",\n borderStroke: \"#DDD\"\n },\n call: (board) => {\n board.querySelector(\".square-e1\").setAttribute(\"fill\", \"#D00\");\n board.querySelector(\".square-e2\").setAttribute(\"fill\", \"#D00\");\n }\n }\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":942,"value":"$34","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":2217,"value":"tex.block`A_3 = \\left[\\begin{array}{ccc|cc}1&1&1&1&1\\\\1&0&0&1&0\\\\1&0&0&0&0\\\\\\hline1&1&0&0&0\\\\1&0&0&0&0\\end{array}\\right] \\text{ and } A_4=\\left[\n\\begin{array}{ccccc|ccc}1&1&1&1&1&1&1&1\\\\1&0&0&1&0&1&0&0\\\\1&0&0&0&0&1&0&0\\\\1&1&0&0&0&0&0&0\\\\1&0&0&0&0&0&0&0\\\\\\hline1&1&1&0&0&0&0&0\\\\1&0&0&0&0&0&0&0\\\\1&0&0&0&0&0&0&0\\end{array}\n\\right].`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1975,"value":"Of course, these matrices grow exponentially as ${tex`m`} increases so that they become harder to build and visualize. There's a `kings_matrix` function in the code below that automates the process of building the the kings matrices. For now, let's take a look at an alternative way to think about these adjacency structures.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":1472,"value":"### Representation as a graph\n\nThere's a natural correspondence between a 0-1 matrix and a network graph. The rows and columns of the matrix correspond to the nodes of the graph; node ${tex`i`} is connected to node ${tex`j`} by an edge in the graph iff the entry in row ${tex`i`} and column ${tex`j`} is a ${tex`1.`} For example, here are the Kings graphs for rows of length 1, 2, and 3:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":1640,"value":"dot`graph {rankdir=LR; 0--0; 0--1}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1985,"value":"---","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":1643,"value":"dot`graph {rankdir=LR; 0--0; 0--1; 0--2}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1987,"value":"---","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":1645,"value":"dot`graph {rankdir=TB; 0--0; 0--1; 0--2; 0--3; 0--4; 1--3}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1631,"value":"$35","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":1659,"value":"board_cnt = math.multiply(\n math.ones(55),\n math.pow(math.matrix(kings_matrix(8)), 7),\n math.ones(55)\n)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1893,"value":"## Large structures","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":1895,"value":"### The kings graph for rows of length 8\n\nThe kings graph for rows of length 8 is a bit hard to digest, since its got 55 nodes and 171 edges. To tame this thing a bit, let's rank the nodes by number kings in the corresponding row and add some interactivity to allow exploration. Here's the result:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":1890,"value":"$36","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1898,"value":"In this image, you can hover over nodes to display the corresponding row and highlight the connections. Here are a few observations to help interpret the graph:\n\n - All the nodes at a certain rank (i.e. height) correspond to rows with the same number of kings.\n - The node labeled zero, corresponding to the empty row, is adjacent to every node in the graph, including itself.\n - There are five rows with four kings corresponding to the five nodes at the top of the graph. These are all adjacent to only node zero.\n - The bottom row consists of nodes corresponding to rows with three kings. The four at the right are adjacent to only node zero but others can be adjacent to two or even three other nodes.\n - The two rows in the middle below node zero consist of nodes corresponding to rows with one or two kings.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":2110,"value":"### Fractal structure in the adjacency matrices\n\nThere's a common way to visualize a zero-one matrix that yields further insight into the adjacency structure. To do so, we create a raster plot; everywhere we see a one in the matrix, we'll plot a black pixel and everywhere we see a zero, we'll plot a white pixel. When we do so, an interesting fractal pattern arises as the limit of the images. Here's the result for ${tex`A_8`}, for example:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":2022,"value":"kings_matrix_plot(8)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2027,"value":"And for ${tex`A_{12}`}","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":2015,"value":"kings_matrix_plot(12)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2132,"value":"Aside from just looking cool, this suggests some stability in the growth of structures related to the matrices. In particular, the sequence of dominant eigenvalues grow exponentially, which turn out to be quite useful in the next section.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":1904,"value":"### Numerical estimates for larger boards\n\nThere's a natural generalization of the Kings problem to ${tex`n\\times m`} boards. The techniques described here provide the solution\n${tex.block`N_{m,n} = \\mathbf{1}^T A_m^{n-1} \\mathbf{1}.`}\nThis can be computed easily enough for values of ${tex`m`} and ${tex`n`} in the single digits. Once these get too much larger, though, the computation becomes cumbersome. It's natural to ask if we can make asymptotic estimates for large values of ${tex`m`} and ${tex`n`}. If you know a bit about eigenvalues, eigenvectors and the power rule, then its reasonable to guess that \n${tex.block`N_{m,n} \\approx \\lambda_m^{n+1},`}\nwhere ${tex`\\lambda_m`} is the dominant eigenvalue of ${tex`A_m`}. Furthermore, the ${tex`\\lambda_m`}s can be estimated using power iteration and, when we do so, it turns out that there's a nice pattern in their growth. Here's a table of those eigenvalues, together with the the ratios of one eigenvalue divided by the previous:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":2094,"value":"html`\n\n\n \n \n ${d3\n .range(eigenvalues.length)\n .map(\n (i) =>\n ``\n )}\n \n

${tex`\\mathbf{n}`}	${tex`\\mathbf{\\lambda_{n}}`}	${tex`\\mathbf{\\lambda_{n}/\\lambda_{n-1}}`}
${i + 1}	${eigenvalues[i]}	${\n i > 0 ? eigenvalues[i] / eigenvalues[i - 1] : \"\"\n }

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2103,"value":"This suggests that the eigenvalues might grow exponentially like ${tex`1.34^n`}. Putting this all together, we obtain the estimate:\n${tex.block`N_{m,n} = \\mathbf{1}^T A_m^{n-1} \\mathbf{1} \\approx 1.34^{m(n+1)}.`}\nThe following computation shows that the estimate is quite good for our board of size 8:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":2107,"value":"1.34 ** (8 * 9) / board_cnt","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2136,"value":"## A little history\n\nThe Kings Problem appears to have originated with Don Knuth, who was primarily interested in the asymptotic growth of the maximum number of kings that can be placed on a ${tex`(2m)\\times(2n)`} board. He wrote up some loose thoughts on the issue in early 1994; you can still find his TeX file of \"Nonattacking kings on a chessboard\" on his [list of unpublications](https://www-cs-faculty.stanford.edu/~knuth/preprints.html). Herb Wilf published a solution to Knuth's problem as [The Problem of the Kings](https://www.combinatorics.org/ojs/index.php/eljc/article/view/v2i1r3) in the second issue of The Electronic Journal of Combinatorics.\n\nI learned of the Kings Problem from Neil Calkin, who cofounded The Electronic Journal of Combinatorics with Wilf. The solution described here is Neil's.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":1121,"value":"## Code","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":1129,"value":"### Computational","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":1841,"value":"$37","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2146,"value":"// The kings matrix for a standard chessboard with rows of length 8\nA8 = kings_matrix(8)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":10,"value":"// Recursive construction of the set of all legal rows of length 8\nrows = {\n let extend1 = (s) => s + \"1\";\n let extend2 = (s) => s + \"1K\";\n let rows = [\n [\"K\", \"1\"],\n [\"1K\", \"K1\", \"11\"]\n ];\n\n for (let i = 0; i < 6; i++) {\n rows.push([rows[0].map(extend2), rows[1].map(extend1)].flat());\n rows.shift();\n }\n return rows[1].reverse();\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":371,"value":"// A Map object that allows us to quickly grab how many kings are in\n// row i of our list of rows.\nking_count = new Map(\n rows.map((s, i) => [i, s.match(/K/g) ? s.match(/K/g).length : 0])\n)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1348,"value":"// Function to compute the kings rows that may be placed\n// adjacency to the ith kings row.\nfunction adjacencies(i) {\n let row = A8[i];\n return row.map((v, i) => (v == 1 ? i : [])).flat();\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1147,"value":"function fibonacci(n) {\n let a = 0;\n let b = 1;\n let c;\n\n for (let i = 0; i < n; i++) {\n c = a;\n a = a + b;\n b = c;\n }\n\n return a;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1925,"value":"// The list of dominant eigenvalues of the kings matrices A_m\n// for a few values of m\neigenvalues = d3.range(1, 12).map(eigs)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1913,"value":"// Function to compute the dominant eigenvalues of the kings matrices\n// using power iteration\nfunction eigs(n) {\n let A = kings_matrix(n);\n let eigenvector = d3.range(A.length).map(() => 1);\n for (let i = 0; i < 30; i++) {\n eigenvector = math.multiply(A, eigenvector);\n eigenvector = eigenvector.map((x) => x / eigenvector[0]);\n }\n eigenvector = math.multiply(A, eigenvector);\n let eigenvalue = eigenvector[0];\n return eigenvalue;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1161,"value":"// Count vertices by valence\nd3\n .sort(\n Array.from(\n d3\n .group(\n A8.map((r) => d3.sum(r)),\n (x) => x\n )\n .values()\n ).map((a, i) => ({\n cnt: a.length,\n valence: a[0]\n })),\n (a) => a.valence\n )\n .reverse()","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2168,"value":"// Number of adjacencies in the Kings graph\n1 +\n (A8.flat(2)\n .map((i) => (i == 0 ? [] : 1))\n .flat().length -\n 1) /\n 2","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1124,"value":"### Graphics functions","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":994,"value":"// Raster plot of the kings matrix A_m\nfunction kings_matrix_plot(m, size = 400) {\n let pts = kings_matrix(m)\n .map((r, i) => r.map((v, j) => (v == 1 ? [j, i] : [])))\n .flat()\n .filter((a) => a.length > 0);\n\n return Plot.plot({\n x: { domain: [0, fibonacci(m + 2)], ticks: 0 },\n y: { domain: [fibonacci(m + 2), 0] },\n width: size,\n height: size,\n marks: [\n Plot.rect(pts, {\n x1: (d) => d[0],\n y1: (d) => d[1],\n x2: (d) => d[0] + 1,\n y2: (d) => d[1] + 1\n })\n ]\n });\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":519,"value":"// Generate an image of the nth legal kings row of length 8\nfunction row_pic(n) {\n let row_pic = Plot.plot({\n width: 800,\n height: 100,\n margin: 0,\n x: { domain: [0, 8] },\n y: { domain: [0, 1] },\n marks: [\n Plot.rect(d3.range(1, 10, 2), {\n x1: (d) => d,\n x2: (d) => d + 1,\n y1: 0,\n y2: 1,\n fill: \"#ddd\",\n stroke: \"#ddd\"\n }),\n Plot.line(\n [\n [0, 0],\n [8, 0],\n [8, 1],\n [0, 1],\n [0, 0]\n ],\n { stroke: \"#ccc\" }\n )\n ]\n });\n\n let matches = rows[n].matchAll(/K/g);\n let match_result = matches.next();\n while (!match_result.done) {\n d3.select(row_pic)\n .append(\"g\")\n .attr(\n \"transform\",\n `translate(${row_pic\n .scale(\"x\")\n .apply(match_result.value.index)}) scale(2.2)`\n )\n .append(() => svg`${king}`);\n match_result = matches.next();\n }\n\n return row_pic;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1127,"value":"// Use the main algorithm described here to generate a random, legal,\n// 8x8 chessboard and return it in Forsyth–Edwards notation.\nfunction random_kings_board_fen() {\n let v = d3.randomInt(0, 55)();\n let path = [v];\n for (let i = 0; i < 7; i++) {\n let choices = A8[v].map((x, i) => (x == 1 ? i : [])).flat();\n v = choices[d3.randomInt(0, choices.length)()];\n path.push(v);\n }\n return path.map((i) => rows[i]).join(\"/\");\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1136,"value":"// Generate the image of a kings board, given its Forsyth–Edwards notation\nfunction kings_board(fen, size) {\n return chessboard(fen, {\n size: size,\n theme: {\n labelColor: \"white\",\n lightSquareFill: \"#FFF\",\n darkSquareFill: \"#DDD\",\n borderStroke: \"#DDD\"\n }\n });\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2203,"value":"// The custom thumbnail\n{\n let div = d3\n .create(\"div\")\n .style(\"width\", \"640px\")\n .style(\"height\", \"400px\")\n .style(\"padding-top\", \"50px\");\n // .style(\"border\", \"solid 1px black\");\n\n let kb = await kings_board(random_kings_board_fen(), 320);\n div\n .append(\"div\")\n .style(\"display\", \"inline-block\")\n .append(() => kb);\n div\n .append(\"div\")\n .style(\"display\", \"inline-block\")\n .append(() => kings_matrix_plot(12, 320));\n\n return div.node();\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1153,"value":"### Imports","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":507,"value":"// Image from WikiMedia\n// https://commons.wikimedia.org/wiki/Category:SVG_chess_pieces\nking = (await (await FileAttachment(\"King.svg\")).text()).slice(55)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":900,"value":"// The images of the 8x8 chessboards are generated using Haris Lapiroff's chessboard function\nimport { chessboard } from \"@harrislapiroff/chessboard\"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1142,"value":"math = require(\"mathjs\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1164,"value":"tippy = require(\"tippy.js\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1167,"value":"tippy_style = html``","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1157,"value":"d3 = require(\"d3@7\", \"d3-graphviz@2\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"}],"files":"$W38","stdlib":"1","titling":"auto"}} 30:"$2f:body"