Here comes another toy puzzle I encountered recently:

Can you arrange 27 cubes, each colored one of nine different colors (3 cubes of each color) into a 3×3×3 cube so that each face shows one square of each color?

As usual, these types of puzzles are fun because they can be solved in many different ways. For this one in particular, it becomes useful to visualize the cube in 3D, which can be done quite easily with Three.js.

Take a moment to think about it before reading the rest!

The puzzle can surely be solved with an exact and deterministic method, involving recursion and heavy pruning. Or even by hand with a magic formula.

But when the number of combinations is high and we don’t necessarily know how to start, it can be convenient to go with a more randomized approach, such as Genetic Algorithm, Simulated Annealing, Monte-Carlo Tree Search and so on.

Simulated annealing has the advantage to have a simple implementation (very little code), and it is the approach proposed in this post.

Here are the most important bits of the solver:

A few points:

- Cubes are defined by an integer between 0 and 26, and colors by an integer between 0 and 8
- The cost is evaluated based on the number of valid faces
- A face is valid if it contains the 9 colors
- From a current state of the cube, a new neighbor is created by swapping 2 cubes randomly chosen

With one caveat: Javascript’s default `Math.random`

function can’t be seeded (it’s a shame I know). To keep the code simple and limit the number of dependencies, I decided to use it anyway. So each page refresh might generate a different solution and can be slower or faster to converge.

The code is available as a gist: https://gist.github.com/jtpio/7d28871d961c7dc0aab161d2e329326c. The solver is wrapped within a Web Worker so it is executed asynchronously on the web page. Feel free to check it out by yourself by downloading it and running a simple web server (`python -m http.server`

for instance, necessary for the Web Worker).

Here is a screenshot of one possible solution:

As always, there must be more than one approach to solve it. Let me know if you found a different one!

Finding a solution for this puzzle wasn’t too difficult, because the cubes can be arbitrarily placed on top of each other.

Apparently there exists a “physical” version of this puzzle, a la Rubik’s Cube, as stated on the Nine-Colour Cube Wikipedia page. The moves seem to be similar to the original Rubik’s Cube (rotation of an entire face), which definitively makes it more challenging!

comments powered by DisqusBy Jeremy Tuloup – 2018 – Theme by bootswatch (slightly tweaked)