# Would it be feasible to use a breadth first search algorithm for finding a solution to the 3x3x3 rubiks cube?

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?

• 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.
– D.W.
Feb 2, 2018 at 16:47
• 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? Feb 2, 2018 at 17:09

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 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).