# Questions about God's algorithm and Rubik's cube

I am creating Rubik's cube solver. It will be good if solver could solve cubes of any size and if it could generate short solutions.

I have found many various information about God's algorithm, which as I understand is able to solve various puzzles, not only Rubic's cube.

So I want to implement God's algorithm, but I cannot find any simple explanation of this algorithm.

In simple words, how does God's algorithm actually work?

• @AndresF. I don't think he is asking for help implementing God's Algorithm but instead asking for a simple clear explanation of what it is and how it works in lay terms. – maple_shaft Jan 13 '14 at 13:01
• @maple_shaft the original question did ask for implementation, but that got edited out. – ratchet freak Jan 13 '14 at 13:14
• In simple words, God's algorithm is: "Always make the best move." – Hellion Jan 13 '14 at 15:52

I don't think it's possible to do better than to quote Wikipedia:God's algorithm:

God's algorithm ... refers to any algorithm which produces a solution having the fewest possible number of moves, the idea being that an omniscient being would know an optimal step from any given configuration.

So it's not "an" algorithm whose working can be described. There are multiple such algorithms, including breadth-first-search and meet-in-the-middle (which performs breadth-first-search from the current position and the solved position and looks for a position reachable by both).

"God's algorithm" is no actual algorithm. It is the theoretical algorithm which solves a given problem in the optimal way. But this algorithm is always specific to a problem.

• There are problems which can be solved by an algorithm which was mathematically proven to be ideal, so this algorithm can be called "God's algorithm" for that given problem.
• For others problems there are algorithms which are suspected to be "God's algorithm" but there is no proof yet.
• There are problems for which algorithms exist, but there is reason to believe that there must be a better algorithm, so God's algorithm for that problem still needs to be found.

The algorithm works a lot like the perfect strategy in chess: from the solved state, recursively enumerate all neighbour states. Once you reach a state that equals your current state, the path that you took to find it is the shortest route to the solution.

The trouble with it is that the space and time required to actually construct the complete tree becomes astronomical, far too large to actually expend them. So its only advantage is that we know it exists, and how to perform it if we could afford it.

Obviously, we would like to have something better; a method that will reliably find the shortest path with much less effort. If we could get hold of such an algorithm, it would make the problem much easier, and presumably (particularly if it were elegant) it would then inherit the appellation "God's algorithm", because it would be superior to the naive solution in every respect. The trouble is that not only do we not know such a method, we don't even know whether it exists.

• Nonsense. There's already a standard method which improves on breadth-first search in a permutation space: it's variously called meet-in-the-middle, bidirectional search, and probably one or two other names. – Peter Taylor Jan 13 '14 at 12:23
• and there are several methods to find "probably good paths" one of which is A* with a good heuristic – ratchet freak Jan 13 '14 at 12:27

To get started with, God's Algorithm is not an algorithm. There is no particular way in which you can solve different permutations of cube with that algo.

What creators of god's algo did:

• Partitioned the positions into 2,217,093,120 sets of 19,508,428,800 positions each.

• Reduced the count of sets we needed to solve to 55,882,296 using symmetry and set covering.

• And they wrote a program which used about 35 CPU years to find solutions to all of the positions in each of the 55,882,296 sets.

I hope this gives you a hint about how god's algo work.

What you can do -

Just store the `43,252,003,274,489,856,000` permutations of cube along `with the solutions` in a database and then everytime you get a scrambled cube, check in you database for that particular permutation of cube and then get solution. Easy. (Pun intended)

Anyways, here is a link that I found out which may help you - Coset solver source code

Use a search tree to go through the data structure shown below.

From personal experience using a set to keep track of each rotational part of the cube works well. Each sub cube is in three sets no mater the size of the rubik cube. So to find a sub cube some where on the rubik's cube you just take the intersection of the three sets (the result is one sub cube). To do a move remove the effected sub cubs from the sets involved in the move and then put them back into the sets that take them as a result of the move.

The 4 by 4 cube will have 12 sets. 6 sets for the 6 faces and 6 sets for the six bands that go around the cube. The faces each have 16 sub cubes and the bands each have 12 sub cubs. There are a total of 56 sub cubes. Each sub cube holds information about color and the direction of the colors. The rubik cube itself is a 4 by 4 by 4 array with each element having information consisting of the 3 sets that define the sub cube at that location.