Rubyik's Cube
0 views
Formal Metadata
Title 
Rubyik's Cube

Title of Series  
Number of Parts 
69

Author 

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 noncommercial 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!

00:00
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
02:33
Strategy game
Repository (publishing)
Linker (computing)
Projective plane
Planning
Machine code
Associative property
03:10
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)
04:36
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
08:19
Multiplication sign
Table (information)
Permutation
Number
Maxima and minima
Strategy game
Cube
Natural number
Term (mathematics)
Central processing unit
Computerassisted 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
11:15
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
17:11
Commutative property
Computer programming
Readonly 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)
Depthfirst search
Line (geometry)
Network topology
Cube
Phase transition
Order (biology)
Right angle
Game theory
Whiteboard
21:28
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)
24:52
Projective plane
Similarity (geometry)
Right angle
2 (number)
26:20
Area
Implementation
Algorithm
Java applet
Robot
Cube
Authorization
Queue (abstract data type)
Auto mechanic
Machine code
Subtraction
Exception handling
27:10
Suite (music)
Context awareness
Group action
Implementation
Algorithm
State of matter
Decision theory
Robot
Translation (relic)
Realtime 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
29:59
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)
00:00
the the the the
00:06
the the the the the right a door and it
00:14
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 fullstack 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 schoolage 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
02:35
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
02:50
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
03:12
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
03:23
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 lefthand 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 threeway 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
04:38
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
05:39
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 90degree 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
08:20
cube so really over 3 strategies here brute force what's coming notice he thought were layer by layer and finally casinos this twophase algorithm so
08:33
while we just bruteforce 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 F35 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
11:18
nogo 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 layerbylayer 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
14:19
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
17:19
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 firstphase 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 layerbylayer 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
18:30
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 tictactoe 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 everpresent 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 breadthfirst Search and depthfirst Search breadthfirst 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 depthfirst search so depthfirst 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 tictactoe 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 tradeoff 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 depthfirst 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 breadthfirst search we hit the solution move on the 5th leaf that's iterated here the free doing a depthfirst 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
21:30
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
24:25
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
25:17
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
26:16
chicken right so it's a similar neck steps in the project so I based the initial
26:23
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
27:07
that and so that
27:11
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 lowlevel 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
29:18
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
30:01
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 3Dprint 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 finegrained 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 mininetwork 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