Can a Rubik's Cube be brute-forced?

 (stylewarning.com)

37 points | by lispybanana3 天前

10 comments

  • dunham2 天前
    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-ddde2 天前
      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.

  • krisoft2 天前
    Of course the true brute-forced algorithm is to pry the cube apart and then assemble it again in the solved state.
    • mihaaly2 天前
      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_Devine2 天前
        All the good Chinese speed cubes these days are sticker-less, so thankfully no more ugly cubes with grody stickers.
  • Terr_3 天前
    > 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

  • dang2 天前
    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)

  • taeric2 天前
    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.
  • pge2 天前
    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!
    • Vampiero2 天前
      In hindsight it should have been fairly obvious that it would immediately explode into a combinatorics problem
      • pge2 天前
        yes, 30 seconds of math would have told me that, but I foolishly jumped in without doing that calculation…
        • madcaptenor2 天前
          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.)
          • joelwilliamson2 天前
            A month of programming can save an hour of planning.
    • consf2 天前
      Sometimes the unintended lessons are the most memorable
      • lukan2 天前
        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.
        • consf1 天前
          But sometimes, watching a teacher work through a problem can actually demystify the process
  • lpizzirani1 天前
    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.
  • alexsmirnov2 天前
    Sure it can. At the peak of Cube popularity, I saw "game set" in store. Included Rubik's Cube and hammer.
  • wly_cdgr2 天前
    After 6831 (give or take) hours, I'm pretty sure the answer is "no"
  • chris_va2 天前
    This sounds like bidirectional search + rainbow tables