[HN Gopher] Can a Rubik's Cube be brute-forced?
___________________________________________________________________
Can a Rubik's Cube be brute-forced?
Author : lispybanana
Score : 52 points
Date : 2024-10-28 00:01 UTC (3 days 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.
| consf wrote:
| But sometimes, watching a teacher work through a problem
| can actually demystify the process
| bqmjjx0kac wrote:
| 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.
| Suppafly wrote:
| >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.
| _flux wrote:
| Does this also happen if you select the branches that are
| closest to the solved state?
| sebtron wrote:
| 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
| 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.
| foobarian wrote:
| 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.
| 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.
| tripplyons wrote:
| 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.
| 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.
| lpizzirani wrote:
| 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.
| jcalx wrote:
| 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...
| dataflow wrote:
| > 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.
___________________________________________________________________
(page generated 2024-10-31 23:01 UTC)