Hacker News new | past | comments | ask | show | jobs | submit login
Self-solving Rubik's Cube (dmm-make.com)
630 points by murkle on Sept 24, 2018 | hide | past | favorite | 103 comments



But is it actually "solving" itself? Or just recording the scramble and playing it back in reverse order? I realize it's an artificial distinction, but if the cube is tracking its state and then running a solve algorithm, that's more interesting (to me) than if it's just popping a stack.

Either way, it's extremely cool.


Looks like it's solving to me. It's taking longer to solve and there's a screenshot of some solving code in the description.

I notice also that it appears to not be able to move the middles sections, so instead it twists the middle and one side and then twists the side back again - so that adds an extra inefficiency.

EDIT if you look at the first video, the first move the solver makes is not the inverse of the last one the player made, so I'm sure it has its own solver. Also, there are pretty standard solver algorithms (I've never looked them up because I don't want to spoil the game for myself but I have a really inefficient one I've figured out myself).


I'm pretty sure it's using some version of Fridrich. It looks like it in the video, and the source code screenshot has a file name, "solve_f2l.cpp", that would appear to be referring to the "first two layers" step, which is usually abbreviated as f2l.

For finding a solution by computer, it has the advantage of being almost completely a rote application of algorithms.


A lot of people have pointed out that solving a cube isn't really a Hard Problem, and that the really interesting thing is the automechanic aspects of it to begin with, but honestly I think it'd actually be harder to make it track the rotations and replay them backwards than to just solve the cube from any static state.

Kinda feel like this is a pretty good example of how solutions to problems can be counterintuitive to people.


Doesn't it need to track the rotations in order to solve it anyway though?


Why? It just needs to record the current position, regardless how it got there.


Yes but the current position of all 6 motors is not enough to determine the state of all 26 cubes. Tracking moves with an encoder for each motor (which you want anyway to ensure you didn't overshoot on a move) sounds like the way to go.

I imagine theres some protocol to tell the controller the cube is solved (e.g. only turn it on in a solved state) and it just tracks moves from there to determine the current state.


That's how I solve a partially solved cube when I pick them up -- just look at where it is and what's next, don't worry about how it got there.


It doesn't have eyes. Or, perhaps more significantly, a way to track the edge and corner cubelets from the initial "solved" position to the current configuration. Face angle isn't enough, you need the path that was taken to get there.


Gotcha, so in other words, it needs the previous spin to help decide what’s next? (It doesn’t have self-perspective)


You can see its not just playing back the reverse order:

- first human shuffle move was rotate around white side

- last cube movement was rotation around green side

Ergo the cube did not just follow the same steps in reverse order


That does not really matter I think. The cool part is that they very able to build a cube that looks similar like Rubik's but has electronics and motors embedded that are able to turn it.

Solving the cube with a computer is a solved problem for a long time and there are myriads of algorithms. Granted the solutions are not perfect (i.e. using the minimum number of steps needed which is always <= 20), but mostly come close (~25 steps).


I think it has psychological significance.

It's one thing to have an object that violates expectations by taking action that an outwardly similar object does not. It's a surprise move that turns the tables on the person interacting with the object. (You could almost view it as a threat or a power dynamic thing.)

Having those actions be as intelligent as possible raises this surprise to another level. If I fiddled with it for 5 minutes and it put it back in 30 seconds, I'd feel even more like I just got owned by the object.


note too a replay solution could have infinite steps to have to reproduce, assuming its not optimized to take any shortcuts to jump to a re-occurring state.


I don't think one is much harder than the other (since solver algorithms already are a solved problem), the hardware seems more impressive to me than whether you put software on it that tracks and reverses movement or has a solver algorithm in it.

From the video it looks like a solver algorithm by the way, and not going for least amount of movements either, it seems to move much more during the solve than the movements the person did. To save battery they should go for optimal amount of moves!


A Rubiks cube solving algorithm seems like a trivial part of the problem if you can run code on it and give commands to make various turns already.


It's solving itself.

The C++ snippet includes permutations for the Fridrich method's first two layers (F2L), which wouldn't be required for a reverse-replay.


It does need to know it's starting configuration though ! So it starts from a solved cube and needs to record the steps to compute the starting unsolved configuration.


It was mixed 10 times (half rotations counting as 1).

It was “solved” with 56 moves.

Seems like a solve algo to me.


Given the source code screenshot it looks like it's using CFOP to solve, so it's not just replaying a scramble.


The problem here is that "self solving" would necessitate that the cube be able to determine what is "wrong" with itself and ultimately figure out not only the "right" self-configuration, but how to get there. That may be a bit much to ask of a cube considering how hard it is for a human to do that.

Stranger still, it might turn out that the cube decides that it's fine the way it already is and it doesn't need to conform to a "right" configuration based on our expectations. In which case; perhaps we're already invented what you're looking for?


Yeah -- what I'm most curious about is how it determines its initial state. Does it need to be powered up and "zeroed" like a scale before it's scrambled? How does the algorithm know which actuator needs to be moved and which direction it needs to be moved in?


It is not as relevant, it is the hardware that looks cool.


No, to me it looks like it did CFOP with an orange cross on the table, and the white cross when he held it in his hand.


Very cool and impressive.

Next step: a solving algorithm that minimizes maximum net horizontal displacement from the starting position, to avoid falling off the table.

(the demonstration video has the cube almost fall off the table. A human had to interfere to push it away from the edge)


It should stand itself on one edge like Cubli and solve itself [1]

[1] https://www.youtube.com/watch?v=n_6p-1J551Y


Yeah, I was thinking it could add some "walking" moves to get away from the edge. Rotate two sides together like two wheels.


Or replace the table with a bowl.


This solves the problem, but wipes 95% of the value of the device as a portable party trick.


Because there are no bowls at parties?


No party has ever had a bowl, however, it may be possible to research opportunities for introducing them in the future.


Seems to me you could make a pretty neat commercial product out of that. Add some LEDs to each surface, plus a speaker and you could have a Rubik's cube that tutors you on how to solve it.


It could scream in terror every time you try to turn the wrong face.


Xiaomi has made the Giiker cube with bluetooth, that links up to a smartphone app that can help you solve the cube or play games. It's 100 yuan in China, roughly 15 USD. Clearly not as fancy but really affordable.

https://www.aliexpress.com/store/product/Xiaomi-Giiker-Cube/...


In my limited rubik's experience, solving (on an amateur level) is really mostly about memorizing moves and I'm not sure you'd really learn those moves very well just seeing it happen in front of you without explanation.


Hence the speaker and LEDs.


Perfect project to run as a Kickstarter campaign


To be killed by the parent company for infringement maybe.


this would be a sellable product even without the motorized aspect of it


I'd buy one if the price wasn't too nuts. Looks pretty cool.


Or have it play music and be like a DJ Rubik's kind of thing


like a bop-it!


Like a Bop It that never says anything but "Twist it!" over and over again.


Fitting the hardware in the cube is the innovation


I find it strange that people here are fixated with the solving software part. What's really cool to me in the project is the mechanical solution; fitting all the motors, axles, MCU, sensors and battery inside a customized cube.


Exactly this!

The solving algorithm is no big deal at this point. Experienced cubers can solve them in under 10 seconds. There are machines that can solve them in < 1s. [1] Again, the innovation there is the accuracy and precision of the machinery involved.

[1] https://www.youtube.com/watch?v=nt00QzKuNVY


The fact they designed custom servos for this surprises me.

That's a significant time/cost, and typically out of reach for home electronics hobbyists.


There are so many cool mods you could make with this, you could have it change to a particular pattern when idle or scramble again once you solve it!


I like the rescramble idea. You could maybe go one step further by varying the difficulty of the rescrambling - I'm not sure if there's an established distance metric between rc states (something like a levenshtein distance, "minimum-number-of-changes-needed"), but the program could shuffle the cube out to some threshold on that metric to get easy, medium, hard, etc.


There is a metric for the # of turns needed to solve a cube from a particular state. I can't remember its name offhand, but the word for the maximum possible number of moves - 20 - is known as God's Number.

I'm not sure it's relevant to the difficulty of the scramble for a human, though. Most solving methods follow an approach that isn't even trying to find the minimum possible number of moves. The one that most of the fastest speedcubers use is, IIRC, the least move-efficient of all the standard methods. It just manages to be faster in terms of time because it's such rote method that, if you learn it well and get it burned into your muscle memory, you don't really have to ever even stop to think about what you're doing in the middle of a solve.


I'm assuming that this cube could not be handled as a normal cube. The gearing would give it an odd feel, like moving a servo by hand, and giving too much torque would probably wear teeth.

To make it feel "normal", you could "assist" the user with the motors, but I'm guessing speed would be severely limited compared to a normal cube.


Just make the faces buttons and have the button press signal a rotation.


I tried making a self-solving rubik's cube in 2013 as part of a school project [1]. It didn't quite work and I gave up.

[1] https://daniel.lawrence.lu/engineering/cube/


Are there awards for this sort of thing? If not, there should be. Such marvelous engineering and craftsmanship skills need to be recognized for the benefit of the individual and to inspire others.


So it moves while self-solving. If the movement is regular, how about an effort to solve associated 'maze puzzles' with scrambles? It would be neat to see solutions with isomorphic paths.


Suddenly realizing how magicians do their Rubiks Cube tricks, they put them in a bag and the cubes solve themselves..


Maybe, maybe not. Substitution tricks are surely pre-industrial.

This does bring Clarke's third law to mind, though.


In Soviet Russia, Rubik's Cube solves you.


this is not how they do it


This is totally charming! Seems like it would benefit from having a clutch so you can disengage the servos while scrambling or attempting to solve by hand.


See also: Self rolling dice

https://m.youtube.com/watch?v=urd8neVMt4Q



Wow, how did they get 850k?

They have like 2 things, a cube that measures its configuration and some matchmaking platform where you can cube against others.

If one wants to learn how to solve the cube using instructions (although I think finding it out on your own is a nice exercise), there are 1000s on the internet and even apps that use your phone's camera to give specific instructions.

On the other hand if you want to do speed-cubing (that's actually a thing) it is impossible to avoid cheating over the internet (granted that's also true for chess and other games that have been solved using computers).

The linked project however is really cool - completely useless, but extremely nice. Kudos to the maker.


This one has the sensors to measure the state of the cube, but not he motors to manipulate the state.


The innards look like Borg technology. Very cool.


There are some CAD pics in that page. I find it curious that the cad pics merge together the mechanical parts, the wires, and the electronics.

Can anyone tell which CAD software they’re using just by looking at the screenshots?


Just a stab, but it could be PTC Creo using wiring looms.

Example image of wiring an assembly in Creo:

http://www.arbortext.com/-/media/Images/CAD/PTC-Creo-PCX---1...

I am not aware of the interface method Creo uses for wiring or resolving connections, it could be purely graphical with no resolving at all. If so I would assume that the electronics/pcbs you can see in the original article are likely just 3D STEP models exported from the ECAD package into Creo.

Sadly, the market does not currently (to my knowledge) present engineers with one single software solution for ecad->mcad>wiring>assembly>release, instead relying on various software packages, licenses and extensions on these with each user (company) forging their own local workarounds to bridge or replace specific steps of the process.


The number of solve moves appears to be 4x the number of shuffle moves (?)


Nice observation. I count 15 vs 65.

Most algorithm to solve the cube use some family of predefined blocks of moves. Each block of moves does something simple but interesting, like swapping two edges, or rotating two corners, without changing the rest of the cube. So you can start building one face and then slowly extend the solved part until all the cube is solved.

This is easy to memorize and to use, because all the decisions to use a block of moves are "greedy", you just fix another edge or you fix another corner, one by one.

The problem is that this approach doesn't provide the shorter solution. It's funny to make tree or four moves and then watch someone else use a few hundreds of moves to solve the cube.


The cube can't do middle rotations, so it will take longer than the minimum path in general; it's also likely that the solving code is not well optimized.


Yeah, they're using a rather naive human-oriented algorithm. It would be straightforward to improve this with a software upgrade.


The videos are incredibly satisfying. I wonder... if you try the old trick of flipping a single edge piece does it give up immediately or attempt the impossible forever?


I bet it has absolutely no idea what the colors on the stickers are. It's probably just keeping track of how the cubelets have been permuted from some initial state, and then figuring out how to get back to that state.

So, if you flip a single edge or corner piece, it'll just solve itself into a state where every cubelet is in the correct position, but that edge or corner piece is rotated.


Yes, it may need to be flipped in software as well as in hardware.


If the software allows for modeling that kind of thing.

There's two ways you could model a piece's orientation in the code: Either relative to its initial state, or relative to some external/objective reference point. The latter would allow you to say, "The initial state looks like the traditional solved state except that this one piece is flipped." Otherwise, though, it wouldn't really be useful, and I'm pretty sure that it would make both the math and the programming more complicated, so I'd assume (or at least hope) that that's not how it's being done.


The software to see if it's in a valid state is trivial. But like the other commenter said, it's probably just calibrated to a "start" position.


Kids these days. Next they'll have bowling balls you can steer with your phone.


That's an awesome idea.

There's a lot of room in a bowling ball so I think it should be possible.

Let's put a camera in the finger holes (no idea if there is a "right" name for them, sorry) and make the ball steer itself.

After that works, start to reduce the hardware size and go for golf balls and the big money ;)


The shortest implementation of solving algorithm is a stack of taken moves while shuffling which just should be reversed one by one.


Unless you scramble the cube using more than 20 moves. http://www.cube20.org/


The comment you're replying to mentioned the shortest implementation, as in the size of the program written to solve the problem.

I believe you're talking about the the optimal shortest path to the solution, which while true, relevant and interesting, isn't contrary to the point.


You could have shuffled it into a position where it takes less moves to solve than you made while shuffling.


specifically, rotate one face one quarter turn 3 times. a replay will undo all 3, but the optimal move is to continue the rotation one more quarter turn. (as the degenerate case for a solution being better than unwinding the move stack.)


He said the shortest implementation, not the shortest execution. I think he meant that the easiest solver to "code" is to just remember the scramble and reverse it.

You can see from the videos that it is not doing that though. The solution is not the trivial reverse of the scramble.


Ah, I misread. Makes enough sense!


More interestingly, the cube is always 20 moves away from a solution, not matter how much you've mixed it up.


Nitpick: cube is at most 20 moves away from the solution. There may be cases when less moves a needed :)

https://en.wikipedia.org/wiki/God%27s_algorithm


Nitpick: aidos is right. The cube is always 20 moves away from a solution (but that solution typically isn’t the fastest possible (the 20 is in face turns, not quarter turns, so you can always add extra turns to the optimal solution to make the solution take 20 turns))


That might very well be, but is it obviously so? What if there was a position that takes 19 moves to solve in the fastest way possible but the next-best solution takes 21 moves? Is there always a solution that takes an even number of steps?


Yes, there is. If the last turn is a quarter turn, replace it by a half turn and a quarter turn in the other direction. If it is a half turn, replace it by two quarter turns.


Well, okay. Technically you're right ;) But what if you count any movements that are followed by another movement of the same face as a single step?


The set of possible configurations would split in an even and an odd set, so there would be configurations that can’t be solved in God’s number of moves.

(AFAIK, we don’t know God’s number if we count moves that way. I would guess it’s larger than 20)


That's definitely a legitimate nitpick!


That depends on whether you think "unscrambling" counts as "solving".


Probably a silly idea, but I wonder if the cube will maintain zero net entropy through this self-solving process.


Frictionless motors must be pretty expensive.


This was my first idea for my senior project in 2012! Didn't do it, but glad someone finally did.


How does the microcontroller know the state of the cube?


Useless Rubik's Cube


QUALITY tutorial... I just did one and am not sure I explained as concisely


That's so cool! When I was figuring out how to solve it myself (took a year of tinkering to come up with an algorithm) the first big revelation is that the centres always stay fixed relative to one another.


Sounds like you're ready for a Rubik's Revenge (4x4x4)!


Solving the original Rubik Cube (Ideal branded, obviously) was an impressive feat 35 or so years ago when the craze was in full swing. I would say this cube is a little bit late to the party. But wouldn't it have been fantastic if your cube could have gone into 'teaching mode' or 'hints mode' where an automated cube could just nudge you on to be able to finish the puzzle without a) popping the squares out or b) clumsily picking off stickers and re-applying them, thinking nobody would notice.

Also had this cube been a retail best seller a decade ago then I think Edward Snowden would have had to have chosen another toy to hide his SD cards in.

Nonetheless, Christmas is coming up, I hope Santa has one of these for me...




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: