# OptClock - optimal Rubik's Clock solver



## qqwref (May 25, 2014)

OptClock is a new program to optimally solve the Rubik's Clock. It can solve any position in seconds on my machine, and it can also generate and solve thousands of random positions in a row, and then display statistics. I came up with the algorithm and wrote the original C++ program, and Ben Whitmore (ben1996123) added a GUI.

Download at mzrg.com/rubik/optclock/optclock.rar or mzrg.com/rubik/optclock/optclock.zip. There is a GUI version, two non-GUI versions with source code, and a readme file.

To run the GUI version you will need QtCore4.dll and QtGui4.dll; the other versions will run standalone. Download here.


----------



## 10461394944000 (May 25, 2014)

So far we've sub-optimally solved millions of scrambles and haven't been able to find a depth 12 position. The average optimal depth seems to be about 9.4.


----------



## Deleted member 19792 (May 25, 2014)

Hooray for optimal clock solves!


----------



## qqwref (May 25, 2014)

10461394944000 said:


> So far we've sub-optimally solved millions of scrambles and haven't been able to find a depth 12 position. The average optimal depth seems to be about 9.4.


Yeah, speaking of statistics, here's 100,000 optimal solves I did:

```
5	2
6	22
7	673
8	7898
9	40977
10	47959
11	2469
Average: 9.43579
```


----------



## Jakube (May 25, 2014)

Nice solver. 

I programmed an optimal clock solver last summer. I'll check, If I can find it anywhere. But If I remember correctly, it was a bit slower than OptClock. I also solved a bunch of random scramble and got the same result, no position required more than 11 moves. 

By the way, I can't get the gui or the stats to run. I downloaded the 4 dlls (libgcc_s_dw2-1.dll, libstdc++-6.dll, QtCore4.dll and QtGui4.dll). Now when I start the gui, ,nothing happens. And the stats crashes, after I enter the searching depth, but no error message. otpclock.exe works however.


----------



## Renslay (May 25, 2014)

I am surprised that there is no God's number or full statistics for the number of positions for each distances for this puzzle.
Maybe this is because the high number of possible postions? How many positions there are? (I probably could calculate it, I'm just too lazy...)


----------



## yoinneroid (May 25, 2014)

Renslay said:


> I am surprised that there is no God's number or full statistics for the number of positions for each distances for this puzzle.
> Maybe this is because the high number of possible postions? How many positions there are? (I probably could calculate it, I'm just too lazy...)



12^12?


----------



## Jakube (May 25, 2014)

yoinneroid said:


> 12^12?



No, it's 12^14 = 1.28 * 10^15. There are 9+9 = 18 little clocks, and the 4 corner clocks on the front are mechanically linked with the 4 corner clocks on the back. So only 14 clocks are free. Any position of these clocks is possible.


----------



## LNZ (May 25, 2014)

According to Jaap's puzzle site for the Rubik's clock, God's number is 13.

Jaap's puzzle site describes the mathematics of this puzzle well.


----------



## Jakube (May 25, 2014)

No, it only says, that every scrambled clock can be solved in 13. So 13 is only a upper bound.


----------



## ryanj92 (May 25, 2014)

Thanks for this, qq and Ben! Will have a look at optimal solutions at some point and see how my efficiency fares up


----------



## irontwig (May 25, 2014)

Renslay said:


> I am surprised that there is no God's number or full statistics for the number of positions for each distances for this puzzle.



Well, it's barely a puzzle.


----------



## Renslay (May 25, 2014)

irontwig said:


> Well, it's barely a puzzle.



Define "barely".


----------



## Jakube (May 25, 2014)

Funny "bug"?

If you want to solve the solved state optimally, it finds the basic solution instantly (0+0), but then takes 1.2 seconds to assure, that there is no shorter solution.


----------



## whauk (May 25, 2014)

Jakube said:


> No, it's 12^14 = 1.28 * 10^15. There are 9+9 = 18 little clocks, and the 4 corner clocks on the front are mechanically linked with the 4 corner clocks on the back. So only 14 clocks are free. Any position of these clocks is possible.


So the number of positions is quite high? However the number of symmetries should be very high, too. There should be 16 rotation/mirror symmetries, 2 time inversion symmetries and the 14 free clocks must take some value twice. My intuition tells me, one should be able to exploit this fact in another symmetry. (I could be wrong)

One more: Turning a wheel can be viewed as an element in the Z/12Z group. There are isomorphisms of this group to itself, that are: multiplying every element by a number, that is co-prime to 12. (1, 5, 7, 11 are the only ones I think). Having thought about that, time inversion is just multiplication by 11.

Putting all these together yields: 16*4=64. Assuming the number of symmetry-invariant positions is very small, the remaining interesting positions add up to: ~2*10^13. Did I miss some symmetries?

Also, when reducing the number of states for every single clock, can we find out some god's numbers there?


----------



## yoinneroid (May 25, 2014)

Jakube said:


> No, it's 12^14 = 1.28 * 10^15. There are 9+9 = 18 little clocks, and the 4 corner clocks on the front are mechanically linked with the 4 corner clocks on the back. So only 14 clocks are free. Any position of these clocks is possible.



oh yeah, somehow I forgot to count the 2 center clocks >.>


----------



## qqwref (May 25, 2014)

Jakube said:


> Funny "bug"?
> 
> If you want to solve the solved state optimally, it finds the basic solution instantly (0+0), but then takes 1.2 seconds to assure, that there is no shorter solution.


That's not really a bug, just a result of how this particular algorithm works. It will loop through the 12^8 possible phase 1 positions no matter what, although it discards all of them immediately.

Do you remember what your algorithm was to find optimal solutions?


Oh yeah, and I ran 50 million scrambles with upper bound of 11, but could not find any 12s 


Spoiler





```
Batch solving complete.
Depth Positions
0: 0
1: 0
2: 0
3: 0
4: 6
5: 69
6: 1446
7: 20099
8: 190078
9: 1263622
10: 6234395
11: 42290285
12: 0
13: 0
Average depth: 10.8116
Took 21196.5s.
```


----------



## Jakube (May 25, 2014)

qqwref said:


> Do you remember what your algorithm was to find optimal solutions?



If I remember correctly, it was very straightforward. I just had a prune table for the cross. 
Solved one cross with the 15 possible moves, then solved the cross + edges on the other side with the other 15 moves. And I used the fact, that moves are commutative. 
My algorithm wasn't a 2-phase solver. The first solution I found, was the optimal one. 

The more I thing about my solver, the more slower it gets. A few hours ago, I thought, that it solved 11 move solutions in half a minute. At the moment I think, that it took up to 5 minutes. 
I will search for my code and test it. I didn't optimize it in any way. I thought about a clock solver today, and I have quite a lot of improvements and ideas. Maybe I'll improve my program in the next days.


----------



## 10461394944000 (May 26, 2014)

50 million more suboptimal solves:


```
3: 0
4: 5
5: 86
6: 1455
7: 19884
8: 190928
9: 1262901
10: 6234657
11: 42290084
12: 0
```


----------



## rokicki (Jun 1, 2014)

Can I get the README file? I'm on a Mac, so I can't run the program, and I don't have a rar unarchiver.


----------



## 10461394944000 (Jun 1, 2014)

rokicki said:


> Can I get the README file? I'm on a Mac, so I can't run the program, and I don't have a rar unarchiver.





Spoiler



## OptClock Readme ##

== What is this? ==

OptClock is a program for optimally solving Rubik's Clock positions. It is Copyright 2014 by Michael Gottlieb and Ben Whitmore. Michael Gottlieb developed the solving algorithm and wrote the non-GUI version of the program, while Ben Whitmore created the GUI in Qt.

The exe files are compiled for Windows, but if you are not using a Windows system you may want to recompile. 

== Notation Used ==

There are two types of notation used for the program: one for scrambles and one for moves.

Scrambles are just lists of 14 integers. Each number represents the "hour" displayed by one of the clock pieces, and any list of 14 integers is a valid scramble. Usually people use 1-12 for each number but this is not required. The order of the numbers is as follows:
1 2 3 . 10 .
4 5 6 11 12 13
7 8 9 . 14 .
(front) (back)
The dotted numbers do not need to be entered since their values are determined by the front corners. Also, when turning from front to back, make sure to turn so that the top of the puzzle remains on top (so 10 is opposite 2).

Moves look something like UUDU u3'. The uppercase part (UUDU) is the state of the 4 pins, in the order top-left, top-right, bottom-left, bottom-right. U means up (pin towards you) and D means down (pin away from you). If the lowercase letter is a u, it means to turn a corner that is next to a U pin; if the lowercase letter is a d, it means to turn a corner next to a D pin. The number tells you the amount to turn, and is just like the notation for cubes: the letter by itself means to turn clockwise by 1 increment; the letter with a number means to turn clockwise by that number of increments; and a ' sign always means to do the same turn counterclockwise instead of clockwise. So in this case (u3') it means to turn a corner next to a U pin counterclockwise by 3 increments.

== Using the Program ==

There are two non-GUI versions: a normal version and a statistics version. The normal version is for solving individual scrambles: just enter in a scramble with the above notation, and it will be optimally solved for you. Enter "q" to quit the program. The statistics version is for solving many scrambles at once and reporting on how many moves they took. Enter in the number of scrambles and an upper bound, and the program will generate that many scrambles and solve them all, and then print some statistics. Every 100 scrambles a number will be printed to the screen so you can be sure it's still running properly.

A little note about the upper bound. Basically, the program will stop searching for solves when it finds a solve using no more than the upper bound number of moves. The higher the upper bound is, the faster the solver will run. If you set it to 0, it will only look for optimal solves.

With the GUI version, the features are pretty much the same, but it is a little different to use. To solve a given scramble, set up the scramble by clicking on the clocks, and then press the "Solve" button. The "Generate random scramble" button will generate a random position, and the "Reset" button will move the clocks back to solved. "Batch solver" works like the statistics version as explained above, although it will also let you run the solver with multiple threads (to speed up execution) and a custom priority level.

Note that all forms of the program will create and use a 3-megabyte tables file (phase2.table). Apart from the program itself, this is all the hard drive space it needs. If you ever lose this file it will just get regenerated the next time the program is run.

== The Solving Algorithm ==

Here I will discuss how the program actually finds optimal Clock solves, since as far as I know this is a pretty new feature. The program itself has a lot of optimizations and memoization, so even if you understand the theory it may be tricky to see out exactly what the code is doing.

The solving algorithm uses two phases. Consider the 9 clocks on each side of the puzzle; we can divide these into 1 center, 4 edges, and 4 corners. The first phase of the solution matches each face's center and edges into a "cross" of 5 clocks pointing the same way. The second phase then solves the corners and two crosses optimally. At a very high level, we can quickly figure out how long a phase-2 optimal solution is, so we just try every possible phase 1 solution and determine the best total movecount we can get, where total movecount is the sum of the phase 1 movecount and phase 2 movecount.

It saves time to separate the puzzle into two phases like this because the 30 possible moves can be split into moves useful for phase 1, and moves useful for phase 2. The 16 phase 1 moves are moves that affect the cross - that is, they move a face's center without moving all four of its edges. The 14 phase 2 moves, on the other hand, preserve both crosses. By design, phase 1 moves are not useful in phase 2 (they break the cross), and phase 2 moves are not useful in phase 1 (they do not affect the cross). So, since we can do the moves of a solution in any order, it is safe to assert that phase 1 moves are only used during phase 1, and phase 2 moves are only used during phase 2.

Phase 2 is simpler, so I'll discuss it first. Because we only have two crosses and four corners to deal with, there are only 12^6 positions - about 3 million. This is small enough that we can use a standard God's Algorithm loop to compute the optimal distance for each of these positions, and then store that in a table. Having the phase 2 distance in a table lookup is what makes the solver fast enough to be practical. For the two-phase algorithm we only need the number of moves, until we want to print a solution, and then we can just work backwards from the phase 2 position to find an optimal move sequence for this phase.

In phase 1, we have to try all solutions to see which ones end up with fast phase 2 solutions, so we can't just set up an optimal table. But there are 16 possible moves, so we have to be clever about it. I divided those 16 moves into two types: edge moves such as UUDD u, which only affect one edge (relative to the center), and corner moves such as UDDD u, which affect two edges (relative to the center). If we know how much we want to do each corner move, then since each of the 8 edge moves affects only one of the 8 edges, and they all must be the same as their center after phase 1, the amount of each edge move that we do is forced. So the only "degrees of freedom" we have for our phase 1 solution is the amount of each corner move that we use. There are 8 of those, with 12 possible angles for each, so there are only 12^8 phase 1 solutions! We can simply loop through those, and check the total movecount of each possibility. The best total movecount means the optimal solution.

Now, 12^8 is about 430 million, so of course we don't want to do too much computation for each one. We can quickly compute the phase 1 movecount by splitting it into a front and a back, each affected by 4 of the 8 corner moves. We can compute the number of moves on each side for every possible set of angles for those 4 moves (that is, two tables of size 12^4) and just add the relevant entries together to get the phase 1 movecount. Then, for phase 2, with a little math we can predict the positions of the crosses and corners for any given set of corner moves, and then plug that into our phase 2 table to get the phase 2 movecount. So the movecount for the whole puzzle is computed by indexing into a bunch of tables, and all we have to do is figure out the indexes.

To save some more time, it turns out we don't even need to look at phase 2 for most of the 12^8 possibilities. Suppose we have already seen an 11-move solution. Then, if we are trying a solution that already takes at least 11 moves in phase 1, we know there's no way it can be better than what we already have, and we can decide not to even check the phase 2 movecount. Phase 1 solutions can take up to 16 moves, so we can usually throw out the vast majority of them, saving a surprising amount of time.

In the end, most of this was only possible because the moves commute - you can do a set of moves in any order. A lot of the tricks I used wouldn't be possible or useful on a cube. Still, it's cool to add this to the list of puzzles that can be solved optimally! After this release, I'm going to see if I can find God's Number. Right now, it's looking like it's 11.


----------



## qqwref (Jun 1, 2014)

Here's a zip of the same files: http://mzrg.com/rubik/optclock/optclock.zip


----------



## rokicki (Jun 1, 2014)

Thanks! I'm happy to say that your source compiles and runs on Linux; I needed to
comment out windows.h and add cstdlib and then all is well.

I've got 64 distance-12 positions at this point (the two we know of, times 32 different
reorientations/multiplications). I wonder how many there are . . .


----------



## qqwref (Jun 1, 2014)

rokicki said:


> I've got 64 distance-12 positions at this point (the two we know of, times 32 different
> reorientations/multiplications). I wonder how many there are . . .


Don't forget you can multiply a scramble by 5 or 7 without changing its orientation  So you have group multiplication (x4), mirroring (x2), flipping (x2), and rotation (x4) for up to 64 positions from a non-symmetrical scramble.


----------



## rokicki (Jun 1, 2014)

qqwref said:


> Don't forget you can multiply a scramble by 5 or 7 without changing its orientation  So you have group multiplication (x4), mirroring (x2), flipping (x2), and rotation (x4) for up to 64 positions from a non-symmetrical scramble.



Right, but it turns out for the two positions we know, there is enough symmetry where this only gives us
32 distinct positions for each of our 2 root positions. If you can verify this for me I'd appreciate it.


----------



## qqwref (Jun 1, 2014)

You're right - I didn't even see the symmetry in Jakube's position at first. So yes, they should each have 32 equivalent positions.

I'm thinking we could do the same thing as Jakube did to prove there are no positions of at least length 13, to find all positions of at least length 12. I'd try it myself but I don't have you guys's source code, or enough RAM to do a 12^9 table anyway. It would work like this:


Spoiler



- Take all 7- or 8-move states of the back side and combine them with a solved cross on the front side
- Undo UUUU u=x5 in all 12 different ways, discard any positions with optimal length <8
- Undo UUdd u=x4 in all 12 different ways, discard any positions with optimal length <9
- Undo Uddd u=x3 in all 12 different ways, discard any positions with optimal length <10
- Undo dUdd u=x2 in all 12 different ways, discard any positions with optimal length <11
- Undo ddUd u=x1 in all 12 different ways, discard any positions with optimal length <12, we're done



I imagine there would be a LOT more positions at each stage than for proving God's Number, but at the end you would have a list of every 12-move position.

By the way, we should be able to compute the number of positions of depths <=5 by enumeration (there are at most 22950733806 at depth 5), and get pretty good estimates of depths 6-11 by just optimally solving lots of scrambles.


----------



## rokicki (Jun 1, 2014)

qqwref said:


> You're right - I didn't even see the symmetry in Jakube's position at first. So yes, they should each have 32 equivalent positions.



I found two more "base" distance-12 positions, so now we're at 4 base positions and 128 total positions.

The positions are:


```
2 4 2 6 1 6 3 10 3 5 3 10 3 9
2 0 4 1 5 1 2 0 4 0 6 7 11 0
2 5 2 11 2 11 9 0 9 4 5 7 5 9
8 11 8 1 6 1 5 4 5 2 6 4 6 1
```

Okay, I get your strategy now. That's surprisingly doable, I think. You need to
solve about 33 billion positions in the first stage.

I will mention it is always possible to solve the cross *and* any specific pair of
two diagonally opposite corners in only 6 moves.


----------



## qqwref (Jun 1, 2014)

It's pretty much just Jakube's approach with an extra move worth of leeway. If Jakube's approach for finding (a lack of) 13-move solutions is valid, this should be too. A generalized version of his original approach could be described something like 1+1+1+1+(1+8) => 1+1+1+(1+9) => 1+1+(1+10) => 1+(1+11) => (1+12) => 13, where we start with positions that require 13 moves in 6 steps (cross move 1 through cross move 5, and then the back 9), and combine two steps together in each step. If we ever combine two steps, and a position can be solved in fewer moves than we expect, we can discard that position because it will have a solution of under 13 moves. Of course, he ended up with no positions at the end, and in fact skipped some steps as unnecessary, but it's worth thinking about the whole thing.

Now with my approach the intuition is like this: 1+1+1+1+(1+at_least_7) => 1+1+1+(1+at_least_8) => 1+1+(1+at_least_9) => 1+(1+at_least_10) => 1+(at_least_11) => at_least_12. Whenever we combine two steps, we want the total movecount to be at least 12 (i.e. either 12 or 13) and that means anything that does not hit the above boundaries (at least 8, at least 9, ...) is a position that we can be sure doesn't require 12 moves no matter what we do in the un-combined steps. So initially we have all back-9 positions that can be solved in at least 7 moves, and when we combine with cross move 5, we need the resulting position to have an optimal solution of at least 8 moves in order for the whole thing to possibly require 12 moves (there are 4 cross move steps left, each of up to 1 move). So we combine all those at-least-7-move positions with the first cross move step and then discard anything that doesn't require at least 8 moves. Continue combining steps until the end, when we combine cross move 1 with the rest of the puzzle and discard everything requiring under 12 moves, and we are done.


----------



## rokicki (Jun 1, 2014)

Yep.

Just for confirmation (anyone want to check?) this is the count of states for solving one cross and four corners.


```
0: 1
1: 165
2: 12507
3: 555533
4: 15211818
5: 243997728
6: 1804523730
7: 2917922526
8: 177556344
```

I've got a number of irons on the stove, but I'll give it a shot.

For a full distance distribution, I really think the coset approach is a winner.
Maybe I'll give it a shot.


----------



## Jakube (Jun 1, 2014)

I can confirm this numbers. When I calculate the numbers from my reduced table, I'll end up with exactly the same. 

I will try your approach, qqwref. Since my 12-proof has nearly the same approach, I'll only have to change a few lines of code. But I guess, that the execution of the program will take much more time.


----------



## Jakube (Jun 1, 2014)

Quick update: 
I've written the necessary code for the distance-12-states, as suggested. But it is way too slow. 
- There are way too many 7 and 8 states for the full side. 
- Instead of solving the state suboptimal (as I did in my proof), here we have to solve them optimally. Therefore much slower. 
- I'm not sure, how many states 'survive' during each elimination, but I guess, they are too many (at least for the first 1-2 undo steps). 

summary: My program run for about 3 hours and only checked ~90.000 different 7/8-move-states. And there are more than 3.000.000.000 of them.


----------



## rokicki (Jun 2, 2014)

I've got my coset solver working, and it's solving 5.2B positions in about 200 seconds on one core.
That's about 25M optimal solves a second. I'm currently running the 9900 cosets on two desktops;
they should finish in a couple of days.

And I've found oodles and oodles of distance-12's. More results in a couple of days.


----------



## 10461394944000 (Jun 2, 2014)

rokicki said:


> That's about 25M optimal solves a second.



oh thats pretty fast


----------

