Jakube
Member
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.
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.