# Finding optimal solution for higher order cubes



## AlexanderGZH (Aug 9, 2015)

Could there a universal algorithm for a n by n by n cube optimal solution? Or by using brute force, what are the ways to lower the amount of guesses?
Currently what I'm thinking of is preventing the algorithm from making unnecessary tries by increasing the lower bound of the number of moves, but I'm currently unable to think of a way to do it.


----------



## mDiPalma (Aug 9, 2015)

In my opinion, if the puzzle has corners, the optimal corner solution is a lower bound. Also EP, EO, etc...

Btw, as far I can understand, you need a Table or Expert System or something for that.


----------



## EMI (Aug 9, 2015)

^ This is not a question of opinion.

OP: I believe a lower bound doesn't really help a lot. For a 4x4, there are roughly 36 possible "next turns", so the number of positions that require n + 1 moves is (roughly speaking) 36 times larger than the number of positions that require n moves. So I guess if you take the length of an optimal corner solution as a lower bound (maybe 10 moves), and your position requires something like 15 moves to solve, it doesn't really make a difference if you try all move combinations of n < 16 or only try 9 < n < 16.


----------



## Lucas Garron (Aug 9, 2015)

AlexanderGZH said:


> Could there a universal algorithm for a n by n by n cube optimal solution? Or by using brute force, what are the ways to lower the amount of guesses?
> Currently what I'm thinking of is preventing the algorithm from making unnecessary tries by increasing the lower bound of the number of moves, but I'm currently unable to think of a way to do it.



Could there be? There is! But unfortunately, we don't know if anything that's fundamentally much faster than brute force.
http://www.jaapsch.net/puzzles/compcube.htm describes the most common techniques. We have multi-stage solvers and pruning tables to help, but they only help until about 3x3x3.

Assuming you meant "decreasing the upper bound", IDA[*] with pruning tables realizes your idea.


----------



## mDiPalma (Aug 9, 2015)

In my experience, EMI is completely correct. If you're going to do some pure IDA, you will likely (in my opinion) bust through the lower bound really quickly from a depth of 0 moves. But if you had a really smart method, you might be able to get a lower bound that's pretty close to the optimal solution.

And you could perhaps use the same lower-bound table as a pruning table. My personal view is that this might help you throughout the solve.


----------

