an invention by aschnell
The Rubik's Cube celebrates its 50th anniversary this year. The goal of this hackweek project is to understand the IDA* (the star is part of the name - not a link to a footnote) algorithm that can be used to find an optimal solution for any (valid) starting condition of a Rubik's cube. The IDA* algorithm also has other applications, e.g. 15-puzzle and pathfinding. I read one paper [1] about it but unfortunately did not understand it well. In any case it is once again graph theory (it is always graph theory if you look at a problem long enough).
Sure there are already implementations of it, e.g.:
https://github.com/Jai0212/Rubiks-Cube-Solver-Using-IDA-Star/
The next hackweek projects are kind of preset already:
Detect cube condition via camera
Build robot to solve real physical Rubik's Cube
[1] https://www.cs.princeton.edu/courses/archive/fall06/cos402/papers/korfrubik.pdf
This project is part of:
Hack Week 24
Activity
Comments
-
10 months ago by aschnell | Reply
So the IDA* algorithm looks more clear now. It finds the solution by iterating the "game tree" but concentrates on the "best" path on every iteration. This is done using a heuristic.
BTW: Back then test research papers were considered part of artificial intelligence so I'm also doing AI after all.
-
10 months ago by aschnell | Reply
I have looked at various programs implementing IDA* based solvers. Many are unfortunately unfinished, broken and undocumented.
The best so far is https://github.com/benbotto/rubiks-cube-cracker. Among other things it properly implements the index to the pattern databases while other programs seem to simply use a hash. It also gives speed measurements: It is really slow (several hours and more). The Korf IDA* solver is apparently still so slow.
That made me think what the online solver at ruwix.com uses since it usually finds a good solution (never had more that 20 moves) in less than a minute. Maybe it uses another approach called the "Two-Phase-Algorithm" (https://kociemba.org/cube.htm). That also used IDA* but combines it with some group theory.
-
10 months ago by aschnell | Reply
Another very old and interesting algorithm is the Thistlethwaite's algorithm that again uses group theory. I proved that any cube can be solved in 52 or less moves. It was later enhanced to use 42 moves (https://www.jaapsch.net/puzzles/thistle.htm). The already mentioned "Two-Phase-Algorithm" is based on the Thistlethwaite's algorithm. And there is also a version of Thistlethwaite's algorithm called Human Thistlethwaite Algorithm.
Similar Projects
Advent of Code: The Diaries by amanzini
Description
It was the Night Before Compile Time ...
Hackweek 25 (December 1-5) perfectly coincides with the first five days of Advent of Code 2025. This project will leverage this overlap to participate in the event in real-time.
To add a layer of challenge and exploration (in the true spirit of Hackweek), the puzzles will be solved using a non-mainstream, modern language like D, Crystal, Gleam or Zig.
The primary project intent is not just simply to solve the puzzles, but to exercise result sharing and documentation. I'd create a public-facing repository documenting the process. This involves treating each day's puzzle as a mini-project: solving it, then documenting the solution with detailed write-ups, analysis of the language's performance and ergonomics, and visualizations.
|
\ ' /
-- (*) --
>*<
>0<@<
>>>@<<*
>@>*<0<<<
>*>>@<<<@<<
>@>>0<<<*<<@<
>*>>0<<@<<<@<<<
>@>>*<<@<>*<<0<*<
\*/ >0>>*<<@<>0><<*<@<<
___\\U//___ >*>>@><0<<*>>@><*<0<<
|\\ | | \\| >@>>0<*<0>>@<<0<<<*<@<<
| \\| | _(UU)_ >((*))_>0><*<0><@<<<0<*<
|\ \| || / //||.*.*.*.|>>@<<*<<@>><0<<<
|\\_|_|&&_// ||*.*.*.*|_\\db//_
""""|'.'.'.|~~|.*.*.*| ____|_
|'.'.'.| ^^^^^^|____|>>>>>>|
~~~~~~~~ '""""`------'
------------------------------------------------
This ASCII pic can be found at
https://asciiart.website/art/1831
Goals
Code, Docs, and Memes: An AoC Story
Have fun!
Involve more people, play together
Solve Days 1-5: Successfully solve both parts of the Advent of Code 2025 puzzles for Days 1-5 using the chosen non-mainstream language.
Daily Documentation & Language Review: Publish a detailed write-up for each day. This documentation will include the solution analysis, the chosen algorithm, and specific commentary on the language's ergonomics, performance, and standard library for the given task.