# [email protected] - CrowdCPU Fewest Moves



## MattyAB (Feb 25, 2016)

Hey Everyone,

I am an intermediate programmer, and had the idea of making a fewest moves calculator, where you give it the type of cube and a scramble and it calculates the fewest moves. This led me on to have the though of a [email protected] or BOINC - style program, where you connect to the main server and it gives you a scramble, then your computer takes some time solving it in the fewest moves, then reports back the solve, and how many moves it took. 

Does anyone like this idea?
Can anyone help out, either programming-wise or solving algorithms for big cubes-wise?
Is this idea even useful? Has anyone already calculated an infinite number of fewest moves?



Let me know what you think!


----------



## 00 (Feb 25, 2016)

For 4x4 and above, it's currently impossible to optimally solve a single state.

For 2x2, we can optimally solve every state in a few seconds (probably less).

For 3x3, it would, in theory, be possible to optimally solve every position given enough time, but how would you store all the data?


----------



## Lucas Garron (Feb 25, 2016)

What is your goal?

As 00 points out, it's trivial to construct a full state graph for 2x2x2, and impossible to solve 4x4x4 optimally.

If we didn't know God's number, you could use this to search for hard positions on 3x3x3. But we already know God's number for HTM, and you're unlikely to discover any new ones for QTM.

Most other puzzles are also in the "trivial" or "infeasible" category.

There might be a good problem you could solve with distributed effort, but you should have a problem you're trying to solve before you put effort into a project like this.

An idea: allow people to submit scramble, and distribute the search to get them solutions more quickly than their computer/browser could.


----------



## unsolved (Feb 25, 2016)

00 said:


> For 4x4 and above, it's currently impossible to optimally solve a single state.



Not too long ago we had a *Fewest Moves Challenge* for programs. One of them solved the 4x4x4 scrambles in around 40 moves each in a matter of minutes. The winning program ran with a more sophisticated algorithm over the course of many days and averaged around 36 moves for each of the 5 scrambles. So, we're not as far off as you may imagine.



00 said:


> For 2x2, we can optimally solve every state in a few seconds (probably less).



The 2x2x2 cube has every state mapped to a distance. It is an instantaneous lookup into a table of 88,179,840 positions, which is 3 raised to the power of 7, times 8 factorial.



00 said:


> For 3x3, it would, in theory, be possible to optimally solve every position given enough time, but how would you store all the data?



The 3x3x3 can be solved, optimally, many times per second. The world record machine solve, with a robot physically turning the cube, is 1.06 seconds I believe.








MattyAB said:


> Can anyone help out, either programming-wise or solving algorithms for big cubes-wise?



I've already written a 5x5x5 solving program. It can solve quadrillions of positions in about 17 seconds. The problem is, the branching factor is so large, it still needs lots of time to reach depth 14. Because the mods here are a bunch of jerks, they keep deleting pictures I post of it. So if you want to see it, you can log into my machine live and view it.

Message me on here, and I'll provide instructions to view it.


----------



## Meep (Feb 26, 2016)

unsolved said:


> The 2x2x2 cube has every state mapped to a distance. It is an instantaneous lookup into a table of 88,179,840 positions, which is 3 raised to the power of 7, times 8 factorial.



It's only 7!*3^6 = 3,674,160 positions.



unsolved said:


> The 3x3x3 can be solved, optimally, many times per second. The world record machine solve, with a robot physically turning the cube, is 1.06 seconds I believe.



As far as I know, it can't solve states optimally that quickly. The robots I've seen just take an early sub-optimal solution instead of running it until the two phases converge on an optimal one (which can take minutes depending on specs).



unsolved said:


> I've already written a 5x5x5 solving program. It can solve quadrillions of positions in about 17 seconds. The problem is, the branching factor is so large, it still needs lots of time to reach depth 14. Because the mods here are a bunch of jerks, they keep deleting pictures I post of it. So if you want to see it, you can log into my machine live and view it.



Why don't you just upload it to some free image hosting site (like imgur) and link to it here? I'd imagine they'd be deleting it because it's either too big, or you keep uploading the same (or similar) screenshots to this site, taking up unnecessary space (with lots of free hosts available). It seems really silly to have someone log into a machine just to view what a screenshot or screen-recording could show.


----------



## unsolved (Feb 26, 2016)

Meep said:


> It's only 7!*3^6 = 3,674,160 positions.



(3^7 * 8!)/24 = (3^6 * 7!), you are correct. I forgot you have only 1/24th of the positions since there are no "centers" to orient with in the 2x2x2 world.



Meep said:


> As far as I know, it can't solve states optimally that quickly.



I've run Herbert Kociemba's code on my machine and it produces 20- and sub-20 move solutions (for cubes not scrambled to distance 20 positions) in a blink of an eye. I could be mistaken however.




Meep said:


> Why don't you just upload it to some free image hosting site (like imgur) and link to it here?



I have.

My offer was to let any coders who wanted to partake in this project to run their code on my machine, and/or view/run their own 5x5x5 scrambles on my 5x5x5 solver. For example, go to TeamViewer.com and download their app, enter *392895346* as the "Partner ID" for my machine, and *pd425k *as the password, and there it is.


----------

