28:null 29:["$","title",null,{"children":"Eight Queens | Nate | Observable"}] 2e:Ta6b, function place_queen(queens = [], depth = 0) { // #--------------------------------------------------------------------------- // # If there are 8 queens placed, then this must be a solution. // #--------------------------------------------------------------------------- // if (length(queens) == 8) { // return(list(queens)) // } if (queens.length == 8) { // had to return this as an object, so that it didn't get flattened by .flat() later // had to return a length property so that filter(_=>_.length) does not exclude these: let result = { solution: queens, length: queens.length }; return result; } // #--------------------------------------------------------------------------- // # Figure out where a queen can be placed in the next row. // # Drop all columns that have already been taken - since we // # can't place a queen below an existing queen // #--------------------------------------------------------------------------- // possible_placements <- setdiff(1:8, queens) let possible_placements = setdiff(d3.range(1, 8+1), queens); // #--------------------------------------------------------------------------- // # For each queen already on the board, find the diagonal // # positions that it can see in this row. // #--------------------------------------------------------------------------- // diag_offsets <- seq.int(length(queens), 1) // diags <- c(queens + diag_offsets, queens - diag_offsets) // diags <- diags[diags > 0 & diags < 9] let diag_offsets = d3.range(queens.length, 0, -1); //.reverse() //queens.length, 1) let diags = [].concat(addel(queens, diag_offsets)).concat(addel(queens, diag_offsets, -1)); diags = diags.filter(diag => diag > 0 && diag < 9) // #--------------------------------------------------------------------------- // # Drop these diagonal columns from possible placements // #--------------------------------------------------------------------------- // possible_placements <- setdiff(possible_placements, diags) possible_placements = possible_placements.filter(x => !diags.includes(x)) // #--------------------------------------------------------------------------- // # For each possible placement, try and place a queen // #--------------------------------------------------------------------------- // possible_placements %>% // map(~place_queen(c(queens, .x))) %>% // keep(~length(.x) > 0) %>% // flatten() return possible_placements .map(placement => place_queen([].concat(queens).concat([placement]), depth + 1)) .filter(_ => _.length) .flat(); }2f:T656,function chibi (options={l:8, wpx:200, qsol : [1,5,6,8,2,4,7,3], bpx: 2}){ // this will render a "lightweight" version of chessboard, allowing me to control margins, turn off the labels, and use simple characters in place of the chessboard-pieces. // this way I can produce a visual that renders quickly in a browser, and looks more like the `geom_tile` in the original R blogpost let l = options.l || 8; let wpx = options.wpx || 200; let bpx = options.bpx || 2; let queen_solution = options.qsol || [1,5,6,8,2,4,7,3]; let pieces = options.pieces; // let pieces = [['Q']]; pieces = pieces || (queen_solution&&queen_solution.map(qindex=>{ let result = Array(l); result[qindex-1]='Q'; return result }).reverse()) || []; let color_1 = options.bgclr1 || 'white'; let color_2 = options.bgclr2 || '#e6e6e6'; //'#DDD'; let text_color = options.txtclr || 'white'; let piece_color = options.pclr || '#0092ff'; return html`

${ d3.range(1,l+1).map((row, row_index)=>{ return `

${ d3.range(1,l+1).map((col, col_index)=>{ let piece = (pieces[row_index]|| [])[col_index]; return `

${piece || ''}

`;}).join('') }

`}) }

`; }30:[] 2c:{"id":"da0fe6a90f0830a4","slug":"eight-queens","title":"Eight Queens","thumbnail":"b9e6c916fc3a9e46f812607ed0cca85392f2ac2028c0e12bd5fedbccc646dd5e","access_level":"public","create_time":"$D2020-11-14T23:33:51.988Z","update_time":"$D2022-11-15T18:06:37.159Z","view_time":null,"first_public_time":"$D2020-11-15T20:08:49.334Z","has_unpublished_edits":null,"fork":false,"stars":9,"starred":false,"owner":{"type":"team","id":"1b7482e6a3605cbf","login":"theredpea","name":"Nate","avatar_url":"https://avatars-next.observableusercontent.com/4f531c0b6a3be95f8811e91826ef6309f5e7968ba9ede56523913f5e30ef3ab2","tier":"starter_2024"},"version":476,"publish_version":476,"role":null,"authored":false,"authors":[{"type":"individual","id":"3dd0060e1bb28b29","login":"theredpea","name":"Nate","avatar_url":"https://avatars-next.observableusercontent.com/4f531c0b6a3be95f8811e91826ef6309f5e7968ba9ede56523913f5e30ef3ab2","tier":null}],"members":[{"type":"individual","id":"3dd0060e1bb28b29","login":"theredpea","name":"Nate","avatar_url":"https://avatars-next.observableusercontent.com/4f531c0b6a3be95f8811e91826ef6309f5e7968ba9ede56523913f5e30ef3ab2","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":1,"collection":{"id":"6ad523ac4dcb4b45","slug":"instagram-shares","title":"Observable's Instagram Shares","owner":{"id":"f35c755083683fe5","login":"observablehq","name":"Observable"}},"type":"notebook","body":{"title":"Eight Queens","cells":[{"id":0,"value":"md`# Eight Queens\n\nAn Observable translation of this [Eight Queens problem solver](https://coolbutuseless.github.io/2020/11/02/8-queens-chess-problem/) in R, from @coolbutuseless. Uses the \\`chessboard\\` Observable library from [@harrislapiroff/chessboard](https://observablehq.com/@harrislapiroff/chessboard)\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":226,"value":"// chessboard('start')\n{\n let i = 0;\n while (true){\n // TODO Use modulo to loop and repeat at beginning, otherwise what happens?\n let curr_index = ((i)%queen_solutions.length);\n let curr_solution = queen_solutions[curr_index].solution;\n yield Promises.delay(1000, chessboard(getFEN(curr_solution), {size: 800 }).then(cb=>html`

Solution ${curr_index+1}: (${curr_solution.join(',')})

${cb.outerHTML}`));\n i++;\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2,"value":"$2e","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":14,"value":"queen_solutions = place_queen()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":308,"value":"{\n // library(tidyverse)\n // v=1:8\n // f=function(q){L=length(q)\n // if(L==8){q}else{flatten(map(setdiff(v,c(q,q+L:1,q-L:1)),~f(c(q,.))))}}\n let at=8,\n f = (q)=>{let L=q.length, v=d3.range(1,at+1), d=d3.range(L, 0, -1);\n return L==at ? (q):(setdiff(v, [].concat(q, addel(q, d), addel(q,d.map(_=>-_)))).map(_=>f([].concat(q, _))).flat())\n }\n \n \n // s=data.frame(c=unlist(f(c())),r=v,x=rep(1:92,e=8),z=3)\n // b=mutate(crossing(c=v,r=v),z=(c+r)%%2)\n // g=geom_tile\n // ggplot(s,aes(r,c,fill=z))+g(d=b)+g()+facet_wrap(~x)\n let fs=f([]);\n \n return Promise.all(d3.range(1, fs.length+1, at).map(st=>chibi({l:8, wpx:60, bpx: -1, qsol: fs.slice(st-1, st-1+at), txtclr: 'transparent'})))\n .then(cbs=> html`\n ${ cbs.map((cb,cb_index)=>`

${cb.outerHTML}${cb_index+1}

`)}\n

\n `)\n \n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":228,"value":"function getFEN(queen_solution){\n // Translates the \"solution\" notation (element index + 1 is the row aka rank; element value is the column aka file)\n // Forsyth Edwards notation : https://en.wikipedia.org/wiki/Forsyth%E2%80%93Edwards_Notation\n // getFEN( [1, 5, 8, 6, 3, 7, 2, 4])\n // \"Q7/4Q3/7Q/5Q2/2Q5/6Q1/1Q6/3Q4\"\n return (queen_solution.solution || queen_solution)\n .reverse()\n .map((queen_file, queen_rank_zero)=>{\n // rank is irrelevant, just return in the same order\n let l = (queen_file-1 || '').toString(); // if the integer is 0, fallback on empty space\n let r = (8- queen_file || '').toString(); // if the integer is 0, fallback on empty space\n return `${l}Q${r}`;\n })\n .join('/');\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":352,"value":"$2f","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":159,"value":"\nfunction setdiff (first_array, second_array){\n // replacing setdiff \n // - https://2ality.com/2015/01/es6-set-operations.html \n // gotta keep them in order:\n return [...first_array].filter(x => ![...second_array].includes(x));\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":182,"value":"function addel(array_like_one, array_like_two, mult){\n // adding one element at a time, or subtracting \n // - https://stackoverflow.com/a/45342187/1175496\n return array_like_one.map((_,i)=>_+((mult || 1) * array_like_two[i]));\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":266,"value":"d3 = require('d3')","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":223,"value":"import { chessboard } from '@harrislapiroff/chessboard'","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W30","stdlib":"1","titling":"auto"}} 2d:"$2c:body"