Rubyik's Cube

0 views

Formal Metadata

Title
Rubyik's Cube
Title of Series
Number of Parts
69
Author
Brunk, Stafford
License
CC Attribution - ShareAlike 3.0 Unported:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal and non-commercial purpose as long as the work is attributed to the author in the manner specified by the author or licensor and the work or content is shared also in adapted form only under the conditions of this license.
Identifiers
Publisher
Confreaks, LLC
Release Date
2017
Language
English

Content Metadata

Subject Area
Abstract
The Rubik's Cube is one of the world's most recognizable puzzles. Knowing how to solve a scrambled cube can almost be called a badge of honor. While there are a multitude of books, articles, and apps on how to solve a cube as a human, what does it take to have a computer solve the problem? This talk will dive into exactly that question. We'll start with an overview of Rubik's Cube algorithms, move onto the logistics of implementing these algorithms, and finish up with some real examples of using Ruby to solve a Rubik's Cube!
Loading...
Point (geometry) Computer programming Mountain pass Multiplication sign Robot Complete metric space XML Computer Root Cube Internetworking Energy level Subtraction Social class Area Intelligent Network Product (category theory) Projective plane Expert system Skewness Set (mathematics) Line (geometry) Cube Speech synthesis Right angle Quicksort
Strategy game Repository (publishing) Linker (computing) Projective plane Planning Machine code Associative property
Rhytidectomy Greatest element Touchscreen Orientation (vector space) Greatest element Total S.A. Number Category of being Type theory Graph coloring Cube Term (mathematics) Cube Queue (abstract data type)
Rotation State of matter Orientation (vector space) Direction (geometry) Mereology Permutation Number Positional notation Cube Dedekind cut Term (mathematics) Kinematics Core dump Queue (abstract data type) Square number Position operator Theory of relativity Cartesian coordinate system Degree (graph theory) Positional notation Lattice (order) Graph coloring Cube Orientation (vector space) Pattern language Data type Resultant
Multiplication sign Table (information) Permutation Number Maxima and minima Strategy game Cube Natural number Term (mathematics) Central processing unit Computer-assisted translation Subtraction God Algorithm Spacetime Theory of relativity Forcing (mathematics) Optimization problem Bound state Computer Computer Table (information) Number God Arithmetic mean Data storage device Cube Order (biology) Right angle Central processing unit
Point (geometry) Random number Greatest element Rotation Implementation Multiplication sign Orientation (vector space) Control flow Mereology Computer Permutation Web 2.0 Strategy game Cube Feasibility study String (computer science) Queue (abstract data type) Position operator Metropolitan area network Algorithm Information Optimization problem Projective plane Set (mathematics) Computer Entire function Symbol table Graph coloring Visualization (computer graphics) Data storage device Cube Order (biology) Website Right angle Routing Force
Commutative property Computer programming Read-only memory Algorithm State of matter Multiplication sign Combinational logic Number Subset Permutation Maxima and minima Root Cube Phase transition Network topology Queue (abstract data type) Energy level Contrast (vision) Subtraction 5 (number) Game theory God Pairwise comparison Optimization problem Instance (computer science) Depth-first search Line (geometry) Network topology Cube Phase transition Order (biology) Right angle Game theory Whiteboard
Point (geometry) Group action Implementation Algorithm State of matter Length Multiplication sign Mereology Total S.A. Subset Number Goodness of fit Iteration Phase transition Representation (politics) Series (mathematics) Subtraction Position operator God Scalable Coherent Interface Addition Algorithm Cellular automaton Optimization problem Counting Total S.A. Bit Instance (computer science) Table (information) Category of being Arithmetic mean Network topology Cube Phase transition Order (biology) Right angle Mathematical optimization Mathematical optimization Row (database)
Projective plane Similarity (geometry) Right angle 2 (number)
Area Implementation Algorithm Java applet Robot Cube Authorization Queue (abstract data type) Auto mechanic Machine code Subtraction Exception handling
Suite (music) Context awareness Group action Implementation Algorithm State of matter Decision theory Robot Translation (relic) Real-time operating system Streaming media Machine code Revision control Cube Linker (computing) Interpreter (computing) Symmetry (physics) Videoconferencing Software testing Code refactoring Data structure Lie group Implementation Subtraction Task (computing) Condition number Computer icon Boss Corporation Algorithm Process (computing) Block (periodic table) Keyboard shortcut Instance (computer science) Machine code Benchmark Functional (mathematics) Open set Loop (music) Network topology Graph coloring Personal digital assistant Cube Interpreter (computing) Object (grammar) Mathematical optimization
Computer file Chatterbot Cellular automaton Robot Projective plane Materialization (paranormal) Interface (computing) Auto mechanic Functional (mathematics) Computer Computer Degree (graph theory) Cube String (computer science) Bus (computing) Hydraulic motor Right angle Library (computing) Vulnerability (computing)
the the the the
the the the the the right a door and it
started this level but no 1st time speaking Arabic offers and speaking in general so I have I a high higher so this is really a skew my name is Stafford Brown and you can find me around the internet and handling under 21 and I work as a full-stack suffer engineer at Guild education in denver colorado and where start up a striving to help working adults go back to school in an informal manner well we don't do however is pretty much anything to do with really excuse so why why did this project and so probably about a year ago I my wife and I were having dinner with their neighbors and there and middle school-age daughter came over and she was super and about a Rubik's Cube solving robot that she'd seen a museum exhibit and she then working on learning assault cubes of herself for the past few months times you just targeting programming classes in schools which is very interested in how this thing actually worked and so I started thinking about the problem and I was like well I mean maybe I can figure out how to build a Rubik's Cube robot and sit down with her and explain the concepts and and go over the differences between how human approaches to solve the problem of solving Rubik's cubes and how computer would do that but there 1 problem though I was not an expert in these areas I wasn't even an amateur and I had never even attempted to solve a Rubik's Cube before I was kind of I had some robotics background some design background but I had not done anything along these lines before so I I was a complete junior Cuba curious whether people rescue CUNY call themselves solving cubes so this point and we all must be thinking how can this guy even solve a Rubik's Cube no no I can't and but really can't and wants to learn the ins and outs of solving a Rubik's Cube by hand on this products is given me a lot better idea around the far animals around the roots Q problem set and but is not given me some sort of magical boost in the ability to do it myself IT he like to follow along at
all all the code of an association links others is posted under the Rubik's Cube a repository of I get have account that Google l just takes the same place and yes so it's the gun so this is the general
roadmap have 1st do is go over some of the basics like that terminology in the notation and if you're a seasoned Cuba my apologies as in the pretty basic for you and the next step is really go look at some of the strategies for solving a Q and finally we'll talk about how what my plans for the next steps on this project as the 1st
of this terminology and there's pretty much 3 basic terms the the familiar with here are faced a facelift in a cube what's so 1st up is a face of
face it's pretty much the individual size of the Q faces are denoted in reference to whichever faces closest to you independent of color I listen says the yellow side of the cube is the 1 that's closest to you so it is the front face from there you can see that the remaining faces on the Q red is the right face left the oranges the let's face blue is the top or upper face screen is the bottom or down face and white is the back face this is a broken up into 9 individual facelets these of basically the individual colored stickers in the queue faces a number from 1 to 9 starting in the upper left-hand corner and wrapping around as you go down you what you wear represents the individual colored pieces of the Rubik's cube so these are the cubes that make up you there are 26 total Q what's the three-way 3 Rubik's they're broken up into 3 categories corners edges and centers you can see the quantity was highlighted here and pink quantity was are exactly that the cubes in the corners of the Rubik's Cube as each corner at you what is the intersection of 3 faces it has 3 possible orientations was take a look at the URIs cornered you work as an example
take a look at where the yellow red and blue sides meet your member of Murphy's terminology this is the intersection of the U R and f faces because this is the your corner there are 3 different orientations displayed here you can see in individual orientation is essentially a simple rotation of the cupola at each corner Q What can be oriented along the same pattern to produce all possible orientations of the cube corners so a few twists but 1 corner we have twisted here and another corners twisted that's another permutation of the queue I no that while the quantity was themselves can be placed into these orientations you can't necessarily reach all these orientations through legal cube moves meeting without actually taking the Cuban rotating it yourself through normal turning of the cube now the next type of Q. What is an edge to edge Q was represent were 2 faces meet again the highlighted here and paint their took 12 total edges of a three referee Rubik's Cube each edge has 2 possible orientations here we can see the 2 different
orientations of the FIR edge would by corners a diver orientation is simply a rotation of the cube slits possible values also like corners permutations of the 12 edges in the cube equal all possible edge orientations finally we have you puts in 3 by 3 cube 6 center cubits as a synergy was only ever touch 1 face there's no orientation worry about they only have 1 where most important things to remember about the center Q What is that its position is essentially fixed all corner an edge cubits move around the centers so the centers are the axis of rotation for each individual face of the cube now the were familiar with the parts that you need to go over how you do know movements on a cue for that here is of adopted annotation of relative movement developed by MAP Professor David saying master will only be talking about the basic movements here your interest in the more advanced you movements I recommend checking out Ruegg stuff comes article on this topic it's a defined in terms of quarter rotations in relation to 1 of the Cubs' faces each move that has an optional modifier that denotes the type of movement I'll be performed in this example will use the front or face as that which is being moved a single letter denotes a clockwise quarter turn so here you can see that the face has gone from its original solve state having all colors rotated by 90 degrees clockwise there's no modifier required for this type of new here we can see an example of a modifier work 2 designates 2 90-degree turns in the clockwise direction is possible within this notation to specify additional higher numbers this is really used since it overlaps other notations for example and for annotation would be equivalent to know movement as and you do for core rotations your back to where you started and F 5 notation is equivalent to enough attention f prime denotes a quarter turn in the counterclockwise direction you know so this is the same as if he'd specified and F 3 rotation individual face movements are chained together to create movement strains take for example the move mystring here prime you 2 we start with solve cube on the left exit you a clockwise turn of the face a counterclockwise turn of the a face and to clockwise turns of the you face the end result is shown on the far right and I'm pretty sure that's the correct here orientation but I drew those by hand in Illustrator so forgive me if I got some squares of the place alright so let's move on to actually solving the
cube so really over 3 strategies here brute force what's coming notice he thought were layer by layer and finally casinos this two-phase algorithm so
while we just brute-force the solution to this it's a 3 by 3 cube right relation take is that well they're actually 43 quintillion possible permutations of Arix Q more precisely 43 quintillion 250 quadrillion 3 trillion 700 274 billion 489 million 856 thousand flat permutations that is a huge number of computing have us all that many permutations would take you years which is exactly where researchers did the upper and lower bounds on the number of moves the required to solve a Rubik's cube is known as God's number the term comes from the idea that were God to be given a scrambled Rubik's Cube he would always solve it and the most optimal way the delta 1st thought to be roughly 17 on the lower end an 80 high and meaning researchers biotech in minimum 17 there's a maximum of 80 moves when they 1st began the research this in nineteen 80 it was until 2010 thanks to the efforts of Thomas' the Herbert Kociemba morally Davidson and John Deatherage that the upper and lower bounds were converged into a single number this number was reached the F-35 CPU years of computing time donated by Google so that's just how long it took them to compute that problem space and that number is 20 all scramble cubes can be solved in a maximum of 20 moves for the most optimal solution researchers discovered this by computing all possible solutions to the Cuban making sure that none of them required more than 20 know that they didn't actually have to compute all 43 quadrillion different solutions in order to reach this conclusion do the nature of how would excuse move some permutations are considered symmetrical to each other they have like this if I to the Rubik's Cube in hell that up to you and then I turned it over the solutions all that cube is exactly the same it's just a different face is on the face those are considered per assymetrical permutations so it took 35 CPU years to compute all the news that means we can just have a look up table right just be like a giant Hashan we can just get it now and the like superfast well it would take a lot of space even if you assume 1 byte for solutions during which is completely unreasonable it would take 43 thousand petabytes just to store everything I'm sure you've got much better things to store than Rubik's Cube movement strengths like a shiny new collection of airdropped cat pictures from really cost so the brute force method is a
no-go random movements were taken infeasible man of computation time Gray Computing all possible movements require a ton of storage much less how long it would take you to actually perform a look up on a dataset that science will have to use other strategies to solve the cube but 1st let's ask how do humans Solarix Q the answer is that break it down into smaller parts to use example of a beginner strategy for solving reduced Q. that's known as the layer-by-layer strategy this strategy is part of a set of strategies of fall under the sea fight genre see thought stands for cross 1st you layers orients position so basically you're starting from the top of the Rubik's Cube solving that layer solving the middle layer of solving the bottom layer this jonna is popular for beginners and for advanced IQ solving techniques the sound speed so must be giving solutions that use this and in some basic computer algorithms that use this and the idea of the site and note that I'm going to go through the strategy as you saw that as a human but I'm not going to go into the strategy in depth and size you'd like more information on this again go to room stuck common they have a great article on a beginner strategy for solving the queue so the 1st step make a white crosses the top you can see that the edges in the centers are also color aligned here but but the corners and the position so marks the complete and solving of the 1st layer you can see that the orange and agree assault centers of stone position and Nexus to solve the 2nd layer and here I've actually flip the queue over and this is in preparation for the next step but the 1st layer would be on the bottom the 2nd layer is in the middle and notice how the yellow Q is in the center on the bottom sulfur yellow across I will put the edges and the place you know so this is closely mirroring what we did and the original in the 1st couple of steps and now narrative but the corners into position so this is called orienting the corners and so there roughly where they need to be but they're not actually solved and finally we solve for the yellow corners that's so we've solve Q of this seems pretty good right broken it down into smaller pieces it's a pretty straightforward way of doing things the remember that each step is a different permutation of the Q were I computer solving this I would have to compute what moves are required to go from point a to point B in the most optimal solution and I have to do that for all 7 steps that illustrate this I have a small them this is the
Rubik's Cube web 5 thousand as so really generate a random you as an that really really fast so this is a very naive implementation of this algorithm you can see that it became that was 79 is not too bad some of these are whole cube rotation this a little bit inflated and so this is just to solve the 1st layer so we'll go that run as so you'll notice on with the whites it's actually doing in a slightly different order than I talked through and it's going to be selling the white corners 1st and then it's going to be solving the white edges and it's just a slightly different order performing the same that did not if if to the something going here the exact that's what's repressed with different routes to begin upstairs city but as will go back to having it computes the entire tube solution part of this is the the slider and using to visualize the cube is a project called roof pig it was it's a pretty cool visualization of it's a little finicky on how solution string comes back at Old actually change the sticker colors around so this should actually be of full cube solutions it doesn't spend at the point on this 1 come back to this summer's whichever tickets symbols of OK rights the opponents
so consumers are was created by Herbert Kociemba a German repetition that you may remember was a member of a team that helped discover that God number was 20 and his is made up of 2 phases the 1st phase solves the Cuba into a known state and this allows the 2nd phase to have a considerably smaller subset of moves required to do the final solving just as an example will use of the 1st 2 layers of solution to solve the cube into a given state so in this instance the first-phase finds of the solution to the 1st 2 layers the 2nd phase solves the rest the queue so in our problems that were looking for the most optimal solution of solving the 1st 2 layers and from there were looking for the most often solution to solve the remaining where contrast that to the layer-by-layer solution that we're just looking at which theoretically worked and you can see that you know if guys number is 20 then phase 1 was states 2 should equal a maximum of 20 but even with the the Meyer moves Roeding that we're well above 20 right so in order to solve this
spreading the tree more specifically a game tree with a game tree you might ask if there's anybody who's new programming you may not be familiar with trees at all so let's go over a small example and I think this is a game tree for a tic-tac-toe so as you can see the initial state of the tree is the initial state of the game an empty board that's the root of the tree but each additional depth of the tree or each level down has leaves there's a connected to OneNote above them have those ever-present a new state in the game each edge or a line that connects each leaf corresponds to a move in the game and then each level the tree is considered an additional depth the idea is to search the tree in the final winning state there are 2 general ways of performing the search breadth-first Search and depth-first Search breadth-first Search searches across the tree so they'll search adept 0 then it'll search adept 1 going from left to right that's to by from left to right etc as you can see that as a tree is iterated at each leaf is checked for the Finnish solution define a solution you done you know ought to going further that what the other thing that we have here is a depth-first search so depth-first search means you go all the way down the tree in the left hand side as far as you can go then you start coming back up go back down come back up so you can see that you're going up and down and then you're moving left to right and so the problem with the game tree is that usually all possible permutations of game on possible or highly difficult to build into a tree tic-tac-toe you can probably pretty easily do you can't put 43 quintillion different combinations into a tree in memory so we need to make some sort of heuristic to make our search more efficient I 1 way do that is to limit the depth of the search we know the guys number specifies that all cubes can be solved in a minimum of 20 moves we can then set search to be 20 and limit how deep we have to go into the tree another problem with the gaming tree as we have a set up is that you have to make a trade-off between how close to solve the Rubik's Cube is for example if all you did was performed 1 turn on the cube you expect that solution to be adept the 1 on the tree however if you do a depth-first search it's possible you be waiting quite a long time the comparison in comparison the doing a depth or 1st search it great if we can minimize the trade off so it really breadth-first search we hit the solution move on the 5th leaf that's iterated here the free doing a depth-first search with the go all the way down and up and down as we go across the his have to wait longer extrapolate that out into the Rubik's Cube problem set and it's a big difference in time
we can use a technique called iterative deepening in order to try and hybridize the difference at in depth and breadth 1st search will continue to use the 1st 2 layers as an example so let's say that it requires 15 moves to solve the phase 1 portion of the algorithm and it solves 11 moves to solve the last layer good that is 26 moves in total iterative did deepening essentially allows us to use less optimal solutions for phase 1 and check to see if we can generate a shorter phase 2 so as to take a look at this so you can see the 1st row of the table is optimal 15 lose for phase 1 and then the 11 moves for the remainder of phase 2 for 26 moves then we check well maybe 16 moves in phase 1 generates a shorter phase to maybe 70 18 19 etc. until we had 26 total moves in phase 1 and 0 and face to however hopefully somewhere along the way we find a shorter total so in this instance for 17 phase 1 moves and we get 6 to use for a total of 23 but as an overall more optimal solution when that happens we we start our search with the new total of 23 eventually Werner get to the point where we can find a more optimal solution may be other them times out they be beer depth to search the tree whatever at that point phase 1 will be the full toll move so the bottom row in the table in phase 2 will be 0 and practice normally when you start getting close to this bound for the last few moves that phase 1 a action the 1st couple of news that you actually find in phase 2 I so I had this all relate to consumers to phase out of so instead of using FT well on the 1st 2 layers of this initial state and its phase 1 initial state consumer solves the cube into to a known state G 1 the properties of G 1 mean that all corners and edges are oriented and all middle layer edges are already in the middle layer I still count was I mean in English as so like I said quarters and edges are oriented so they're roughly in position to where they need to be of solve state middle led the layer edges are already in the middle layer meaning that if the 1 end up in the middle layer or the 2nd layer down from the top of the need already be there but maybe not necessarily on the side that discuss they're going in that part the idea around solving to this state is from here only a small subset of moves are required affair solving the Q so from stage 1 you can see that only the moves U D R 2 F 2 L 2 and B 2 will be required to actually move the cube into the cell state at this cube is not speak you were in state g 1 this is just a representation of different edges corners that oriented rights
hopefully this time were a little more likely so we will be using Kociemba sovereign this time I'm I'm sending it to search to a depth of 21 slept 1 what in God's number and the reason for this is that my implementation of consumers are right now need some optimization and 1 additional piece of depth dramatically helps the amount of time it takes to search that sometimes it takes a little bit Kay got
back we had 20 new solutions that that the It's easy that took 14 seconds to compute and sometimes is a lot faster migrate there about 21 lives solution so long as I've seen thus far I implementations 45 seconds some might take a while at sea right
chicken right so it's a similar neck steps in the project so I based the initial
implementation off of a reference Python implementations by a couple of different individuals 1 by the initial author of the algorithm of ordered his private the petition was from his Java implementation and in the 2nd 1 was from Maxim so I use She's chemical build a bunch of different cube solving robots online and is that's a novel ideas on different robot mechanics except on most efficient ways like grabbing and letting go of the queue and the poor the code fairly directly and I converted idiomatic ruby and in areas where I thought it would be fairly low risk and but in general it was kind of high finance light it kind of looks a bit like
that and so that
the as by next task is to try and optimize the code for the really interpreter so 1 thing that this other than makes prolific use of these while loops of that lot while trees in there Rubalcaba loves to tell me that I need to using loop instead however from my eyes low-level testing loop is actually slower than using while true if you remember loop requires a block which creates a new variable context every single time while as looping right there so it's very possible that as I am optimizes algorithm it will not end up being idiomatic ruby and I intend writing some kind of benchmark suite to try and see like what kind of a penalty does idiomatic ruby actually happened this room and another thing I like to put in place a cemetery detection if you remember I talked about that before and basically detecting if I can take a given cute stay and then see if it's been rotate or something like that and try and short circuits some of my searching and some of the algorithm has like the baseline features in place for that is these further fleshed out and there's also in your implementation of coziness algorithm called into the case you can see the get have link there it actually will solve the cube into the initial state of more than 2 G 1 it has a couple of initial states in a couple of different ways of prunes the decision tree I have investigated very deep I actually found out about it only a couple days ago but he become a need to see what kind of optimizations I can pull out of that and so 1 last thing and I definitely mention a robot at the beginning of this talk and I've done action alot of initial work on the robot the boss functionality can boiled into 3 steps read the cube state solved the solution and then solve so in this instance use open the to read the cube state I use consumers algorithm or some modified version of it to compute the solution and then translate them move set into the motor rudiments as you can see a
screenshot here of some the work I've done to read a faceless in open sea than the faceless themselves are being highlighted and their properly detected color and there's still some work to do around dynamically common saying for different lady playing conditions and doing some refactoring I was working pretty well but the only thing that I have not gotten working particularly well is that the open sea the bindings for Ruby do not handle lie video streams of particularly well I'm I think I need to drop to something that's see that's to handle the data structures and aunts translation of every objects is just too slow to do that the video processing in real time for this and we select implemented and the next step is news
consumers our so your cover that and then the last piece is the robot and in translating the movements of strings into some kind of motor movements as so I've been designing the mechanics of the robot already on the get have repository there's an SEL files and those are the file that you 3D-print and around like the cube gripper and how you now 2 years and stuff like that and eventually hoping to have a full build materials up their instructions and for people to build their own bot had a run it etc. and might also start implementing motor functionality I checked the existing projects like the to jam and it stayed don't really implement stepper motors and I need fine-grained motor control IC from turning exactly 90 degrees and stuff and so I'm going to be in the lining up implementing my own whether weak solution and there's already a library up I get have a username called live on the Eee and so this is a USB if the interface to what's called the ITC bus lots of wafer blade embedded stuff to talk to each other I feel like a mini-network basically and It's a C library that's wrapped by using ever fight and it I built up a Construx to be compatible with the existing ITC jam and so eventually I hope to integrate that into a motor control or are you just drop in place and for existing projects instead of using something like a Raspberry Pi you just look up something that it offered cells to use the Porter computer and get the exact same functionality right thanks so I got Thacker in her at my
Loading...
Feedback

Timings

  558 ms - page object

Version

AV-Portal 3.10.1 (444c3c2f7be8b8a4b766f225e37189cd309f0d7f)
hidden