MegaminXolver uses too much memory

[Cemoixerestre]

I've run MegaminXolver on my laptop, and it cannot solve a megaminx with more than 20 moves. The reason is that it takes too much memory. A hash-table with depth 10 takes 40% of the memory of my laptop (I have a Lenovo Yoga 2.13, I use ubuntu 16.04).

I have a few ideas to improve the memory usage of this solver:

• Dictionnaries such as {'edgePermutation': …, 'cornerOrientation': …, 'cornerPermutation': …} could be replaced by 3-uples of named tuples. For example:

from collections import namedtuple State = namedtuple('State', field_names=['edgePermutation', 'cornerOrientation', 'cornerPermutation']) solvedState = State(edgePermutation=0, cornerOrientation=0, cornerPermutation=0)

• The hash-map could map states to their distance to the solved state instead of a full sequence of moves. If we know that the state x is at a distance 7 to the solution, we look at the 8 possible moves, and if we see that after applying the move m, we are at a distance 6 to the solution, we know that it there is a sequence starting with m that solves x in 7 moves.

I have implemented your algorithm using these tricks in pure Python. I am able to generate of hash-table of depth 11, and to find a 22-moves solution in a few seconds. It could be useful, because some PLLs cannot be solved in less than 22 moves using the R and U faces.

[Odder]

The reason behind not making it a tuple was readability, but namedTuples seems like a cool addition!

Oh gosh, of course it should use move counts and traverse down for finding the solutions, what a waste of memory.

If you have made these changes, feel free to make a pull request.

[shuantsu-zz]

could you share the code?