Can a Rubik's Cube be brute-forced? | Hacker News Reader

Can a Rubik's Cube be brute-forced?

stylewarning.com

61 pointslispybanana40 comments

I 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/

Yes! 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.

This 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.

Of course the true brute-forced algorithm is to pry the cube apart and then assemble it again in the solved state.

I 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)

All the good Chinese speed cubes these days are sticker-less, so thankfully no more ugly cubes with grody stickers.

The fun thing about disassembling a cube is that not all reassembled states are solvable; makes for hours of fun with unwitting Rubik solving friends.

Eh, 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.

Can a Rubik's Cube be brute-forced? - 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)

Perhaps 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...)

I’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.

echoangle is correct!

Reposts are fine after a year or so. This is in the FAQ: 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.

My 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>)

Oh 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&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.

I'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>

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.

> 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

Fun to see someone else look at the cube as permutations. 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.

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

In hindsight it should have been fairly obvious that it would immediately explode into a combinatorics problem

yes, 30 seconds of math would have told me that, but I foolishly jumped in without doing that calculation…

Chemists 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.)

A month of programming can save an hour of planning.

Sometimes the unintended lessons are the most memorable

Yes, 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.

But sometimes, watching a teacher work through a problem can actually demystify the process

In college, I took a discrete math course with the world's most unprepared, distractible professor. It was incredible. He would come in with nothing planned in particular, we could ask about concepts from the textbook and he would invent a problem on the spot. Then he'd run through various problem-solving strategies until one worked. I learned so much about how a mathematician thinks from this class.

This was in sharp contrast to my calculus classes where the results were basically thrown at you fully-formed. If you're lucky, you might get to walk through a proof with the professor, but you're never going to see how they mentally navigate the search space.

Sounds great, much better than rote drugery imo!

>Only after we had written a really simple depth-first search did I realize that it would take several lifetimes to run.

I wonder if just making random moves over and over would be faster.

Does this also happen if you select the branches that are closest to the solved state?

If you just care about finding any solution, you can consider a multi-step approach such as Thistlethwaithe's algorithm.

If insead you want to find the shortest possible solution for any giveb configuration, that indeed is much harder! The best optimal solvers at the moment use very large pruning tables to help the brute-force search.

A nice exercise could be solving a 2x2x2 cube. That one is much more manageable.

This page is great is you want to learn more: https://www.jaapsch.net/puzzles/compcube.htm

Compare 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.htm...

> 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.

Yes, 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?

The 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.

Yeah I got that, but it's really not as interesting as it seems. Let me explain why.

Say we have an array p[1], p[2], ..., p[n] with all possible rubiks cube configurations

Then this function will solve the cube:

    move(1) = p[1]^(-1)
    move(i) = p[i]^(-1) * p[i-1]

In laymans terms, the resulting algorithm is: assume the initial configuration is p[1], then solve it. If it wasn't, undo those moves then solve as if the initial position was p[2], etc...

So, yeah. Those fixed solving sequences / hamiltonian paths are actually very common. We can make one for any permutation of the group elements.

So I posed a more interesting question: what is the simplest sequence of moves that has this property?

I 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.

I’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.

Sure it can. At the peak of Cube popularity, I saw "game set" in store. Included Rubik's Cube and hammer.

This sounds like bidirectional search + rainbow tables

After 6831 (give or take) hours, I'm pretty sure the answer is "no"

Reply on news.ycombinator.com