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/
> 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.
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!
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.)
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.
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 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.
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 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
[dead]
Related:
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)
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
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.
Sure it can. At the peak of Cube popularity, I saw "game set" in store. Included Rubik's Cube and hammer.
After 6831 (give or take) hours, I'm pretty sure the answer is "no"
This sounds like bidirectional search + rainbow tables