2b:null 2c:["$","title",null,{"children":"How to Model a Rubik's Cube and Write Solvers | Zhouheng (Jeffrey) Sun | Observable"}] 31:T45f,md`## Step 1: Know your representations There are multiple ways to go about representing a cube, forming a hierarchy from physical to abstract shown below. As we'll explain later, each comes with some unique advantages: - **Geometry-based** : each piece / sticker is a point in the 3d space - useful for modeling moves - **Facelet-based**: a cube is a permutation of its stickers, or, facelets (54 for Rubik's cube) - useful for visualization and partial solving - **Piece-based**: stickers that belong to the same edge or corner piece are physically inseparable. Piece-based models make use of this fact, to model each piece by their orientation and permutation. - useful for random state generation, state legality check, and optimized solving I will walk you through my own approach to model the cube in a fairly natural way, switching between these different representations when necessary, in order to give you a reference point so you can build your own Rubik's cube application. Note that this article focuses on ease of understanding and coding. It will not particulary address the optimizations. `32:T5f0,gmoves = { let create_move_set = (base_name, axis, pred) => { let move1 = create_gmove(base_name, axis, 90, pred) let move2 = create_gmove(base_name + "2", axis, 180, pred) let move3 = create_gmove(base_name + "'", axis, 270, pred) return [move1, move2, move3] } let U = create_move_set("U", new Vec(0, 1, 0), (pos) => pos.y > 0) let u = create_move_set("u", new Vec(0, 1, 0), (pos) => pos.y >= 0) let D = create_move_set("D", new Vec(0, -1, 0), (pos) => pos.y < 0) let d = create_move_set("d", new Vec(0, -1, 0), (pos) => pos.y <= 0) let E = create_move_set("E", new Vec(0, 1, 0), (pos) => pos.y === 0) let y = create_move_set("y", new Vec(0, 1, 0), () => true) let L = create_move_set("L", new Vec(-1, 0, 0), (pos) => pos.x < 0) let R = create_move_set("R", new Vec(1, 0, 0), (pos) => pos.x > 0) let l = create_move_set("l", new Vec(-1, 0, 0), (pos) => pos.x <= 0) let r = create_move_set("r", new Vec(1, 0, 0), (pos) => pos.x >= 0) let M = create_move_set("M", new Vec(-1,0, 0), (pos) => pos.x === 0) let x = create_move_set("x", new Vec(1, 0, 0), () => true) let F = create_move_set("F", new Vec(0, 0, 1), (pos) => pos.z > 0) let B = create_move_set("B", new Vec(0, 0, -1), (pos) => pos.z < 0) let S = create_move_set("S", new Vec(0, 0, 1), (pos) => pos.z === 0) let z = create_move_set("z", new Vec(0, 0, 1), () => true) let gmoves = {}; [U, D, u, d, E, y, L, R, l, r, M, x, F, B, S, z].flat().map(move => gmoves[move.name] = move) return gmoves }33:T573,md`### Step 8c: from G2 to G3 -- Opposite Color on Opposite Side + Corner Orbits

${tex`G_2 = \longrightarrow G_3 = `}

We shall reduce the cube so it becomes half turn solveable. Obviously, a basic constraint is to get all opposite colors to be on opposite faces (cuz you can only swap pieces on opposite faces with half turns). On top of that, we need something more for corners. Sometimes, even when the basic constraint is satisfied, corners still cannot be solved with half turns due to **parity** (for example, consider the y perm on a 2x2). To avoid that, corner permutations must fall into one of 96 permitted states, or orbits. #### Generating the corner table The corner parity slightly complicates our solver definition -- now the condition for solved becomes more nuanced. Luckily, we can work from backwards, starting from the solved cube, and explore all the half-turn generated corner permutations (there should be exactly 96 of these), and simply store them in a table and look it up to determine if a state is in G3. In fact, we can borrow a pruning table to explore the states for us. To create that pruning table, let's consider what we need for the half-turn corner orbit mask. Well, let's just be generous and include all the corner facelets with \`g3_corner_mask\`! `34:Tc03,draw_gcube_demo = () => { let gcube_demo_length = 40 let gcube_demo_margin = 0 let style = `` let piece = (x, y, z) => { let rotate = (Math.abs(z) === 3) ? "" : (Math.abs(y) === 3) ? "rotateX(90deg)" : "rotateY(90deg)" let l = (gcube_demo_length + gcube_demo_margin) / 2 let transform = `transform: translateX(${x * l}px) translateY(${y * l}px) translateZ(${z * l}px) translate(-50%, -50%) ${rotate} ` let classes = (y === -3 && x === 0 && z === 0) ? "cube_face_u_center" : (x === 3 && y === -2 && z === 0) ? "cube_face_r_u" : "" return `

` } let scene = html` ${style}

${solved_gcube.map(s => piece(s.pos.x, s.pos.y, s.pos.z)).join("\n") }

` return scene }35:T4c6,scramble_interface = (id, gen_func) => { const form = html`` const wrap = html`

${form}` const input = html`

` const gen = html`` gen_func = gen_func || gen_scramble input.firstElementChild.value = gen_func() gen.onclick = (event) => { document.getElementById(`${id}_input`).value = gen_func() wrap.value = document.getElementById(`${id}_input`).value; event.currentTarget.dispatchEvent(new CustomEvent("input", {bubbles: true})) } const solve = html`` solve.onclick = (event) => { wrap.value = document.getElementById(`${id}_input`).value; event.currentTarget.dispatchEvent(new CustomEvent("input", {bubbles: true})) } form.appendChild(input) form.appendChild(gen) form.appendChild(solve) //form.addEventListener("change", () => form.dispatchEvent(new CustomEvent("input", {bubbles: true})) ) //f//orm.addEventListener("input", () => { } ) wrap.value = "" return wrap }36:[] 2f:{"id":"b908ba5779cc3b95","slug":"how-to-model-a-rubiks-cube","title":"How to Model a Rubik's Cube and Write Solvers","thumbnail":"582836d2554bc3991e649501d5c9cabb4680f1500102823449d1ab4f9a4b777b","access_level":"public","create_time":"$D2020-11-22T21:05:24.410Z","update_time":"$D2024-04-23T02:23:08.532Z","view_time":null,"first_public_time":"$D2020-11-24T02:58:30.812Z","fork":true,"stars":16,"starred":false,"owner":{"type":"team","id":"dd97d788d86e95f8","login":"onionhoney","name":"Zhouheng (Jeffrey) Sun","avatar_url":"https://avatars-next.observableusercontent.com/291ec9640cd16e7341d5f6951c390abff150ca54524e31a241a74ddf76fb7813","tier":"starter_2024"},"version":4428,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"1b3d3c858eeaffa0","login":"onionhoney","name":"Zhouheng (Jeffrey) Sun","avatar_url":"https://avatars-next.observableusercontent.com/291ec9640cd16e7341d5f6951c390abff150ca54524e31a241a74ddf76fb7813","tier":null}],"members":[{"type":"individual","id":"1b3d3c858eeaffa0","login":"onionhoney","name":"Zhouheng (Jeffrey) Sun","avatar_url":"https://avatars-next.observableusercontent.com/291ec9640cd16e7341d5f6951c390abff150ca54524e31a241a74ddf76fb7813","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":true,"trashed":false,"subscribed":null,"forks":12,"collection":{"id":"731be5907a6f2955","slug":"cubing","title":"Cubing","owner":{"id":"dd97d788d86e95f8","login":"onionhoney","name":"Zhouheng (Jeffrey) Sun"}},"type":"notebook","body":{"title":"How to Model a Rubik's Cube and Write Solvers","cells":[{"id":0,"value":"md`# How to Model a Rubik's Cube and Write Solvers`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4316,"value":"viewof tt_demo_scramble = {\n let scr = scramble_interface(\"demo\")\n let view = html`

\n Demo: a Rubik's Cube solver we'll build in step 8

${scr}

`\n scr.addEventListener(\"input\", () => { view.value = scr.value; })\n return view\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4324,"value":"{\n const tt_demo_solution = solve_thistlethwaite(create_ifcube(tt_demo_scramble))\n \n let scr = tt_demo_scramble\n let s = tt_demo_solution\n let cube = (...moves) => apply_fmoves(solved_cube, moves.join(\" \"))\n let graph = vis1([\n [ cube(scr), \"Scramble\" ],\n [ cube(scr, s[0]), `Reduce to G1:
${s[0]}` ],\n [ cube(scr, s[0], s[1]), `Reduce to G2:
${s[1]}` ],\n [ cube(scr, s[0], s[1], s[2]), `Reduce to G3:
${s[2]}` ],\n [ cube(scr, s[0], s[1], s[2], s[3]), `Reduce to solved:
${s[3]}`]\n ])\n \n return html`

${md`Solution = \\`${s.join(\" \")} (${ s.join(\" \").split(\" \").length}f)\\` `}

${graph}

`\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1077,"value":"md`\nWhether you're a coder, a speedcuber or both, you must have wondered how to model a Rubik's Cube programmatically, and build stuff like **cube solvers** and **simulators** out of it.\n\nThis article will show you exactly how do to that. What sets it apart is the approach -- it neither too abstract nor too technical, but seeks to strike a good balance in between, so it can be both practical and understandable by non-expert programmers and non-expert cubers alike. **You're gonna read the code alongside the text explanations.** Everything is derived programmatically from scratch, and all code is fully shown and explained.\n\nWe'll go over different cube models in Step 1-4, build a simulator in Step 5, build some partial cube solvers in Step 6-7, and build a full Rubik's cube solver with the Thistlethwaite method in Step 8.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1415,"value":"html`

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2,"value":"$31","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":22,"value":"md`## Step 2: Visualize with the facelet system\n\nHow to quickly draw the cube? We'll use the simple 2d unfolded form to show the 6 faces. On each face there are 9 colored pieces, which we call the facelets. \nWe want to draw \\`6 * 9 = 54\\` squares with 6 possible colors in the right places on a canvas. The natural cube model for this task is gonna be the **facelet-based** model. \n\nLet's encode the 54 facelets (stickers) with a string of 54 characters.\nWe name the 6 faces \\`URFDLB\\` (Up, Right, Front, Down, Left, Back). We also use the same 6 letters to refer to the color belonging to each face on a solved cube.\n\nWe designate the face ordering to be \\`URFDLB\\`, that is the first set of 9 characters describe what colored stickers currently occupy the 9 positions on the U face, the second set describing R face, etc. \n\n\nThen a solved cube will be 9 \\`U\\`s, followed by 9 \\`R\\`s, etc. \n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":535,"value":"solved_cube = [...\"URFDLB\"].map(s => s.repeat(9)).join(\"\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":533,"value":"\nmd`Let's draw the cube because it's hard to tell what's going on from its string form. \n Feel free to change the color scheme by editing the 'color' object.`\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1351,"value":"html`

\n ( This is an interactive notebook! Click to the left side of any code block to inspect or edit it -- changes will be instantly propagated. ) \n

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":128,"value":"\ncolor = ({\n \"U\": \"white\", \"D\": \"yellow\", \"L\": \"orange\", \"R\": \"red\", \"F\": \"#00aa00\", \"B\": \"blue\", \"X\": \"darkgray\",\n // more colors for step 8\n \"o\": \"#fdfdc6\", \"x\": \"blueviolet\", \"y\": \"magenta\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":41,"value":"function vis(cube) {\n const sc = 15; // scale factor = length of each sticker in pixels.\n const canvas = DOM.canvas(13 * sc, 10 * sc);\n const ctx = canvas.getContext('2d');\n \n // Retina display hacks\n scaleCanvas(canvas, ctx)\n ctx.translate(sc / 2, sc / 2)\n \n function draw(idx, r, c) {\n for (let i = r; i <= r + 2; i++)\n for (let j = c; j <= c + 2; j++) {\n ctx.fillStyle = color[cube[idx++]];\n ctx.fillRect(sc * j, sc * i, sc, sc);\n ctx.lineWidth = 2\n ctx.strokeRect(sc * j, sc * i, sc, sc)\n }\n }\n \n // draw the faces\n draw( 0, 0, 3) // U\n draw( 9, 3, 6) // R\n draw(18, 3, 3) // F\n draw(27, 6, 3) // D\n draw(36, 3, 0) // L\n draw(45, 3, 9) // B\n \n return canvas\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":43,"value":"vis(solved_cube)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":123,"value":"md`## Step 3: An attempt to define the moves\nIn our model, moves are simply permutations of facelets.\n\nWe model permutation as a list of \\`(source, dest)\\` pairs where the facelet at index \\`source\\` goes to index \\`dest\\`.\n\n\nBefore we start, let's invent a notation \\`S(face, idx)\\` so we can easily refer to the facelets. For instance, \n\\`S(F, 4)\\` will refer to the 4th facelet on the F face (FL), counting from top to bottom, left to right. In fact, to make things clear let's draw the index labels on each face.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1425,"value":"S = function(f, i){\n return \"URFDLB\".indexOf(f) * 9 + i - 1\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1429,"value":"facelet_labeling = {\n const sc = 20; // scale factor = length of each sticker in pixels.\n const canvas = DOM.canvas(13 * sc, 10 * sc);\n const ctx = canvas.getContext('2d');\n \n // Retina display hacks\n scaleCanvas(canvas, ctx)\n ctx.translate(sc / 2, sc / 2)\n ctx.font = '11px Courier';\n ctx.textBaseline = 'middle';\n function draw(face, r, c) {\n let idx = 0\n for (let i = r; i <= r + 2; i++)\n for (let j = c; j <= c + 2; j++) {\n ctx.fillText(face + (++idx), sc * j + sc / 6, sc * i + sc / 2);\n ctx.lineWidth= 2\n ctx.strokeRect(sc * j, sc * i, sc, sc)\n }\n }\n \n // draw the faces\n draw( \"U\", 0, 3) // U\n draw( \"R\", 3, 6) // R\n draw( \"F\", 3, 3) // F\n draw( \"D\", 6, 3) // D\n draw( \"L\", 3, 0) // L\n draw( \"B\", 3, 9) // B\n \n return canvas\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":171,"value":"md`And some utility functions: *perm_from_cycle* maps a cycle \\`(a,b,c)\\` to permutations \\`(a,b) (b,c) & (c,a)\\`. \n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":204,"value":"md`### Example 1: U move\nLet's start with the U move. It's permutation can be described with the five cycles below. `","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":145,"value":"u_move = \n [\n perm_from_cycle( [ S(\"U\",1), S(\"U\",3), S(\"U\",9), S(\"U\",7) ] ),\n perm_from_cycle( [ S(\"U\",2), S(\"U\",6), S(\"U\",8), S(\"U\",4) ] ),\n perm_from_cycle( [ S(\"F\",1), S(\"L\",1), S(\"B\",1), S(\"R\",1) ] ),\n perm_from_cycle( [ S(\"F\",2), S(\"L\",2), S(\"B\",2), S(\"R\",2) ] ),\n perm_from_cycle( [ S(\"F\",3), S(\"L\",3), S(\"B\",3), S(\"R\",3) ] ),\n ].flat()","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":211,"value":"md`Now that we've modeled the U move, let's try it out on our cube. The \\`apply_move\\` function will take a cube and a move (i.e. a permutation), and return the new cube. Let's visualize \\`apply_move(solved_cube, u_move)\\` to see what happens: `","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":735,"value":"apply_move = function(cube, perm) {\n let new_cube = [...cube]\n for (let x of perm) {\n new_cube[x[1]] = cube[x[0]]\n }\n //perm.forEach( ([src, dst]) => new_cube[dst] = cube[src] );\n return new_cube\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":227,"value":"vis(apply_move(solved_cube, u_move))","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":260,"value":"\nmd`**Great**! Now we have something working.\nIt's time to derive the other layer moves. However this is rather tedious -- we have to manually come up with a long list of permutations for each move. Even if we can simplify a bit by defining base moves and derive the rest as their combination, the facelet system will remain a headache when it comes to other concerns: for instance, say we want to have a notion of what piece each sticker belongs to. Do we know which facelet on U belongs to piece \\`UFR\\`? To express this facelet-piece association will then require another round of maual labeling. \n\nNonetheless, we've established that current \"string of facelets\" system makes our visualization quite easy. Maybe we still want to save this representation for the **visualization layer**, while using a different representation to model the movement and pieces instead? \n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":264,"value":"md`## Step 4: Redefining moves with geometry\n\nWe want to find a representation that makes the cube-modeling process as programmatic as possible. What abstraction gives a **natural** definition of the moves and sticker-piece correspondence, etc.? Well, perhaps the geometry-based model could work. I mean, what are moves on a Cube but pieces of a plastic toy rotating along a metal axis? \n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":573,"value":"md`Let's try that out now. \n\nFirst we'll create physical representations for each **sticker**! \nA sticker here is similar to a facelet in the facelet system, only that it has *no* color associated, but rather :\n\n\\`sticker := (target, current)\\` \n\n\\` target := a 3D vector, describing the position it belongs to \\`\n\n\\`current := a 3D vector, describing position it's now at \\`\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":588,"value":"create_sticker = (pos, dst) => ({pos: pos, dst : dst || pos})","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":590,"value":"md`We'll adopt THREE.js's coordinate system as below. `\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":577,"value":"html`

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":631,"value":"md`\nTo make sure coordinates are integers, we set the length of each cubic piece to 2. The center of the cube will be (0, 0, 0), while the U center piece will be centered on (0, 2, 0). Therefore, the U center **sticker** , as it stays on top of the surface, will have coordinate (0, 3, 0). \n\nSimilarly, the UR piece will be centered at (2, 2, 0), with the U sticker at (2, 3, 0) and the R sticker at (3, 2, 0).\n\n(if this confuses you for now, worry not.. keep reading and you'll eventually get the idea. )\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1565,"value":"draw_gcube_demo()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":594,"value":"md`And then, a move is really just AXIS and ANGLES!\nWell, almost... we also need a function to tell whether a sticker at its current position will participate in the rotation or not. We call that function \\`predicate\\`.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":308,"value":"create_gmove = (name, axis, angle, predicate) => ({ name, axis, angle, predicate } )","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":647,"value":"md`To give you an idea, here's how to write \\`u_move\\` in our geometric system:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":649,"value":"create_gmove(\"U\", new Vec(0, 1, 0), 90, (pos) => pos.y > 0)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":610,"value":"md`A cube is simply a collection of these stickers. Moves will be applied to each sticker, performing the rotation on their current \\`pos\\` whenever the predicate returns true: `","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":325,"value":"apply_sticker = (move, sticker) => (\n (move.predicate(sticker.pos)) ? // does the move involve this position? \n {...sticker, pos: new Vec().copy(sticker.pos).applyAxisAngle( move.axis, -move.angle / 180 * Math.PI ).round() } : // if so, rotate around axis with angle\n sticker ) // else, do nothing","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":661,"value":"md`Hey we're almost there! I'll let you read through the rest on your own. `","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":329,"value":"apply_gmove = (cube, move) => cube.map(s => apply_sticker(move, s))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":387,"value":"get_face = (sticker) => {\n let {x, y, z} = sticker\n return (x === 3) ? \"R\" :\n (x === -3) ? \"L\" :\n (y === 3) ? \"U\" :\n (y === -3) ? \"D\" :\n (z === 3) ? \"F\" :\n (z === -3) ? \"B\" : \"X\"\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":281,"value":"solved_gcube = {\n let stickers = []\n for (let face of [3, -3]) {\n for (let coord1 of [-2, 0, 2]) {\n for (let coord2 of [-2, 0, 2]) {\n stickers.push(...[ create_sticker(new Vec(face, coord1, coord2)),\n create_sticker(new Vec(coord1, face, coord2)),\n create_sticker(new Vec(coord1, coord2, face)) ])\n }\n }\n }\n return stickers\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":664,"value":"md`

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":653,"value":"md`### Step 4b: All moves defined, geometrically\n\nFinally, here we are!!\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":353,"value":"$32","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":431,"value":"apply_gmoves= (gcube, moves) => \n moves.trim().split(/ +/).filter(s => s).map(m => gmoves[m]).reduce( apply_gmove, gcube )","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":675,"value":"md`### Step 4c: Visualize by converting back to facelets `","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2690,"value":"md`Since our visualizer only takes facelets, it's time to write a converter. Let's do this with minimal manual labor: we only need to write down the translation from U face stickers to U facelets, and reuse it --- for the other faces, we rotate their sticker coordinates to the U face in a way that our U face translation will produce the correct facelet ordering for that face. Expand the code below for more details. `","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":379,"value":"gcube_to_fcube = (gcube) => {\n // URFDLB\n let scube = []\n let fill_face = (stickers, idx) => {\n stickers.sort( (s, t) => s.pos.z - t.pos.z || s.pos.x - t.pos.x ).forEach(s => {\n scube[idx++] = get_face(s.dst) } ); \n };\n let face_rotating_moves = [\"\", \"y x\", \"x\", \"x2\", \"y' x\", \"y2 x\"]\n face_rotating_moves.forEach( (moves, i) => \n fill_face(apply_gmoves(gcube, moves).filter(s => get_face(s.pos) === \"U\"), i * 9) )\n return scube.join(\"\")\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":717,"value":"md`Now that we've defined all moves on a cube, it's time to test them out! `","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":719,"value":"draw = (scramble) => vis( gcube_to_fcube( apply_gmoves (solved_gcube, scramble) ) )","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":406,"value":"draw(\"M' U M'\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":722,"value":"{\n let moves = \"R U R' U' \".repeat(6).split(\" \").filter(s => s)\n for (const i of tick(900)) {\n yield i.then(i => {\n return draw(moves.slice(0, i % 24).join(\" \"))\n })\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":742,"value":"md`## Step 5: A 3D Simulator for free \nLet's take a moment to review.\n\nFirst , we bootstraped our cube modeling effort with the **facelet** system. It's nice cuz it gives us super easy 2D visualization to inspect any cube models we have, which is necessary in guiding our initial explorations.\n\nThen, we proceed to find some of its weakness, and switch to the **geometric** system to better model the moves. \n\nBefore we try to do more with our model (solving, random state generating, etc.), let's take a moment to appreciate what we've built so far with the **geometric** system. In fact, we've created a 3D simulator for free! \n\nAll that is left to do is:\n1. draw the stickers according to their 3D positions, with a graphics library\n2. have some basic keyboard mappings to update the cube on each keypress\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":755,"value":"md`We'll make a brief detour to set up the graphics engine. Trust me, it's simple enough. Just a bunch of boilerplate code. Let's start. `","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":942,"value":"md`### 5b. Setting up the graphics\nOur graphics library only need three things: the renderer (calculates the pixels), the scene (collection of 3d objects), and the camera (our viewpoint). The following code sets them up. \n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":947,"value":"renderer = {\n const renderer = new THREE.WebGLRenderer({ antialias: true })\n renderer.setSize(sim_width, sim_height)\n renderer.setPixelRatio(devicePixelRatio);\n return renderer\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":816,"value":"scene = (meshes) => {\n let scene = new THREE.Scene()\n scene.background = new THREE.Color(0x444444);\n for (let mesh of meshes) scene.add(mesh)\n return scene\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":818,"value":"camera = {\n const camera_position = new Vec(5, 6, 6)\n let camera = new THREE.PerspectiveCamera(75, sim_width / sim_height, 0.1, 1000)\n camera.position.copy(camera_position)\n camera.lookAt(new Vec(0,0,0))\n return camera\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":974,"value":"md`### 5c.Adding in the sticker objects, et Voila!` ","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":953,"value":"md`Now comes the crux of our 3d simulator: for each sticker, create a corresponding 3D object (*mesh*) in our graphics engine. A mesh really is just a flat 3d cube (*geometry*) with a color (*material*). \n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1641,"value":"create_mesh = (sticker) => {\n const geometry = new THREE.BoxGeometry(1.6, 0.1, 1.6)\n const color = sim_colors[get_face( sticker.dst )]\n const material = new THREE.MeshBasicMaterial({ color })\n const mesh = new THREE.Mesh(geometry, material)\n mesh.position.copy( sticker.pos ) // IMPORTANT: we assign the position directly from the geometric cube\n \n // rotate the sticker plate \n const current_face = get_face( sticker.pos )\n if (current_face === \"F\" || current_face === \"B\")\n mesh.setRotationFromAxisAngle(new Vec(1, 0, 0), Math.PI / 2)\n else if (current_face === \"L\" || current_face === \"R\")\n mesh.setRotationFromAxisAngle(new Vec(0, 0, 1), Math.PI / 2)\n return mesh\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":944,"value":"sticker_mesh = (cube) => cube.map(create_mesh)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":994,"value":"md`\nFinally these objects are going to be added to our \\`scene\\`, and we call render in a loop to continuously render the scene. We also throw in a little bit of magic to monitor whenever a key is pressed, and update the the cube and graphics objects accordingly. Now our simulator is up and running!\n\n*(Hint: If you don't know what the default mapping is, press I J K F and see what happens! Enter to reset.)*\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":806,"value":"sim_display = { \n renderer.render(scene(sticker_mesh(sim_cube)), camera)\n return renderer.domElement\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1007,"value":"key_monitor = {\n window.addEventListener('keydown', (e) => {\n const key = e.key.toUpperCase()\n if (key === \"ENTER\") mutable sim_cube = solved_gcube\n else if (key in key_mapping) mutable sim_cube = apply_gmoves(sim_cube, key_mapping[key])\n })\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":922,"value":"key_mapping = ({\"I\": \"R\",\n \"K\": \"R'\",\n \"W\": \"B\",\n \"O\": \"B'\",\n \"S\": \"D\",\n \"L\": \"D'\",\n \"D\": \"L\",\n \"E\": \"L'\",\n \"J\": \"U\",\n \"F\": \"U'\",\n \"H\": \"F\",\n \"G\": \"F'\",\n \";\": \"y\",\n \"A\": \"y'\",\n \"U\": \"r\",\n \"R\": \"l'\",\n \"M\": \"r'\",\n \"V\": \"l\",\n \"T\": \"x\",\n \"Y\": \"x\",\n \"N\": \"x'\",\n \"B\": \"x'\",\n \".\": \"M'\",\n \"X\": \"M'\",\n \"5\": \"M\",\n \"6\": \"M\",\n \"P\": \"z\",\n \"Q\": \"z'\",\n \"Z\": \"d\",\n \"C\": \"u'\",\n \",\": \"u\",\n \"/\": \"d'\"\n })","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":928,"value":"sim_colors = ({\n \"U\": 0xffffff, \"D\": 0xffff00, \"F\": 0x00aa00, \"B\": 0x0000ff, \"L\": 0xffa500, \"R\": 0xff0000 });","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1111,"value":"step6 = md`## Step 6: Building a simple First Block solver`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3051,"value":"md`We are going to build a simple DFS partial solver to solve the **First Block** (FB) of the Rubik's Cube, which are the pieces that make up a 1x2x3 block on the left-lower part of the cube. For more background, FB is the first step in the Roux speedsolving method, and a FB solver is valuable in helping Roux speedsolvers improve their solutions.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1118,"value":"md`### Step 6a: Reasoning with facelets again\nTo make our solver reasonably fast, \nwe should decide on a model, one where cube moves can be quickly performed.\n\nThe geometric cube looks like a bad candidate because, well, performing rotations on 3d points seems rather inefficient at encoding information. The piece cube can be potentially fast but we haven't touched on that yet. \n\nSo the question becomes, can the facelet cube beat the geometric cube at performing moves? If so, we can settle on that for now. Let's start by converting the geometric moves to the facelet cube, borrowing the same conversion that we wrote when we were visualizing geometric cubes in Step 4. \n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1165,"value":"gcube_to_fcube_idx = {\n // URFDLB\n let map = {}\n let repr = (vec3) => vec3.x + \",\" + vec3.y + \",\" + vec3.z\n let work = (rot, idx) => {\n for (let z of [-2, 0, 2]) {\n for (let x of [-2, 0, 2]) {\n let pos = apply_gmoves([create_sticker(new Vec(x, 3, z))], rot)[0].pos\n map[repr(pos)] = idx++\n }\n }\n }\n\n let face_rotations = [\"\", \"x' y'\", \"x'\", \"x2\", \"x' y\", \"x' y2\"]\n face_rotations.forEach( (rot, i) => work(rot, i * 9) )\n return (vec) => map[repr(vec)] \n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1174,"value":"md`Recall that a facelet move is a permutation i.e. a list of \\`(src_idx, dst_idx)\\` pairs.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1152,"value":"// name, axis, angle, predicate\n// we take a solved cube, apply gmove, convert it to scube, and analyze the changes.\nconvert_gmove_to_fmove = (gmove) => apply_gmove(solved_gcube, gmove).map( s => \n [gcube_to_fcube_idx(s.dst), gcube_to_fcube_idx(s.pos)] ).filter( ([x, y]) => x !== y) ","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1518,"value":"md`We can verify its correctness by converting the U move and comparing it to our manually defined \\`u_move\\`. `","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1510,"value":"convert_gmove_to_fmove(gmoves[\"U\"]).sort().toString() === u_move.sort().toString() ","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1235,"value":"md` ### A surprising easy conversion\nNow let's map our all \\`gmoves\\` from our constructed \"library of moves\" to the facelet level. As we can see, thanks to all the infrastructure we've written, transferring move definitions between models is surprisingly easy. `","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1181,"value":"fmoves = Object.fromEntries(\n Object.entries(gmoves).map( ([k, v]) => [k, convert_gmove_to_fmove(v)] ) )","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1949,"value":"JSON.stringify(fmoves)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1931,"value":"html`

\n Tips for building your own solver: \n
\nThe array above (fmoves) is actually ALL you need to jump-start your own facelet based model! You can skip the geometric modeling part, and just copy over this definition array to get your solver working! (or maybe just a few base moves like U, x and y, and compose the rest on your own) \n

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1288,"value":"md`Finally, let's define the analogous functions for applying the moves: `","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1204,"value":"apply_fmoves = (cube, moves) => \n moves.trim().split(/ +/).filter(s => s).map(m => fmoves[m]).reduce( apply_move, cube )","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1208,"value":"vis(apply_fmoves(solved_cube, \"M' E2 M E2\"))","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1251,"value":"md`#### How much speed have we gained\nNow it's time to test out our hypothesis: it is faster to perform moves on facelet cube compared to the geometric cube`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1320,"value":"viewof run_perf = wait_til_button(\"Click to Run Tests\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1212,"value":"{\n run_perf;\n let n_sample = 100000;\n let desc = \"100k\"\n let t = Date.now()\n let cube = solved_cube\n let move = fmoves[\"R\"];\n for (let i = 0; i < n_sample; i++) {\n cube = apply_move(cube, move)\n }\n let s1 = (Date.now() - t) \n \n\n t = Date.now()\n cube = solved_gcube\n move = gmoves[\"R\"]\n for (let i = 0; i < n_sample; i++) {\n cube = apply_gmove(cube, move)\n }\n let s2 = (Date.now() - t)\n \n let str = md`\n| Model under test | Time | Moves (million) per sec |\n|:---:|:---:|:---:|\n| facelet, 100k | ${s1}ms | ${ (1000 / s1 / 10).toFixed(2)} |\n| geometric, 100k | ${s2}ms | ${ (1000 / s2 / 10).toFixed(2)} |\n\n `\n //let str = [\"Result\", \"=\".repeat(20), s1, s2].join(\"\\n\")\n return str\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1157,"value":"md`### Step 6b: Defining the solver\n\nA solver is made up of two things: the definitions for *what* to solve, and the algorithms for *how* to solve it. Let's focus on the definitions for now. \n\nThe solver definition takes among others, two things:\n the *candidate moves* it can apply to each state,\n and the *condition* at which it considers a state solved.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1883,"value":"create_simple_solver = (is_solved, candidate_moves) => ({ is_solved, moves: candidate_moves })","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1987,"value":"md`For First Block, the solved condition is simply that the colors on the relevant facelets all match with the target color. The target facelets are shown below.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2031,"value":"fb_pieces = [S(\"L\",4),S(\"L\",5),S(\"L\",6),S(\"L\",7),S(\"L\",8),S(\"L\",9),\n S(\"F\",4),S(\"F\",7),S(\"B\",6),S(\"B\",9),S(\"D\",1),S(\"D\",4),S(\"D\",7)]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2039,"value":"vis( (() => { const fcube = [...\"X\".repeat(54)]; fb_pieces.map(idx => fcube[idx] = \"URFDLB\"[ 0 | (idx / 9) ]); return fcube }) () )","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1887,"value":"fb_is_solved = {\n const fb_faces = fb_pieces.map(idx => \"URFDLB\"[ Math.floor(idx / 9) ] )\n return (fcube) => {\n for (let i = 0; i < fb_pieces.length; i++) {\n if (fcube[fb_pieces[i]] !== fb_faces[i] ) return false; // early return for performance\n }\n return true;\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1993,"value":"md`As for moves, the First Block stage is usually solved under STM (Slice Turn Metric), which considers the following 27 moves as the elementary moves:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1895,"value":"stm_moves = [...\"UDFBLRMES\"].map(m => [m, m + \"'\", m + \"2\"]).flat()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1905,"value":"fb_simple_solver = create_simple_solver(fb_is_solved, stm_moves)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2000,"value":"md`### Step 6c: The algorithm -- a simple DFS implementation`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2013,"value":"md`Now that we have the solver definition, let's write the logic that carries out the solving process. We implement a very slow but simple DFS algorithm here. Later, we'll show how to extend it to advanced algorithms like IDA*, which is basically a clever variation.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2023,"value":"md`A DFS algorithm takes a state and keeps searching down the tree until it hits the depth limit. It will guarantee to find a solution where \\`depth <= depth_limit\\`, given that one exists.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1333,"value":"function solve_dfs(solver, cube, solution, depth_remaining) {\n if (solver.is_solved(cube)) return solution.trim()\n if (depth_remaining === 0) return null\n for (const move of solver.moves) {\n let result = solve_dfs( \n solver, \n apply_move(cube, fmoves[move]), \n solution + \" \" + move, \n depth_remaining - 1\n )\n if (result !== null) return result\n }\n return null\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2068,"value":"scramble_dfs = \"U R2 B L D\"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2027,"value":"md`Let's test it out! If we scramble the cube with \\`${scramble_dfs}\\`, we'd have a cube that looks like this: `","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2053,"value":"vis(apply_fmoves(solved_cube, scramble_dfs))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2058,"value":"md`The solution must be shorter than the scramble, because the starting moves \\`U R2\\` doesn't affect the FB facelets. Let's run the dfs and see if it can find a 3 move solution: `","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1916,"value":"solution_dfs = solve_dfs(fb_simple_solver, apply_fmoves(solved_cube, scramble_dfs), [], 3)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2067,"value":"vis(apply_fmoves(solved_cube, scramble_dfs + \" \" + solution_dfs))","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2090,"value":"md`Nice! Our DFS algorithm works! Feel free to edit \\`scramble_dfs\\` to see if it can handle other cases. `","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2101,"value":"md`### Step 6d: Ensuring shortest solutions with IDDFS\nOne small gotcha here is that the DFS solver only returns a solution \\` <= depth_limit \\`, but NOT necessarily the shortest solution within the depth range. For example, if we scramble with \\`L\\` and search with depth 3, due to the ordering of the \\`move_candidates\\`, the DFS will try solution that starts with U layer moves first, and settle on the first solution it finds:\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2110,"value":"solve_dfs(fb_simple_solver, apply_fmoves(solved_cube, \"L\"), [], 3)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2124,"value":"md`Luckily there's a simple fix: let's increment the depth limit by one each time. For each depth limit, we'll restart the DFS, and we break when DFS first returns a solution at a given depth. This way, we'll make sure DFS always returns the shortest solution. This is called **Iteratively Deepening DFS** (IDDFS). \n\nWhile it seems that our modified version is repeatedly searching old states when it restarts an iteration at a new depth, this redundancy is actually fine -- because asymtotically the bulk of the work always happens at the deepest layer, which is fresh (i.e. different) at each iteration. Therefore it has roughly the same runtime as BFS, with the advantage being it is memoryless -- so it can go on for much longer without worrying about blowing up the momry.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2123,"value":"function solve_iddfs(solver, cube, depth_limit) {\n for (let depth = 0; depth <= depth_limit; depth++) {\n let solution = solve_dfs(solver, cube, [], depth)\n if (solution !== null) return solution\n }\n return null\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2132,"value":"md`Now if we try again, the issue will be resolved:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2137,"value":"solve_iddfs(fb_simple_solver, apply_fmoves(solved_cube, \"L\"), 3)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2146,"value":"md`Whew. We finally good now! Well, one last thing, the DFS is actually slow! It has to explore 27^D solutions for a depth of D, many of which are pretty far away from being a solution, or producing identical states as far as First Block is concerned. Can we guide the DFS solver away from these bad states? Turns out we can, and this is how most (competent) solvers are written : with a smart **pruning** procedure. \n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2159,"value":"md`## Step 7: Speeding up the solver with pruning\nIn search problems, **pruning** (lit. cutting of branches) is a way to tell the solver whether a state is impossible to yield a solution for. For example, if we have a table listing all cube states where First Block will take at least 3 moves to solve, then when the remaining depth is 2, we can consult this table, and if the answer is YES, we can end our search early knowing that even if we explored all states reachable from that state in 2 steps, none of them will work. By not visiting unfruitful states, we can save a lot of time. \n\nIn fact, this is exactly how we're going to build our pruning table! We will work backwards, starting from the solved state and make a move, to generate all cases 1 move away from solved, and write them down. Then starting from these states, we'll make another move, to generate all cases 2 moves away from solved, and so on. And we'll go on until the table becomes too large to conveniently store in memory. \n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2385,"value":"md`### Step 7a: Preparations -- reasoning with a masked cube`","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2201,"value":"md`We use a variant of the facelet cube here: instead of associating each indexed position with a face color, we associate it with the target index. We'll call this the **indexed facelet cube (\\`ifcube\\`)**. Don't worry, you can forget about it soon --- it is only useful so far as it paves the way for a **masked cube**.\n\nNote that we can still use \\`apply_fmoves\\` and the fmoves definitions because they describe permutations that are agnostic to the content stored at each index. The function below shows how the conversion works:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2392,"value":"ifcube_idx_to_fcube_face = (idx) => \"URFDLB\"[Math.floor(idx / 9)]","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2204,"value":"solved_ifcube = Array(54).fill().map( (_, i) => i) ","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3769,"value":"create_fcube = (moves) => apply_fmoves(solved_cube, moves)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2770,"value":"create_ifcube = (moves) => apply_fmoves(solved_ifcube, moves)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2410,"value":"md`\nThe indexed facelet cube offers one extra functionality: whereas the regular facelet cube describes the color at each position, the \\`ifcube\\` describes the exact facelet. This way, we can take any cube and **extract the pieces we're interested in** (by their target index). For instance, a mask for FB solver would leave the FB pieces as is, while painting the rest of the cube grey. \n\n\\`get_masked_cube\\` does exactly that. It takes a mask (i.e. indices of pieces of interest ), and converts the ifcube back to a fcube while coloring the unmasked pieces gray (with a special X face). \n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2196,"value":"mask_cube = (ifcube, mask) => \n [...ifcube].map(idx => mask.includes(idx) ? ifcube_idx_to_fcube_face(idx) : \"X\").join(\"\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2214,"value":"vis1([\n [mask_cube(create_ifcube(\"D2 R2\"), solved_ifcube), \"unmasked\"],\n [mask_cube(create_ifcube(\"D2 R2\"), fb_pieces), \"masked by FB\"]\n])","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2445,"value":"md` In fact, as far as our partial solving goes, the masked facelets is all that matters! Now that we're done converting an \\`ifcube\\` to a masked \\`fcube\\`, we can keep working at this level throughout the entirety of our pruning and solving process. Essentially, **masked cubes** gives us a way to group together states that are identical except for the irrelevant pieces. This way we'll be able to explore states much more efficiently during searching. \n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2467,"value":"md`### Step 7b: Generating the pruning table\n\nNow we want to generate a pruning table of depth **k**. That is, find all the states that takes up to **k** moves to solve. \nThe code below shows how the table is generated. \\`frontier\\` describes all states on the current depth level, and we generate them by expanding from the previous frontier by making a move. Whenever we discover a new state that hasn't been added in the pruning table, we add it to the \\`frontier\\` and record its depth in the pruning table. `","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2555,"value":"viewof fb_pruning_depth = slider({\n min: 0, \n max: 5, \n step: 1, \n value: 4, \n title: \"FB Pruning Depth\", \n description: \"Feel free to adjust the depth. Depth = 5 could take a while though.\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3164,"value":"pruning_stats(fb_pruning_table, \"FB\", true)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3105,"value":"gen_pruning_table = (solved_states, depth, moveset) => { \n let pruning_table = {}\n let previous_frontier = solved_states\n solved_states.forEach(s => pruning_table[s] = 0)\n \n for (let i = 1; i <= depth; i++) {\n const frontier = []\n for (let state of previous_frontier) {\n for (let move of moveset) {\n let new_state = apply_move(state, fmoves[move]).join(\"\")\n if (!pruning_table.hasOwnProperty(new_state)) {\n pruning_table[new_state] = i\n frontier.push(new_state)\n }\n }\n }\n previous_frontier = [...frontier]\n }\n return pruning_table\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2470,"value":"fb_pruning_table = gen_pruning_table([mask_cube(solved_ifcube, fb_pieces)], fb_pruning_depth, moveset.htmrwm)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3161,"value":"pruning_stats = (table, desc, verbose) => {\n const depth_count = []\n let max_depth = 0\n for (const value of Object.values(table)) {\n depth_count[value] = depth_count[value] + 1 || 1;\n max_depth = Math.max(max_depth, value)\n }\n if (verbose) {\n let rows = [\"| Depth | State |\", \"|:---:|:---:|\"]\n for (let i = 0; i <= max_depth; i++) {\n const row = \"| \" + [i, depth_count[i]].join(\" | \") + \" |\"\n rows.push(row)\n }\n rows.push(`| total | ${Object.keys(table).length} |`)\n return md`${desc} pruning table generated: \\n\\n ${rows.join(\"\\n\")}\n `\n }\n else {\n return md`✅ ${desc} pruning table generated: Depth = ${max_depth}, Total states = ${Object.keys(table).length}`\n }\n \n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2498,"value":"md`### Step 7c: Applying pruning in our DFS algorithm\nAlright. We've got our pruning table nicely in place.\nIt's time to invoke it in our DFS. Remember, the idea is that:\n

\n If we're at a state where we have **K** steps left, and we know for sure the state takes ** > K ** steps to solve, then we abandon the state immediately.\n

\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2532,"value":"md`First let's update our solver definition to include the pruning table and pruning depth (i.e. max depth of our pruning table): if a state exists in the pruning table, we take its depth there. If not, we will **lower bound** its depth by \\`pruning_depth + 1\\`. Note that our idea is built around inequalities, so that even when a state is NOT in the pruning table, lower bound estimates can still be useful. `","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2534,"value":"create_solver = (is_solved, candidate_moves, pruning_table, pruning_depth) => ({ pruning_table, pruning_depth, is_solved, moves: candidate_moves })","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2240,"value":"fb_solver = create_solver(fb_is_solved, moveset.htmrwm, fb_pruning_table, fb_pruning_depth)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2546,"value":"md`Then let's incorporate pruning into our DFS, along with some small optimizations:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2173,"value":"function solve_dfs_with_pruning(solver, cube, solution, depth_remaining) {\n const cube_str = Array.isArray(cube) ? cube.join(\"\") : cube\n if (solver.is_solved(cube_str)) return solution.join(\" \")\n // Pruning\n let lower_bound = solver.pruning_table[cube_str]\n if (lower_bound === undefined) lower_bound = solver.pruning_depth + 1\n if (lower_bound > depth_remaining) \n return null\n \n for (const move of solver.moves) {\n if (solution.length && move[0] === solution[solution.length - 1][0]) \n continue; // aside: never use the same layer in consecutive moves\n solution.push(move)\n let result = solve_dfs_with_pruning( solver, apply_move(cube, fmoves[move]), solution, depth_remaining - 1)\n if (result !== null) return result\n solution.pop()\n }\n return null\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2573,"value":"md`And of course, update the IDDFS, which in case you forget, acts as the frontend to our solver and calls DFS incrementally to ensure optimality. Slight changes to our interface as well : since it works with masked cubes, it now takes a masked \\`fcube \\` as input. ` ","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2249,"value":"function solve_iddfs2(solver, masked_cube, depth_limit) {\n for (let depth = 0; depth <= depth_limit; depth++) {\n let solution = solve_dfs_with_pruning(solver, masked_cube, [], depth)\n if (solution !== null) return solution\n }\n return null\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2578,"value":"md`### Step 7d: Building an interactive solver\nWe have built a pruning-empowered solver that is a huge improvement from before. But how fast is it? It's time to showcase this with an interactive solver.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2589,"value":"gen_scramble = () => {\n let pprev = -1, prev = -1\n let scramble = []\n for (let i = 0; i < 30; i++) {\n let layer;\n do {\n layer = 0 | (Math.random() * 6);\n } while (layer === prev || (layer % 3 === prev % 3 && layer === pprev) ); \n scramble.push(\"URFDLB\"[layer] + [\"2\", \"'\", \"\"][0 | Math.random() * 3])\n pprev = prev\n prev = layer\n }\n return scramble.join(\" \")\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2299,"value":"viewof fb_scramble = {\n let scr = scramble_interface(\"fb\")\n let view = html`

\n First Block Solver

${scr}

\n\n

`\n scr.addEventListener(\"input\", () => { view.value = scr.value; })\n return view\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2251,"value":"fb_solution = solve_iddfs2(fb_solver, mask_cube(create_ifcube(fb_scramble), fb_pieces), 10)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2304,"value":"vis1 = (cubes_with_comment) => {\n return md`\n

\n ${cubes_with_comment.map( ([cube, comment]) => html`\n

${vis(cube)}

${comment}

\n `)}\n

`\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3343,"value":"vis1([ \n [apply_fmoves(solved_cube, fb_scramble), \"scrambled cube\"],\n [mask_cube(create_ifcube(fb_scramble), fb_pieces) , \"scrambled cube (masked)\"],\n [mask_cube(create_ifcube(fb_scramble+ \" \" + fb_solution), fb_pieces) , \"scramble + solution\"],\n])","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3316,"value":"md`[Click here to view it on alg.cubing.net](${`https://alg.cubing.net/?alg=${fb_solution}&setup=${fb_scramble})`}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2312,"value":"html`

\n \nPerformant and correct, our FB solver is fully working now! \n\n\n

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3041,"value":"md`### Step 7e: Creating more solvers on the fly\nLet's briefly review. We first created a **solver definition** language that lets us define any solver with three things -- a condition for solved, a set of moves, and a pruning table. Then we've created a general DFS algorithm that takes a solver definition and solves any given cube. \n\nBecause of how generic our interface is, we can easily reuse the same code to create more solvers. We'll showcase this by building a **cross** solver and an **LSE** solver, both popular substeps in speedsolving.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3146,"value":"moveset = ({\n mu : [\"M\",\"M'\",\"M2\",\"U\",\"U'\",\"U2\"],\n htm : [...\"UDFBLR\"].map(m => [m, m + \"'\", m + \"2\"]).flat(),\n htmrwm : [...\"UDFBrRM\"].map(m => [m, m + \"'\", m + \"2\"]).flat(),\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3270,"value":"pieces = ({ \n cross: [S(\"D\",2),S(\"D\",4),S(\"D\",6),S(\"D\",8), S(\"L\",8),S(\"R\",8),S(\"F\",8),S(\"B\",8)],\n lse: [S(\"U\",2),S(\"U\",4),S(\"U\",6),S(\"U\",8),\n S(\"L\",2),S(\"R\",2),S(\"F\",2),S(\"F\",8),\n S(\"B\",2),S(\"B\",8),S(\"D\",2),S(\"D\",8), // edge pieces\n S(\"U\",1),S(\"U\",5)]// extra pieces to make sure corner and centers are solved\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3120,"value":"cross_solver = {\n let depth = 4\n let table = gen_pruning_table([mask_cube(solved_ifcube, pieces.cross)], depth, moveset.htm)\n let solver = create_solver(x => table[x] === 0, moveset.htm, table, depth)\n return solver\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3130,"value":"lse_solver = {\n let depth = 8\n let table = gen_pruning_table([mask_cube(solved_ifcube, pieces.lse)], depth, moveset.mu)\n let solver = create_solver(x => table[x] === 0, moveset.mu, table, depth)\n return solver\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3445,"value":"viewof misc_solver_select = {\n let select = html`