A pocket cube can have 3 674 160 different positions. For a “No-SQL” database, it’s a piece of cake.
Neo4j is a graph database. In this tool, each node could be a cube position, and eges from one node to another could be a move.
As this software can find the shortest path between two nodes, could it solve the cube with “god move” i.e. 14 at most from a given position ?
The answer is : yes, within a few milliseconds.
Here is how to do.
First of all, we have to code the cube description. Here is a way to do :
This is the same as :
The position of a cube is written into an array of 24 elements :
# The solved cube is as it :
$position = array(
# or, if we give a number for each color :
$position = array(
However, this representation has a downside : imagine a solved cube in front of you. Its position is
000044335522443355221111. Turn the whole cube in the space to have another side color in front of you. It will be for example
000033552244335522441111. But this is the same cube ! We can’t have 2 IDs !
We can rotate the whole cube 4 times on the 6 faces. There are 24 different notation for the same cube.
To reduce this number to one, we can sort thoses 24 notations by alphabetic order :
The first element is used as the key to identify the position (ID).
The ID for the solved cube is :
Then, we can code, the following methods :
- domove : to play a move, i.e. turn a face like this :
Letters mean : Front, Back, Up, Down, Left, Right. Moves are done clockwise. A “i” is counter clockwise.
In the program, moves are done by swaping the array elements. For example, a move up (U), will change the elements 0 to 3 and 4 to 11 (refer to the description upper).
- undomove : to undo a move (just “domove Li” to undo L ;))
- setpos : to set a given position to the cube.
- rotx : do moves U, Di, and your cube has rotated a 1/4 turn.
- roty : do moves Li, R.
Generating all possible positions
Or how to generate 3 674 160 ids for all the positions of the cube and the links between them.
Here is the algorithm :
we start from the solved cube
save that this position is to do
while we have positions to do:
get the ID (A) of the position
add ID (A) to the nodes if not already added
for each 12 possible moves:
play the move
add the ID (B) of this new position to the nodes if not already added
save thate this position (B) is to do if not already done
save the edge A->B in the edges file
undo the move
save the position ID (A) as done
Here is the progress :
After around twenty hours, we have two CSV files of 110 and 585 Mb.
And bingo ! there are 3 674 160 nodes ! this number has never been coded. So it really works. The algorithm is correct.
We have the
edges.csv file :
You have noticed that i had written headers to import to Neo4j.
Import files to Neo4j
If we have a temporary database, we can delete it :
sudo rm -rf /data/databases/*
Change directory to our CSV files :
Import files to Neo4j :
/var/lib/neo4j/bin/neo4j-admin import \
--into /data/databases/graph.db \
--nodes nodes.csv \
--relationships edges.csv \
--delimiter ";" \
--array-delimiter "-" \
It is really fast ! 3,6 millions nodes and 10,6 millions of edges imported in 1 minute and 8 seconds !
IMPORT DONE in 1m 8s 438ms.
Peak memory usage: 79.57 MB
NB : you have to restart Neo4j :
sudo service neo4j restart.
Solving the cube
Or finding the shortest path between two nodes.
002140534352524214031513. We ask Neo4j, to find the shortest path between it and the solved ID which is
000022443355224433551111Here is the Cypher query :
MATCH (c1:Cube), (c2:Cube), p = shortestPath((c1)-[m:MOVE*]-(c2))
WHERE c1.pos="002140534352524214031513" AND c2.pos="000022443355224433551111"
The results comes in 0.08 seconds :
NB : A directed link is not necessary but in Neo4j links are directed. We don’t care about the directions. A move from node (A) goes to (B) and (B) goes to (A).
We could’nt add the move name to the edges [MOVE] because we have simplified 24 notations to 1.
So to find the move name (F, B, D, Di, L…) between two nodes, we can do like this :
We start from the given position, we play the 12 possible moves, and we check each ID of the new position, to match with the ID of the next node of the solution got from Neo4j.
I made some tests. Cube is really solved at most in 14 moves !
Try the Rubik’s pocket cube solver online.