1
$\begingroup$

I am trying to implement a rubiks cube solving program,and I am trying to figure out which algorithm to use,so far I have only come up with using breadth first search to find a shortest path from the initial configuration node to the solution node. Each edge of the graph would be a 90 degree turn of a face of the rubiks cube(180 degree turns considered as 2 turns). As for representing each configuration of the rubiks cube in a node I am thinking of using a 3x3x3 array of integers.Each element of the array would be an int from 1 to 6 representing each of the colours. So if I used the Breadth First Search Algorithm for finding an optimal solution to the rubiks cube, would it run without taking up too much memory or too much time on an average computer?

$\endgroup$
  • 1
    $\begingroup$ What are your thoughts? Have you tried to work out how long it would take? Have you tried to work out how many states there are? Is there something that prevents you from answering this on your own? We're happy to help you understand the concepts but just solving exercise-style problems for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ – D.W. Feb 2 '18 at 16:47
  • $\begingroup$ The answer can depend on how you encode manipulating the cube as a graph. For instance, there are algorithms for cycling three corners without changing the rest of the puzzle, so you could add an edge between the end-state of that move. More importantly, it is important to define a single move is: a single 90 deg turn? Or is an 180 deg turn also a single move? $\endgroup$ – Discrete lizard Feb 2 '18 at 17:09
1
$\begingroup$

For given Rubik's cube, the maximal number of moves required to solve any permutation of valid configuration is 26 in quarter-turn metric, but only 20 as half-turn metric, it means that if you have the most distant configuration amongst all possibilities the height of the tree is 20 levels, using BFS you have to store the previous level, using only quarter-turn metric the number is 26, but using unconstrained BFS the algorithm will terminate after 20 steps. It would also be nice to keep the path from current configuration to solved state if you wish to use it later. With majority of solutions at 18 moves as high as about $29*10^{18}$, the straightforward application of BFS is not really feasible for memory usage.

The worst case time required to solve puzzle from any configuration will traverse all solutions space, this is not feasible either. To put it in numbers, the empirical result to find the worst case number of moves took 35 cpu years, checking only solutions that require less than 20 moves, not aiming at the optimal state, reducing problem by symmetry and splitting to 55,882,296 sets that require checking shrinking actual number of states even further. These observations are not available using vanilla BFS. So the time usage is also not feasible.

As for the comments, using any algorithmic system of solving cube by human will not yield optimal solution, but will span at about 40 to 80 moves, but would be really straightforward to implement and both time and space would be negligible.

The Rubik's Pie (Domino) from the other answer is significantly easier, not only by removal of one layer, but some quarter turns are not possible to perform, but still it requires 18 moves in Half-turn metric and 19 in Quarter-turn metric, with solution space with only $406 425 600$ possible positions which is small when compared with $43 252 003 274 489 856 000$ ($10^{11}$ times smaller).

$\endgroup$
0
$\begingroup$

This depends on what you mean by too much time. I implemented a multi-threaded bidirectional BFS solver for the Rubik's Pie (2x3x3), and for a configuration that took 14 moves to get back to the solution node, it took about 10 hours to find the sequence, but ymmv.

Time was definitely the biggest factor. For a Rubik's cube of that size, there just aren't that many children of a given configuration, so you should be fine on memory.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.