[HN Gopher] Can a Rubik's Cube be brute-forced?
___________________________________________________________________
Can a Rubik's Cube be brute-forced?
Author : lispybanana
Score : 31 points
Date : 2024-10-28 00:01 UTC (23 hours ago)
(HTM) web link (www.stylewarning.com)
(TXT) w3m dump (www.stylewarning.com)
| Terr_ wrote:
| > 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
| dang wrote:
| 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)
| pge wrote:
| 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!
| Vampiero wrote:
| In hindsight it should have been fairly obvious that it would
| immediately explode into a combinatorics problem
| pge wrote:
| yes, 30 seconds of math would have told me that, but I
| foolishly jumped in without doing that calculation...
| madcaptenor wrote:
| 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.)
| joelwilliamson wrote:
| A month of programming can save an hour of planning.
| consf wrote:
| Sometimes the unintended lessons are the most memorable
| lukan wrote:
| 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.
| krisoft wrote:
| Of course the true brute-forced algorithm is to pry the cube
| apart and then assemble it again in the solved state.
| mihaaly wrote:
| 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)
| Patrick_Devine wrote:
| All the good Chinese speed cubes these days are sticker-less,
| so thankfully no more ugly cubes with grody stickers.
| taeric wrote:
| 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.
| dunham wrote:
| 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/
| eddd-ddde wrote:
| 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.
| chris_va wrote:
| This sounds like bidirectional search + rainbow tables
| wly_cdgr wrote:
| After 6831 (give or take) hours, I'm pretty sure the answer is
| "no"
| alexsmirnov wrote:
| Sure it can. At the peak of Cube popularity, I saw "game set" in
| store. Included Rubik's Cube and hammer.
___________________________________________________________________
(page generated 2024-10-28 23:01 UTC)