2c:null 2d:["$","title",null,{"children":"8 Queens | Kelley van Evert | Observable"}] 32:T442,md`The classic 8-queens puzzle: *Can we place 8 queens on a chessboard in such a way that none of them threaten each other?* Well-solved with recursion, because we can state the problem generally as: ${tex.block`Q(N, P) \quad\textrm{iff}\quad \begin{cases} P \ne \varnothing & \textrm{if } N = 1 \\ \exists_{p \in P}\big[Q(N-1), P \setminus \{ q \mid q \sim p \} \big] & \textrm{else} \end{cases}`} Where we've defined a "threatening" relation as ${tex.block`(x_1, y_1) \sim (x_2, y_2) \quad\textrm{iff}\quad \textrm{any} \left\{\begin{array}{rcl} x_1 &=& x_2 \\ y_1 &=& y_2 \\ x_1-y_1 &=& x_2-y_2 \\ x_1-(8-y_1) &=& x_2-(8-y_2) \end{array}\right.`} And then ask the initial question ${tex.block`Q(8, \{ (x,y) \mid 1 \le x \le 8, 1 \le y \le 8 \})`} You can straightforwardly write this out in JavaScript, and interestingly the number of steps that have to be performed varies a great lot on the order of the fields initially provided. For instance, it might take as little as 10 steps, or as many as 30000. Below, you can play around with the shuffling of the list of fields.`33:T51f,{ if (!selected) return null const S = 30 const root = d3.select(svg` `) root.selectAll(".field").data(selected.ps, p => p.join("-")) .enter().append("rect") .attr("transform", ([x, y]) => `translate(${S*x} ${S*y})`) .attr("width", S) .attr("height", S) .attr("stroke", "none") .attr("fill", "#eee") const q = root.selectAll(".field").data(selected.queens, p => p.join("-")).enter(); q.append("circle") .attr("transform", ([x, y]) => `translate(${S*(x+.5)} ${S*(y+.5)})`) .attr("r", 10) .attr("height", S) .attr("stroke", "none") .attr("fill", "#333") q.append("text") .attr("transform", ([x, y]) => `translate(${S*(x+.5)} ${S*(y+.5)})`) .text((_, i) => i) .attr("fill", "white") .attr("font-weight", "bold") .attr("font-family", "monospace") .attr("text-anchor", "middle") .attr("alignment-baseline", "middle") return html`

Do ${selected.n} qeens fit in here (the lightgray fields)? ${selected.res ? "YES" : "no"}

${root.node()}

` }34:[] 30:{"id":"ff3060a54b9bdb08","slug":"8-queens","title":"8 Queens","thumbnail":"04e09b256cb6fef65127a8de823cf385951e7040ee8b95fb8cf01129b771fec7","access_level":"public","create_time":"$D2019-04-02T18:02:30.643Z","update_time":"$D2019-04-02T20:25:39.514Z","view_time":null,"first_public_time":"$D2019-04-02T18:31:39.511Z","has_unpublished_edits":null,"fork":false,"stars":3,"starred":false,"owner":{"type":"team","id":"cdda271b76654961","login":"kelleyvanevert","name":"Kelley van Evert","avatar_url":"https://avatars-next.observableusercontent.com/86df2bc54dd099fad6826dfcf7ae3dd97c5e0cdcf0cf3e0ac85ecd13e1938db2","tier":"starter_2024"},"version":495,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"a35690ff73833989","login":"kelleyvanevert","name":"Kelley van Evert","avatar_url":"https://avatars-next.observableusercontent.com/86df2bc54dd099fad6826dfcf7ae3dd97c5e0cdcf0cf3e0ac85ecd13e1938db2","tier":null}],"members":[{"type":"individual","id":"a35690ff73833989","login":"kelleyvanevert","name":"Kelley van Evert","avatar_url":"https://avatars-next.observableusercontent.com/86df2bc54dd099fad6826dfcf7ae3dd97c5e0cdcf0cf3e0ac85ecd13e1938db2","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":1,"collection":{"id":"7eacc2f229920947","slug":"ideas","title":"Nerdy","owner":{"id":"cdda271b76654961","login":"kelleyvanevert","name":"Kelley van Evert"}},"type":"notebook","body":{"titling":"auto","title":"8 Queens","cells":[{"id":0,"value":"md`# 8 Queens`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":385,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":48,"value":"md`**Number of queens & board size:**`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":4,"value":"viewof N = number({ min: 1, max: 20, step: 1, value: 8 })","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":6,"value":"fields = Array.from({ length: N*N }).map((_, i) => [i % N, Math.floor(i / N)])","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":243,"value":"mutable selected = null","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":283,"value":"viewof rerun = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":241,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":200,"value":"{\n function display_node (node) {\n const li = d3.select(html`

${node.children.map(display_node)}\n

`)\n li.select(\".info\").on(\"mouseover\", () => mutable selected = node)\n return li.node()\n }\n \n return html`\n

Total number of steps for this shuffling: ${tree.steps}

${display_node(root)}\n \n `\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":18,"value":"Q = {\n function Q (n, ps, parent, queens = []) {\n (mutable tree).steps++;\n const node = { n, ps, queens, parent, children: [] }\n parent.children.push(node)\n if (n === 1) {\n node.res = ps.length >= 1\n if (node.res) {\n node.winning = { n: 0, ps: [], queens: [...queens, ps[0]], children: [], res: true }\n node.children.push(node.winning)\n }\n }\n else {\n node.res = any(ps, p => Q(n - 1, ps.filter(unrel(p)), node, [...queens, p]))\n }\n \n if (node.res) {\n parent.winning = node\n }\n return node.res\n }\n \n return Q\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":56,"value":"mutable tree = null","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":196,"value":"root = tree.children[0]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":24,"value":"{\n rerun\n mutable tree = { steps: 0, children: [] }\n Q(N, shuffle(fields), mutable tree)\n \n let sel = (mutable tree).children[0]\n while (sel.winning) {\n sel = sel.winning\n }\n mutable selected = sel\n \n return md`**[This cell bootstraps the computation]**`\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":493,"value":"md`**Helpers, libraries**`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":19,"value":"any = (arr, c) => arr.reduce((any, item) => any || c(item), false)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":8,"value":"unrel =\n ([x1, y1]) =>\n ([x2, y2]) => !(\n (x1 === x2)\n || (y1 === y2)\n || (x1-y1 === x2-y2)\n || (x1-(N-y1) === x2-(N-y2))\n )","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":275,"value":"function shuffle(a) {\n for (let i = a.length - 1; i > 0; i--) {\n const j = Math.floor(Math.random() * (i + 1));\n [a[i], a[j]] = [a[j], a[i]];\n }\n return a;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":69,"value":"d3 = require(\"d3\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":42,"value":"import { number, slider } from \"@jashkenas/inputs\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W34","stdlib":"1"}} 31:"$30:body"