7 ms·
Can a Rubik's Cube be brute-forced?
- Terr_ 2y ago> The essence of the result is this. Reminiscent of a “meet in the middle” algorithm Hm, so something akin to a bidirectional path-finding problem, where one can still call it "brute force" because both known positions (start and goal) are each doing a breadth-first search, as opposed to something fancier than picks a direction. https://en.wikipedia.org/wiki/Bidirectional_search https://en.wikipedia.org/wiki/Bidirectional_search
- nostromo177 2y ago[dead]
- dang 2y agoRelated: Can a Rubik's Cube be brute-forced? - https://news.ycombinator.com/item?id=36645846 https://news.ycombinator.com/item?id=36645846 - July 2023 (108 comments) (Reposts are fine after a year or so; links to past threads are just to satisfy extra-curious readers)
- scoot 2y agoPerhaps just post without justification of it's allowed? (Imagine if every valid post had to follow with why they think it's okay to post...)
- echoangle 2y agoI’m not sure if I’m reading your comment right but dang is a moderator and wasn’t justifying his comment, but saying that this post is fine. He wanted to clarify that him posting the previous post with the same link wasn’t a criticism but just for reference.
- dang 2y agoechoangle is correct! Reposts are fine after a year or so. This is in the FAQ: https://news.ycombinator.com/newsfaq.html https://news.ycombinator.com/newsfaq.html. Links to past threads are just to satisfy extra-curious readers. Edit: I guess I already said that above.
- scoot 2y agoMy bad, I read it incorrectly Edit: I appreciate my comment being hidden to reduce distraction for others, and to (selfishly) to prevent downvoting (not that I'm collecting MIPs or anything! <sweatsmile>)
- dang 2y agoOh you're far from the only one who reads those links that way—people commonly (mis)interpret links to past threads as being an implicit reproach ("why did you post this? it was already posted years ago"), when the intended meaning is more "hey, if you like this, there's related interesting stuff over here". I struggled for years to find the right language for presenting those links because nearly every wording seemed to provoke this misunderstanding. I eventually settled on simply saying "Related". That seems to minimize (but alas not eliminate) it. I often say "Related. Others?" which seems to work pretty well (https://hn.algolia.com/?dateRange=all&page=0&prefix=true&query=by%3Adang%20related%20others&sort=byDate&type=comment https://hn.algolia.com/?dateRange=all&page=0&prefix=true&que...). It's still my intention to integrate this related-links business more into HN's UI, which could maybe help with this quite a bit.
- dredmorbius 2y agoI'll often call out either dupes (reposts w/in a year, often w/in days, hours, or minutes...) vs. prior discussions, and especially perennial favourites. For the latter I'll specifically note that reposts are in fact permitted and encouraged after a suitable period, linking guidelines and one of your own comments to that effect. Where submissions have had recent discussion but not above HN's somewhat vague "significant discussion" threshold (I generally go by <20 comments), I'll also note that. Often it's because I'd recalled earlier submission and wasn't sure myself whether or not those were dupes. Since other HN readers are also involved in flagging dupes, or boosting repeat submissions for stories under the threshold, communicating this clearly is useful. A point I've also emphasized in the past: <https://news.ycombinator.com/item?id=40849853 https://news.ycombinator.com/item?id=40849853> My own first comment on that thread my be buried dues to downvotes, it's the reply to the linked comment and read (prior to clarifying edits linking & citing guidelines): If you're calling a submission a dupe, say so. In this case, there's an 11-hour old submission, but at only 6 comments, it's well below the threshold I (a non-privileged HN participant) usually call for dupes, that being ~20 comments. So no, this is not a dupe. Since it's difficult to assess an author's intent on a vague or link-only comment, being explicit as to what the situation is is something I'd strongly encourage.
- pge 2y agoThis reminds of the time I decided to teach one of my kids about computer programming, and suggested we write a program to solve a rubik's cube as an example (rubik's cubes were popular at her school at the time). Only after we had written a really simple depth-first search did I realize that it would take several lifetimes to run. Great lesson, but not the one I meant to impart!
- Vampiero 2y agoIn hindsight it should have been fairly obvious that it would immediately explode into a combinatorics problem
- pge 2y agoyes, 30 seconds of math would have told me that, but I foolishly jumped in without doing that calculation…
- madcaptenor 2y agoChemists have a saying about this: "A month in the laboratory can save an hour in the library." (The time units can vary, but yes, I did write that correctly.)
- joelwilliamson 2y agoA month of programming can save an hour of planning.
- consf 2y agoSometimes the unintended lessons are the most memorable
- lukan 2y agoYes, but usually it is pretty bad for the learning experience, if the teacher stumbles and needs time for himself to figure things out. It can work out to become a deep lesson, if the student is highly motivated and the teacher good at explaining his thought processes - otherwise the student will stand aside and get bored and loose interest, as the problem is way beyond his level to understand.
- krisoft 2y agoOf course the true brute-forced algorithm is to pry the cube apart and then assemble it again in the solved state.
- mihaaly 2y agoI once rearranged the coloured stickers on the faces. On top of cheating it looked very ugly afterwards. : ) (ps.: after a quick search I see that one can buy replacement stickers for a few bucks on Amazon :D)
- Patrick_Devine 2y agoAll the good Chinese speed cubes these days are sticker-less, so thankfully no more ugly cubes with grody stickers.
- foobarian 2y agoThe fun thing about disassembling a cube is that not all reassembled states are solvable; makes for hours of fun with unwitting Rubik solving friends.
- stouset 2y agoEh, the friends that don’t know this almost certainly aren’t solving the cube anyway. The ones who would be likely to solve it would catch on pretty quickly.
- taeric 2y agoFun to see someone else look at the cube as permutations. https://taeric.github.io/cube-permutations-1.html https://taeric.github.io/cube-permutations-1.html is one of the more fun visualizations I've made that was looking at this. Reminds me I need to finish it. I can't remember why I haven't gotten further.
- dunham 2y agoI had a prof in college describe solving a rubik's cube as group conjugation (e.g. f * g * f^-1). For example, you find a way to swap two pieces on the top layer and mangle the bottom (f), turn the top (g), and then do the opposite (f^-1), swapping a different pair and un-mangling the bottom. Between complementary swaps, edge flips, and corner rotations, you can build an entire solution with this technique. (My current version of this does the edges first, ignoring any damage to corners and then does corners.) Somewhat related - many years ago there was a tutorial of the Gap computer algebra system that analyzed the rubik's cube group. I can't find the original, but there is a translation to Julia here: https://oscar-system.github.io/GAP.jl/stable/examples/ https://oscar-system.github.io/GAP.jl/stable/examples/
- eddd-ddde 2y agoYes! This is also how I learnt to solve Rubik's cubes. You eventually develop the intuition to solve any move without having to "memorize" anything.
- tripplyons 2y agoThis is exactly how the Old Pochmann method works for solving a Rubik's cube blindfolded! You can effectively come up with and memorize a sequence of corner swaps and edge swaps. It is probably the simplest method for solving a Rubik's cube sighted as well because of how simple it is.
- chris_va 2y agoThis sounds like bidirectional search + rainbow tables
- wly_cdgr 2y agoAfter 6831 (give or take) hours, I'm pretty sure the answer is "no"
- alexsmirnov 2y agoSure it can. At the peak of Cube popularity, I saw "game set" in store. Included Rubik's Cube and hammer.
- lpizzirani 2y agoI feel like a simple brute force method is using a "labirinth" exploration. Make a list of all possible moves in a single state, do one of these moves and check: if you already saw the result, go back and try a new branch until the cube is solved.
- jcalx 2y agoCompare another "brute force" method: if we imagine the state space of all Rubik's Cube configurations as nodes and quarter-turn transitions between them as edges, it turns out there exists [0] a Hamiltonian circuit for this massive graph. By symmetry, we can traverse this circuit with the same moves starting from any configuration. Amazingly this means we can solve a Rubik's Cube without ever knowing what the original configuration is, as long as we can ask at any time if the cube is solved or not. [0] https://bruce.cubing.net/ham333/rubikhamiltonexplanation.html https://bruce.cubing.net/ham333/rubikhamiltonexplanation.htm...
- dataflow 2y ago> Amazingly this means we can solve a Rubik's Cube without ever knowing what the original configuration is, as long as we can ask at any time if the cube is solved or not. I think you mean current configuration? Otherwise it's kind of silly, the original configuration is irrelevant once you know the configuration you are currently at.
- sebastianmestre 2y agoYes, you can solve a cube by this simple algorithm i = 0 while not solved apply move(i) Interestingly, there is no constant function `move(i) = x` that makes this algorithm correct. If there was, there would be a single element x of the rubik's cube group that generates the entire group (every element could be written as x^n) This would imply that the group is commutative (x^n * x^m = x^(n+m) = x^(m+n) = x^m * x^n), which every cuber knows is false from experience (permuting moves does not lead to the same final configuration) An interesting question would then be: whats the simplest piecewise-constant function that makes this algorithm work? I.e. is it possible to use move x1 for the first n1 steps, then x2 for the second n2, then x3 for the next n3, ..., then xk for the next nk? And if so, what is the smallest k that makes it so?
- BoiledCabbage 2y agoThe whole point is that in a way, there is that constant function that you say doesn't exist. Or more specifically, there is a fixed sequence of moves that will traverse through every possible configuration of a Rubik's cube then take you back to whereveryou started. One of those states is the solved state. Meaning whenever you complete this sequence you will have done a full loop of all possible cube states. The interesting thing is that it doesn't matter where you start, you can follow this same sequence. So you can be blindfolded, never see the cube, perform the sequence and one of those states will be a solved Rubik's cube. That I believe is OPs point.
- barrystaes 2y agoI’d say; Yes using only about 7 steps where each repeats a permutation, but it requires reorientation of the cube ofcourse. But reassembling is the true brute.