# God's Number for Clock found



## Jakube (May 31, 2014)

I just found the God's Number for Rubik's Clock and proved it. 
Each of the 12^14 (=1283918464548864) different possible states can be solved with *12 moves*. 

*God's number for Clock is 12.*

There are states, with cannot be solved with less than 12 moves and there is no state, which needs more than 12. 


I was acctually quite surprised by the result. Michael Gottlieb (qqwref) and Ben Whitmore (10461394944000) have solved 50.000.000 random states multiple times using their clock solver OptClock. All states were solvable in not more than 11 moves. I did the same thing with my own solver (not published yet) and got the same result. 

Only when I tried to prove 12 as upper bound, I accidentally ran into a few such state. They seem to be really rare. 

12 is a nice God's Number thought. It's the only number, that appears on the puzzle (18 times!) except the market year 1988. 


*Prove:* 

*Lower bound 12:*
A state that needs at least 12 moves is:
UUdd u=5, dUdU u=4, ddUU u=5, UdUd u=4, UUUd u=-1, UUdd d=1, dUdU d=-1, ddUU d=5, UUUd d=4, UddU d=6, dUUd d=5, ddUd d=-3
or in notation for OptClock: 2 0 4 1 5 1 2 0 4 0 6 7 11 0
So 12 is the lower bound for God's number. 

*Upper bound 13:*
You can always solve the cross on the front side with max. 5 moves. And the back side (all nine clocks) with max. 8 moves. Therefore 5 + 8 moves as upper bound. 
This was proven already by Jaap Scherphuis (Jaap's Puzzle Page - Rubik's Clock) and Milan Baticz. I confirmed this result by doing a iterative-deepening depth-first search. 

*Upper bound 12:*
If there is a state with 13 moves optimal, than a solution (there are much more) can be written as ddUd u=x1, dUdd u=x2, Uddd u=x3, UUdd u=x4, UUUU u=x5 + the 8 moves for the back side. x1, ... x5 are integers between 1 and 11. 
My idea was, to find for each of these 13-move solutions a shorter one. Therefore there cannot be a 13-move-optimal state. 
I took all 8-move states of the back side and combined them with a solved cross on the front side. A optimal solution for this is of course 8 moves. 
Then I undid the last move UUUU u=x5 in all 11 different ways and looked for optimal solutions. If one of the states has a <= 8 move solution, the whole solution would be <= 5 - 1 + 8 = 12. So if all 11 states have a <= 8 solution, the 13-move original state can be solved with <= 12 moves. This can be done surprisingly quite often. Only in a few hundred cases this doesn't lead to success. In this case I also undo the move UUdd u=x4 and Uddd u=x3, resulting in 11^3 = 1331 different states and I look for a <= 10 move solution for each of them. Therefore the original 13-move state can be solved in <= 5 - 3 + 10 = 12 moves. My program checked all those bad 8-move back sides and found for each possible 13-move state a <= 12 solution. Note: Undoing the last 3 moves might not be necessary. 

*Background:*
I build a clock solver about a year ago, but it was quite slow. Inspired by OptClock I decided to program a new, much faster, one. As it turned out, it's not only faster than my old one, it's even much faster than OptClock. It can find the optimal solution for more than 10 random clock states each in a second. And it finds sub-optimal solutions for an quite unbelieving number of states in a short time. It uses a very big lookup table (1,5 GB) and because of some unknown reason, the java program won't start, unless I allow it to use 4 GB RAM as heap memory. Therefore I would still recommend OptClock, if anyone want to have optimal solutions. 
Awoken by the speed of my program, I decided to set the lower bound of God's Number to 12. (I actually wanted to do this a year ago, but back then my solver was way too slow.)
It was kinda a nice coincidence, that I came across a 12 move solution. I wanted to find <= 12 move solutions for some really hard cases, and thought, that I also can look for <= 11 move solutions instead. 
I may release my program in the next days. I want to review and clean the code first.


----------



## qqwref (May 31, 2014)

Whoa! Nice job! I was thinking about how to do this myself, but didn't have a workable idea yet.



Jakube said:


> A state that needs at least 12 moves is: [...]2 0 4 1 5 1 2 0 4 0 6 7 11 0


Very cool. I just tested this myself and, indeed, it takes 12 moves. We actually ended up running over 150 million total random scrambles and didn't find a state like this. I wonder how many there are? (Would you want to work together to try to find the distribution table of God's Algorithm?)



Jakube said:


> As it turned out, it's not only faster than my old one, it's even much faster than OptClock. It can find the optimal solution for more than 10 random clock states each in a second. And it finds sub-optimal solutions for an quite unbelieving number of states in a short time. It uses a very big lookup table (1,5 GB) and because of some unknown reason, the java program won't start, unless I allow it to use 4 GB RAM as heap memory. Therefore I would still recommend OptClock, if anyone want to have optimal solutions.


I'm impressed, and this is certainly interesting to hear. I thought my approach was pretty fast, and maybe it can still be optimized, but yours sounds much faster still. 1.5 GB is a little over 2 * 12^9 bits, so would I be correct in assuming you are storing the optimal solutions for the corners plus one of the crosses? How long does it take to generate this table?


----------



## 10461394944000 (Jun 1, 2014)

thats pretty surprising


----------



## Coolster01 (Jun 1, 2014)

Awesome!


----------



## Jakube (Jun 1, 2014)

qqwref said:


> We actually ended up running over 150 million total random scrambles and didn't find a state like this. I wonder how many there are? (Would you want to work together to try to find the distribution table of God's Algorithm?)



Yes, they must be really really rare. I found the solution last night and during this night i solved a couple of 100.000.000 states sub-optimally. All these states seemed really hard to me. But I only found two 13-move states, until I aborted the program after 10 hours. 

I would like to work on a distribution table with you. But honestly, at the moment I have no idea, how to approach this. 



qqwref said:


> 1.5 GB is a little over 2 * 12^9 bits, so would I be correct in assuming you are storing the optimal solutions for the corners plus one of the crosses? How long does it take to generate this table?



Your correct. I saved the optimum solution length for each different states of one side (cross + corners). Because the inverse of a state has the same solution length a the normal state, I only need to save 7*12^8 entries. And each entry takes 4 bits. 
I also have a prune table for only the centers of one side. 
So my solver just solves the centers on front side, and checks the table, how much moves the back side takes. Then creates another solution for the front side, and so on. 

The generation of the table is surprisingly quite fast. It only takes about 10 minutes (if I assume that 8 is the max value). I initialize the table with 8s, then do a iterative-deepening depth-first search until depth 6, and finally go over the whole table and check for each 8, if it can reach a 6 with one move. If so, I update it to a 7.


----------



## rokicki (Jun 1, 2014)

Jakube said:


> I just found the God's Number for Rubik's Clock and proved it.



Wow! Congratulations! I just logged in to post that I found a distance-12 position, and saw this post.
Arghh!

Anyway, I've been following much the same path as you have been, programming-wise. Same
cross+corner table (although I didn't bother reducing mine by inverse so it's 5G entries). Same
optimal and sub-optimal solves (both are lightning fast). Solved 3B random states in under
12 moves each, then changed my random selection to favor positions I thought would be
more difficult. Same surprisingly rare, but found a distance-12.

I did not yet have a proof that 12 was always possible.

The distance 12 position I found is 2 4 2 6 1 6 3 10 3 5 3 10 3 9. This appears to
be significantly different than yours (mine has left/right symmetry, just by chance).

Building a distance distribution for this puzzle wouldn't be too hard but it would take a
fair amount of CPU time. I'd use a simple coset approach; the subgroup would be the
front cross (reduce this by symmetry), and the coset size would be 12^9 for the back.
Do all the back moves as a "prepass" and use a search that's just front-affecting-moves
only. I bet this would complete pretty quickly and it's trivially made parallel. You'd
need about 5.1B/4 or a bit more than a gigabyte of RAM for each run.


----------



## Renslay (Jun 1, 2014)

Congratulations!

How about writing a scientific paper about it? Like Tomas Rokicki's "Twenty-Two Moves Suffice for Rubik’s Cube" (The Mathematical Intelligencer, March 2010, Volume 32, Issue 1, pp 33-40)
http://link.springer.com/article/10.1007/s00283-009-9105-3


----------



## Sin-H (Jun 1, 2014)

yes, Jakob, write a paper. It's great to have a non-empty publication list already at an undergrad level


----------



## rokicki (Jun 1, 2014)

Yes, I think this should be worth a paper somewhere.

Some new results: I've got 17 (mod symmetry and rotations) total distance-12s
which expand out to 592 total distinct distance-12 positions at this point in time.
Most expand to just 32 positions, but there's a couple of ones that expand to 64
(so no symmetry) and one that only expands to 16.



Spoiler



10 11 10 9 10 9 3 3 3 4 6 7 6 10 --> 32
10 0 8 11 7 11 10 0 8 0 6 5 1 0 --> 32
10 1 10 7 10 7 9 0 9 8 1 11 1 9 --> 32
1 5 4 8 6 7 1 5 4 6 10 8 5 6 --> 32
0 1 6 8 2 8 1 0 1 5 4 10 4 6 --> 64
1 1 3 5 7 6 1 1 3 11 6 5 7 11 --> 16
1 1 5 2 11 2 1 1 5 6 9 8 7 6 --> 32
1 10 2 2 0 1 1 10 2 8 1 2 4 8 --> 32
1 11 1 3 9 3 10 0 4 1 3 9 3 0 --> 64
1 2 8 4 8 7 1 2 8 10 5 0 6 10 --> 32
3 0 3 4 10 4 3 3 3 0 8 2 8 3 --> 32
6 0 6 4 2 4 6 3 6 10 6 7 6 4 --> 32
1 11 7 9 3 9 10 0 4 1 3 9 3 0 --> 32
1 4 11 6 11 6 6 3 3 8 6 1 6 9 --> 32
10 0 8 11 7 11 10 0 8 0 6 5 1 0 --> 32
10 11 10 9 10 9 3 3 3 4 6 7 6 10 --> 32
4 1 6 3 10 0 4 1 6 10 8 4 9 10 --> 32



Also, I've looked at the symmetries of the cross.
I see a total of only 9906 distinct cross positions, up
to the various symmetries we have identified; can
someone confirm this? This means we only need
to solve 9906 cosets to calculate a full distance
table.

Further, I've got a coset solver running now; it
currently takes about 30min on one core to
compute distances for 12**9 positions, so that's
a rate of about 2.8M optimal solves a second.

With this coset solver we'll only need about 5000
core-hours to calculate the distance distribution.
I could run this on my home machines, or I can
inquire as to availability of an academic cluster
We may be able to speed up the coset solver, too.

Please PM me if you have interest. The coset solver
is tiny (174 lines and I'm sure I can cut that down)
and I'd be willing to share that code with anyone.
It does presently require 5.2MB of RAM to run.


----------



## qqwref (Jun 1, 2014)

Writing a paper would be cool, good luck with that. Please mention me somewhere.

5000 core-hours... 200ish core-days... that's a lot, but if you have access to any kind of big cluster it would be almost nothing. Maybe if you're nice to unsolved you could have him run it on his machine. I could contribute a bit but compared to serious compute hardware it'd be almost negligible


----------



## rokicki (Jun 1, 2014)

qqwref said:


> Writing a paper would be cool, good luck with that. Please mention me somewhere.
> 
> 5000 core-hours... 200ish core-days... that's a lot, but if you have access to any kind of big cluster it would be almost nothing. Maybe if you're nice to unsolved you could have him run it on his machine. I could contribute a bit but compared to serious compute hardware it'd be almost negligible



This is the first coset solver I've written for clock, and I may be able to speed it up a lot with SSE.

And yeah, it's a lot, but even a small academic cluster (think 8 nodes at 12 cores per node) would crank through this in
a couple of days.

Jakube got the main result, so he'll have to drive things paper-wise, and I hope he does.


----------



## rokicki (Jun 5, 2014)

Here's the final distance distribution for a 12-hour
Rubik's Clock. Much more later, once I get a chance.


```
0: 1
1: 330
2: 51651
3: 4947912
4: 317141342
5: 14054473232
6: 428862722294
7: 8621633953202
8: 101600180118726
9: 528107928328516
10: 613251601892918
11: 31893880879492
12: 39248
```


----------



## ryanj92 (Jun 5, 2014)

excellent work! 
so most scrambles are 9-10 moves optimal, but there are a bunch of 11's too... i might do a few reconstructions soon so i can check out my own movecount and see how it compares...


----------



## qqwref (Jun 5, 2014)

rokicki said:


> Here's the final distance distribution for a 12-hour
> Rubik's Clock. Much more later, once I get a chance.
> 
> 
> ...


Wow, great job! That cutoff at 12 is crazy, no wonder it was hard to find those positions.


----------



## Jakube (Jun 5, 2014)

So on average we would have to solve around 3.3*10^10 random states, until there appears a 12-move one. 

Great result.


----------



## 10461394944000 (Jun 6, 2014)

rokicki said:


> Here's the final distance distribution for a 12-hour
> Rubik's Clock. Much more later, once I get a chance.
> 
> 
> ...



do you have a list of the distance 12 positions?


----------



## Coolster01 (Jun 6, 2014)

Wow, it's more likely to get a distance 2 than 12 :O


----------



## rokicki (Jun 6, 2014)

Here's a quick writeup.

http://cube20.org/clock/

I plan to turn the code into a literate program and write things up
at a bit more length.

Some highlights:

There are distance-12 positions with six of the clocks already at zero.

The final program did more than 28 million solves a second (on
one core).

There are only 120 distance-12 positions for a clock with only 11 hours
(instead of 12).


----------



## qqwref (Jun 6, 2014)

Very cool write-up. As far as your idea of allowing the modulo to be changed, do you think prime numbers are easier or harder to optimally solve and/or analyze than highly composite numbers such as 12? My first attempt at an optimal solver was to use linear algebra (specifically a variant of Gauss-Jordan elimination) to try to answer, for any given set of moves, what positions would be generated by those moves. Since 12 is so composite I ran into some issues that I didn't end up properly resolving before I thought of the algorithm behind OptClock.

Oh, and what do you guys think the God's Number would be in qtm? It shouldn't be overly difficult to modify our existing programs to do qtm-optimal solutions (although depending on how you store stuff you may need more space in your pruning tables). I don't have time to do it right now, though.


----------



## rokicki (Jun 6, 2014)

Well, I'm not doing a lot of "math" here. The modulo reduction means that the reduction in
cosets is greater for prime clock sizes. The distance distributions going from, say, 10 to
11 to 12 seems to be fairly smooth; that is, it doesn't appear that there are significant
differences in the layout of the state space. (I haven't shared the distance counts for
values other than 12; that's on my list.)

I also tried working with the linear algebra in a modular field, but found that there were
just too many "choices" to make, too many ways to combine moves. But there is
probably a way to combine the math with the search to make the search more effective.

The QTM is interesting! As you say, I'd probably backtrack to an earlier version of the
code that uses byte values rather than packed 4-bit values in 5-bit fields; with that, as
you say, almost no code change would be required to solve cosets. The speed would
not be as great but it would be fast enough to gain some good insight. I suspect the
God's number would be several times higher (no surprise there) but I don't have a good
feel for how high. Definitely an interesting question.


----------

