Two directional serch for cube solutions...

I remember when the cube first came out, theorist speculated any cube could be solved in around 25 moves. However, if this site is solving consistently in under 20 and not claiming that as optimal, then the actual maximum number of moves needed must be in the teens.

The fact that this typically solves cubes in 18 or so moves does not prove that some position would not require 25 moves, but that does not seem likely. What is most likely is that more than 90% of all scrambled positions can be solved in no less than the theoretical maximum.

Regardless, I still think an optimal solution could be done on home computers in around 10 years.

> However, if this site is solving consistently in under 20 and not claiming that as optimal, then the actual maximum number of moves needed must be in the teens.

The superflip (to take a well-known example) requires 20 (q+h), so the maximum is at least 20. There are other positions known at depth 20, see

http://www.math.ucf.edu/~reid/Rubik/symmetric.html
http://www.geocities.com/jaapsch/puzzles/symmetr1.htm

So far as I am aware, all of the known cases at depth 20 have a high degree of symmetry.

> Regardless, I still think an optimal solution could be done on home computers in around 10 years.

If you mean optimal solutions to specific problems, Cube Explorer (or Mike Reid's program) will already do that for you, as kcushing mentioned. If not... I am unsure what you mean.

Just a followup. In the face turn metric (q turns and h turns allowed), no position has been found that takes more than 20 moves, and positions have been found that do take the full 20 moves. There is no proof that I know of that 20 moves is maximal. The fact that Cube Explorer "always" finds a solution in 20 face turns or less is not a proof that no positions exist that do take more than 20 face turns.

In the quarter turn metric, a position has been found (by Mike Reid) that requires 26 moves.

Cube Explorer works in the face turn metric. The algorithm that it uses is better suited to the face turn metric than it is to the quarter turn metric.

>Someone on this thread suggested strong 5 moves from each direction and searching beyond there without storing the positions.

It's workable, though I have not tried it myself (IDA* is almost certainly faster in practice, on any machine with sufficient memory)... the detailed description of the Fiat algorithm can be downloaded from here.

The paper is an old one (1989): I'm not sure whether you would need an IEEE subscription to read it (but see also the link below).

All the states at depth 10, say, from both ends can be generated in O(N^0.5) time by combining pairs of permutations at depth 5. The key point (mentioned in my earlier post) is that those states are generated in a definite order, so that all matches can be found without storing more than a tiny fraction of the search fronts in memory.

A good description (with an explicit example) of how the states can be generated "in order" was given in Cube Lovers by Alan Bawden. His explanation is considerably clearer than the original article.

I have used half of the Shamir algorithm to calculate the number of positions out to ten face moves from Start and out to thirteen quarter turns from Start. The results out to ten face moves and out to twelve quarter turns were posted to the old Cube-Lovers. The results out to thirteen quarter turns were calculated after Cube-Lovers shut down, and so far have not been posted anywhere. The algorithm is fairly slow and takes a lot of memory. I'm working on some improvements as we speak.

By "half the algorithm", I mean simply that you start a unidirectional search at Start, producing positions in lexicographic order in order to eliminate duplicates. You don't do the other half of the bi-directional search.

In order to calculate out to 2n from Start, you have to store all the positions out to n from Start.

Indeed, the bookkeeping is very nasty.

Jerry Bryan

.
Thanks to everyone who wrote back about this question.

Funny how small the world is; the paper many of you refer to as Shamir's method was written by a bunch of people whose main interest is Cryptography, the science of secret communication. This is indeed my field of research, including quantum cryptography and quantum teleportation (http://www.cs.mcgill.ca/~crepeau/index_en.html).

For the record the authors of the paper are Fiat, Moses, Shamir, Shimshoni and Tardos. It is the tradition in our field to list authors in alphabetical order, regardless of each other's contribution. A proper way to refer to their work is to use the accronym "FMSST89".

On may 22, 1987 Adi Shamir gave a lecture at MIT on early work towards FMSST89. I was a grad student at MIT at the time but unfortunately I was away on that day and missed his lecture...

Of course Shamir is the most famous of these people (because of the RSA cryptosystem) but all five of them deserve our recongnition. Funny that "RSA" is indeed a very rare exception to the alphabetical order rule. I assume they knew the tremendous significance of their invention and decided to be listed according to contributions instead of alphabetically.

To summarize what I found in your answers and in e-mail discussions with some of you:
1) Tom Rikicki developped a C program that optimally solves Rubik's cube configurations (http://tomas.rokicki.com/rubsolv164.c) and requires 700Mb to run.
2) Herbert Kociemba developped "cube explorer" a windows-only program that also computes optimal solutions.

Being a Mac OS person, I didn't manage to try "cube explorer" yet. I am hoping to compile Rikicki's C program on my Mac but have not found the time to do that yet (I need to find a gcc compiler). I am not sure what method neither of these programs use exactly. Please correct me if I have missed anybody else's software...

Cheers, Claude

There are also

(3) Herbert Kociemba's old program Cube Optimizer, available as C++ source code (easily compiled). Not as fast as the optimal solvers in the current Cube Explorer, but very useful for working in batch mode.

(4) Mike Reid's program. C source only, but uses symmetry reductions and can do QTM or HTM. Needs a little fiddling around to get it to compile with non-GNU compilers. See
http://www.math.ucf.edu/~reid/Rubik/optimal_solver.html

Either program will run with about 90Mb RAM.

> level 10 will be approximately 231x10^9 [positions]
> I think it is doable.

You could indeed generate that list, and store it completely if you had about 2 Terabytes of space, assuming you use about 66 bits per position. This can be much reduced by using some trickery. The list should be in sorted order, so that looking up a position is fast.

You then need to consider those positions as permutations, and apply the inverse permutation to the position wou want to solve. This essentially generates another list of the same size. Any position these lists have in common will give a solution.

This second list need not be stored, and could be checked against the first list as it is generated. I suspect however that unless you could somehow have that first list in Ram, the disk seek time will make it extremely slow.
You could instead generate and store the second list level by level. At each level sort it, and compare the sorted list to the first sorted list. This is much quicker since you are reading through the first list in order, and are comparing many more positions as you do so.

> Maybe Herbert or Jaap known a position that needs more than 20 turns?

There are no q+h positions >20 turns that I know of. Tom Rokicki has done a lot of searching with his optimal solver and not found any in over 10000 positions.

> On a 32-bit machine the array limit is 2 billion
Isn't that just the limit on the index? Why not use a 2 dimensional array then.

> Going to level 11 is necessary because we already know that some positions require 20 moves.
Level 10 would be enough to solve all the positions we know of. Level 11 would only be necessary when we happen to get one of those elusive positions that require more than 20 moves (and then the level 10 list is enough to prove it is >20 moves).

So far I would say that for solving individual positions, this method would be overkill. The standard IDA* searches are pretty effective.
On the other hand, if you wanted to prove that all positions can be solved in 20 moves, or search for positions that need 21 moves then such a table would be a very good start.

I would actually store the positions not in one long list but as an array of lists. The array is indexed by the corner arrangement, and the list is of all edge arrangements that occur with that corner arrangement. This also makes it easier to make the table smaller taking into account the symmetries of the cube.

For any corner arrangement it should then be easy to check whether all positions with that corner arrangement are solvable within 20 moves. Then to search for positions of 21 moves, you could start by checking the more likely corner arrangements first (e.g. supertwist)



Jaap's Puzzle Page:
http://www.geocities.com/jaapsch/puzzles/

Jaap,

I'm pretty sure the limit in my case is from the 32-bit address limit. I'll have to look at the code again to see if it was signed or unsigned.
The absolute limit would be 4 gigabytes on a 32-bit machine. I never actually maxed out the memory in this system so the program was using the swap space as virtual memory, which turned out better than I thought it would.

64 bit motherboards and processors are becoming very affordable so it's the price of memory that concerns me. Assuming I can use DDR400 SDIMM modules it's about $250 Canadian per gigabyte. The biggest hard drives seem to be around 160 gig so it may be a while before we can search for more antipode(s).

> I'm pretty sure the limit in my case is from the 32-bit address
> limit. I'll have to look at the code again to see if it was signed
> or unsigned.
> The absolute limit would be 4 gigabytes on a 32-bit machine.

The internal workings of the modern PC are a bit of a mystery to me. Is >4Gb really not possible without a 64-bit architecture? I thought memory was paged anyway so that should not be a problem.
Sure, you can't have an array with more then 2^32 entries, simply because the index is a 32 bit integer, but that is why I thought that using multi-dimensional arrays could work. I know you can't have files that are more then 4Gb on most OSes, because the file pointers are usually ints too.
Anyway, there is no need to have the whole lot in a single file/array. By using multiple (or multi-dim) arrays/files, you should be able to get around such artificial limits.

Then again, all this may be completely off base, as it is mostly speculation.

Jaap's Puzzle Page:
http://www.geocities.com/jaapsch/puzzles/

>Tom Rokicki has done a lot of searching with his optimal solver and not found any in over 10000 positions.

I haven't seen a report of this work. Do you happen to know what distribution of states was, w.r.t. depth in the q+h metric? And, especially, did he find any at depth 20 in his sample?

Sorry, I remembered wrong. It was 'only' 22700 or so cubes, and another 34000 in q metric:

http://games.groups.yahoo.com/group/speedsolvingrubikscube/message/8541

There were no 20 q+h positions, and 23 is the deepest in q metric.

Jaap's Puzzle Page:
http://www.geocities.com/jaapsch/puzzles/

Mike Reid found a position requiring 26 moves in the quarter turn metric. Given that random and exhaustive searching apparently found no position requiring more than 23 moves in the quarter turn metric, I would be dubious that 20 moves is maximal in the face turn metric.

Jerry Bryan