Confused clock face puzzle

Question

There is a clock face with the correct (target) numbers written in circles. But somebody confused the clock face and created a crazy clock with numbers written in ellipses.

Your task is to repair the clock face by moving individual numbers one by one around the clock's perimeter and also using the four drawn lines that form a cross. In the center of the cross there is an initial empty place. The 12 numbers and the empty place form 13 connected fields.

How many and which moves do you need to repair the clock by moving the numbers according to the rules above?

(Resembles a bit Loyd's fifteen, there are many permutations available so using brute force algorithms does not seem to work. I am also quite interested if an algorithm for solving this puzzle can be found, so a strategy for solving it would be handy. I have not solved it yet but I suppose that a simple solution exists.)

---

I have added to GitHub a small app that allows interactively solving the puzzle. https://github.com/Karluzo/ConfusedClock. There is .exe file WindowsFormsApplication1.exe .NET 4.5, Windows (I did not name it well...) - there you can see, how I try to solve it. It seems to me that there are always 24 ways to go (12 clockwise and 12 counterclockwise). But I might be mistaken. Yes, I am mistaken, I have simplified it too much. A new version with free movement on the GitHub as WindowsFormsApplication2.exe

---

I'll try to add the most accurate translation I am able to produce of the original text:

The picture shows a clock face with numbers inscribed into rings. Above them the clock face in an oval is confused (1-12). Your task is to repair the clock face by moving the single digits along lines - around the perimeter and along the cross with an empty ring in the middle - consists of 13 fields with links. How many moves it takes to make a crazy clock face fixed to normal hours. Describe the steps to solve the puzzle.

(I guess single digits does not mean, that you move 1 and 0 of 10 separately). As long as I did not solve the puzzle myself I do not feel to be the right person to interpret it, but I will try to find the true meaning of the text. On the GitHub there is also the non-translated version

Answer 1

Here's a solution which I believe is optimal - 35 moves overall:

1. Move the number 3 into the centre

2. Move fifteen numbers clockwise (i.e. move the number 2 to the empty slot, then the number 12 to the empty slot, and so on fifteen times)

3. Move the number 3 out of the centre (upwards)

4. Move the number 12 into the centre

5. Move six numbers anticlockwise (in the same fashion as step 2, but in the other direction)

6. Move the number 12 out of the centre (to the left)

7. Move the number 3 into the centre

8. Move three numbers anticlockwise

9. Move the number 3 out of the centre (to the right)

10. Move the number 12 into the centre

11. Move three numbers anticlockwise

12. Move the number 12 out of the centre (upwards)

I solved it with a computer program. The algorithm is pretty naive - at every step I build a list of possible states using all possible changes to the states of the last step. Of course, only the following 4 things are considered steps - moving a number into the centre, if it's free (one of 4 options); moving out of the centre, to the free slot; moving 3 numbers clockwise, if possible; or moving 3 numbers anticlockwise, if possible.

Also, I remember the previous step for each state, so I don't just retract it. And, once I've built the whole list of possible states I discard any duplicates before moving on to the next step.

At the final step I have 781086 possible states, one of which is the solution.

Here's the code. To use just run solve():

(Now runs a bit quicker - about 13 seconds on my computer...)

(Now runs on Python 3.5 too. Thanks to Jonathan Allan.)

# A state is made of (by index):
# 0: the numbers around the clock (starting from the top),
# 1: the number in the centre of the clock,
# 2: the empty slot index (-1 for centre),
# 3: the chain of previous steps made,
# 4: from which slot we moved from/to centre (when relevant).
INIT_STATE = ([1, 12] + [i for i in range(2, 12)], -1, -1, [-1], [-1])
SOLVED = [12] + [i for i in range(1,12)]

MOVE_TO_CENTRE = 0
MOVE_FROM_CENTRE = 1
MOVE_CLOCKWISE = 2
MOVE_ANTICLOCKWISE = 3

def get_new_state(state, move, slot=None):

    if move == MOVE_TO_CENTRE:
        new_state = (state[0][:], state[0][slot], slot, state[3] + [move], state[4] + [slot])
    elif move == MOVE_FROM_CENTRE:
        new_state = (state[0][:], -1, -1, state[3] + [move], state[4] + [state[2]])
        new_state[0][state[2]] = state[1]
    elif move == MOVE_ANTICLOCKWISE:
        new_state = (state[0][:], state[1], (state[2] + 3) % 12, state[3] + [move], state[4] + [-1])
        if state[2] == 9:
            new_state[0][9:] = state[0][10:12] + state[0][:1]
        else:
            new_state[0][state[2]:(state[2] + 3) % 12] = state[0][(state[2] + 1) % 12:(state[2] + 4) % 12]
    elif move == MOVE_CLOCKWISE:
        new_state = (state[0][:], state[1], (state[2] - 3) % 12, state[3] + [move], state[4] + [-1])
        if state[2] == 0:
            new_state[0][0] = state[0][11]
            new_state[0][10:] = state[0][9:11]
        else:
            new_state[0][(state[2] - 2) % 12:(state[2] + 1) % 12] = state[0][(state[2] - 3) % 12:state[2]]
    return new_state

def get_next_step_options(state):

    options = []
    if state[2] == -1:
        for slot in range(0, 12, 3):
            if not ((state[3][-1] == MOVE_FROM_CENTRE) and (state[4][-1] == slot)):
                options.append(get_new_state(state, MOVE_TO_CENTRE, slot))
    else:
        if state[3][-1] != MOVE_TO_CENTRE:
            options.append(get_new_state(state, MOVE_FROM_CENTRE))
        if state[3][-1] != MOVE_CLOCKWISE:
            options.append(get_new_state(state, MOVE_ANTICLOCKWISE))
        if state[3][-1] != MOVE_ANTICLOCKWISE:
            options.append(get_new_state(state, MOVE_CLOCKWISE))
    return options

def print_instructions(final_state, initial_state=INIT_STATE, print_states=False):

    state = initial_state
    for move, info in zip(final_state[3][1:], final_state[4][1:]):
        if move == MOVE_TO_CENTRE:
            print("Move the number %d into the centre" % state[0][info])
        elif move == MOVE_FROM_CENTRE:
            print("Move the number %d out of the centre" % state[1])
        elif move == MOVE_ANTICLOCKWISE:
            print("Move three numbers anticlockwise")
        elif move == MOVE_CLOCKWISE:
            print("Move three numbers clockwise")
        state = get_new_state(state, move, info)
        if print_states:
            print("New state:", state)
    print()

def solve(state=INIT_STATE):

    states = [state]
    while True:
        print(len(states))
        new_states = []
        for curr_state in states:
            new_states.extend(get_next_step_options(curr_state))
        states = new_states
        del new_states
        solutions = [s for s in states if s[2] == -1 and s[0] == SOLVED]
        if len(solutions):
            print("\nFound %d solutions!\n" % len(solutions))
            for solution in solutions:
                print_instructions(solution)
            return

Answer 2

I also wrote a quick solver to get a

$35$ move, optimal solution

Which yields

       1
    11  12
  10       2
 9           3
   8       4
     7   5
       6


    11  12
  10       2
 9     1     3
   8       4
     7   5
       6

      11
        12
  10       2
 9     1     3
   8       4
     7   5
       6

      11
    10  12
           2
 9     1     3
   8       4
     7   5
       6

      11
    10  12
   9       2
       1     3
   8       4
     7   5
       6

      11
    10  12
   9       2
 8     1     3
           4
     7   5
       6

      11
    10  12
   9       2
 8     1     3
   7       4
         5
       6

      11
    10  12
   9       2
 8     1     3
   7       4
     6   5


      11
    10  12
   9       2
 8           3
   7       4
     6   5
       1

      11
    10  12
   9       2
 8     3
   7       4
     6   5
       1

      11
    10  12
   9
 8     3     2
   7       4
     6   5
       1

      11
    10
   9      12
 8     3     2
   7       4
     6   5
       1


    10  11
   9      12
 8     3     2
   7       4
     6   5
       1

       3
    10  11
   9      12
 8           2
   7       4
     6   5
       1

       3
    10  11
   9      12
 8     1     2
   7       4
     6   5


       3
    10  11
   9      12
 8     1     2
   7       4
     6
       5

       3
    10  11
   9      12
 8     1     2
   7
     6   4
       5

       3
    10  11
   9      12
 8     1
   7       2
     6   4
       5

       3
    10  11
   9      12
 8           1
   7       2
     6   4
       5


    10  11
   9      12
 8     3     1
   7       2
     6   4
       5

      11
    10
   9      12
 8     3     1
   7       2
     6   4
       5

      11
    10  12
   9
 8     3     1
   7       2
     6   4
       5

      11
    10  12
   9       1
 8     3
   7       2
     6   4
       5

      11
    10  12
   9       1
 8     3     2
   7
     6   4
       5

      11
    10  12
   9       1
 8     3     2
   7       4
     6
       5

      11
    10  12
   9       1
 8     3     2
   7       4
     6   5


      11
    10  12
   9       1
 8     3     2
   7       4
         5
       6

      11
    10  12
   9       1
 8     3     2
           4
     7   5
       6

      11
    10  12
   9       1
       3     2
   8       4
     7   5
       6

      11
    10  12
           1
 9     3     2
   8       4
     7   5
       6

      11
        12
  10       1
 9     3     2
   8       4
     7   5
       6


    11  12
  10       1
 9     3     2
   8       4
     7   5
       6

      12
    11
  10       1
 9     3     2
   8       4
     7   5
       6

      12
    11   1
  10
 9     3     2
   8       4
     7   5
       6

      12
    11   1
  10       2
 9     3
   8       4
     7   5
       6

      12
    11   1
  10       2
 9           3
   8       4
     7   5
       6

In finding the solution it built all $5,379,522$ unique states reachable using up to the number of moves required (including the start state; stopping once the solved state was found). Each state is saved with a reference to the state from which it was reached, which allows the print of the path taken.

Python code

INIT_STATE = (None, (1,12,2,3,4,5,6,7,8,9,10,11))
SLVD_STATE = (None, (12,1,2,3,4,5,6,7,8,9,10,11))

def solution():
    slnDict = initSlnDict()
    depth = 0
    while 1:
        depth += 1
        incrSlnDict(slnDict)
        if foundSln(slnDict, depth):
            break
    printPath(slnDict, depth)

def iterStates(state=INIT_STATE):
    if state[0] is None:
        for i in range(0, 12, 3):
            yield (state[1][i], tuple(state[1][j] if j != i else None for j in range(12)))
    else:
        i = state[1].index(None)
        im = (i-1)%12
        ip = (i+1)%12
        yield (state[0], tuple(state[1][ip] if i==j else None if ip==j else state[1][j] for j in range(12)))
        yield (state[0], tuple(state[1][im] if i==j else None if im==j else state[1][j] for j in range(12)))
        if i % 3 == 0:
            yield (None, tuple(state[1][j] if j != i else state[0] for j in range(12)))

def printState(state):
    s = ['' if state[0] is None else state[0], ['' if state[1][i] is None else state[1][i] for i in range(12)]]
    print('''      {0:>2}
    {1:>2}  {2:>2}
  {3:>2}      {4:>2}
{5:>2}    {6:>2}    {7:>2}
  {8:>2}      {9:>2}
    {10:>2}  {11:>2}
      {12:>2}'''.format(s[1][0], s[1][11], s[1][1], s[1][10], s[1][2], s[1][9], s[0], s[1][3], s[1][8], s[1][4], s[1][7], s[1][5], s[1][6]))

def initSlnDict():
    return {0: {INIT_STATE: None}}

def incrSlnDict(slnDict):
    d = max(slnDict)
    nd = d + 1
    slnDict[nd] = dict()
    for fromState in slnDict[d]:
        for toState in iterStates(fromState):
            if not any(toState in e for e in slnDict.values()):
                slnDict[nd][toState] = fromState

def foundSln(slnDict, depth=None):
    if depth is None:
        for depth, dDict in slnDict.items():
            if SLVD_STATE in dDict:
                return depth
        return False
    else:
        return SLVD_STATE in slnDict[depth]

def printPath(slnDict, depth=None, state=SLVD_STATE):
    if depth is None:
        depth = foundSln(slnDict)
    if depth is False:
        print(None)
    else:
        s = state
        res = [state]
        while depth > 0:
            s = slnDict[depth][s]
            res.append(s)
            depth -= 1
        for s in res[-1::-1]:
            printState(s)
            print('')

Answer 3

We start at position $(1, 12, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11)$

Here are the steps that can give one very unoptimized solution :

Shift the top left corner in CW direction by 1 notch.
this means : place 1 in center, blank goes CCW from North to West, which means that the numbers in the quarter of circle go CW, then put 1 back in blank.
We now have $(11, 12, 2, 3, 4, 5, 6, 7, 8, 1, 9, 10)$

Shift East block CW (place 6 in center, every other number in east block go 1 notch CW)
We now have $(6, 11, 12, 2, 3, 4, 5, 7, 8, 1, 9, 10)$

Shift South block 1 notch CW (place 1 in center, every south block go 1 notch CW)
We now have $(6, 11, 12, 1, 2, 3, 4, 5, 7, 8, 9, 10)$

Now place 6 in center, and make 5 complete CW turns (until the blank is on north and is between 5 and 7)
Place 6 on top.
We now have $(6, 7, 8, 9, 10, 11, 12, 1, 2, 3, 4, 5)$ which is not the solution, but it is 6 notches away (180° rotation), which seems much more favorable.

All we have to do now is swapping the numbers in the right place :
Put 12 in the center, make 5.5 full turns in either direction, and place 12 in North.
We now have $(12, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11)$

Let's count the moves :

Shift NorthWest (1) : $+5$ (1 move to put in center, 3 to shift the others numbers, and 1 move to put back in place the number from the center.)
Shift East (6) : $+8$
Shift South (1) : $+8$
5 turns (6) : 60 + 2 : $+62$
5.5 turns (12) : 66 + 2 : $+68$
This makes a total of $145$ moves.

I think that shorter solutions can be found by bruteforcing.

Answer 4

Sorry for no visuals, I'll try to add some later.

EDIT: Counted 76 moves

The solution is rather lengthy:

EDIT: Updated, I seem to have written some steps wrong by accident. Bold steps were changed.

1. Move 1 to the centre.
2. Move 12, 2, 3 counter-clockwise one step.
3. Move 1 to the right.
4. Move 12 to the centre.
5. Move 9, 10, 11 clockwise one step.
6. Move 12 to the left.
7. Move 1 to the centre, then move 2, 3, 11 clockwise one step.
8. Move 12, 9, 10 clockwise one step, and move 1 to the left.
9. Move 2, 3, 10, 11 counter-clockwise one step so that 11 is on top, leaving the empty space in the middle.
10. Move 1 to the centre, and move 12, 9, 11 counter-clockwise one step.
11. Move 1 to the top.
12. Move 1, 2, 3, 10 clockwise one step.
13. Move 12, 9, 11 clockwise one step.
14. Move 10 to left space.
15. Move 3 to centre. Move 11, 1, 2 clockwise once step, then move 3 to the top space.
16. Move 10 to the centre.
17. Move 12, 9, 3 counter-clockwise one step.
18. Move 10 to the top space.
19. Move 12 to the centre, move 9, 3, 10, 11, 1, 2 counter-clockwise one step.
20. Move 12 to the right.
21. Move 9 to the centre.
22. Move 3, 10, 11 counter-clockwise one step.
23. Move 9 to the top.
24. Move 12 to the centre.
25. Move 9, 1, 2 clockwise one step.
26. Move 12 to the top.
27. Move 3 to the centre.
28. Move 10, 11, 12, 9, 1, 2 counter-clockwise one step.
29. Move 3 to the right.
30. Move 9 to the centre.
31. Move 10, 11, 12 clockwise one step.
32. Move 9 to the left.

Answer 5

Somewhat more general answer, since the specifics are well taken care of. Warning: Math ahead.

Label each of the positions around the clock from 1 to 12, so that in the 'correct' clock 1 is at position 1, 2 is in position 2 and so on. Label the center of the clock '0'.

Note that any sequence of moves which could possibly put the clock into the correct position (assuming the center of the clock starts out empty) can be divided into a number of segments, each of which takes the form:

1. Move number at 3, 6, 9, or 12 to center.

2. Rotate every number around the circle exactly once either clockwise or counterclockwise, leaving the same space at 3, 6, 9, or 12. Repeat zero to five times.

3. Rotate a group of three, six, nine, or twelve numbers adjacent to the position you just moved the one space either clockwise or counterclockwise.

4. Return center number to the gap, which will have shifted three, six, nine or twelve spaces around the board, therefore still being reachable from the center.

Note that, if we write out the list of numbers from position 1 to position 12, for example (12, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 1) in the question's starting case, moves of this kind can do one of three things:

If we return the center number to the same gap, then we have just cycled the rest of the list around. For example, in the question's starting position, if we move the 1 into the center, shift the other numbers clockwise twice and put the one back at position 12, we get:
(10, 11, 12, 2, 3, 4, 5, 6, 7, 8, 9, 1).

If we return the center number to a different gap without rotating every number, then we have shifted the numbers between the two gaps (direction depending on the direction we rotate). For example, putting one into the center, shifting 12, 2, and 3 counterclockwise and moving 1 to the newly opened position 3 gives us:
(2, 3, 1, 4, 5, 6, 7, 8, 9, 10, 11, 12).

If we do both, we combine the two effects, shifting all the numbers and then just the ones in between. For example, if we move one to the center, shift everything clockwise four times, then put the gap at position 6 by shifting the numbers at 6, 5, 4, 3, 2, and 1 counterclockwise once, we go from:
(12, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 1)
to
(8, 9, 10, 11, 12, 2, 3, 4, 5, 6, 7, 1)
to
(9, 10, 11, 12, 2, 1, 3, 4, 5, 6, 7, 8)
Note that this is just a combination of the other two types.

Now let's do a bit of math- specifically, let's look at Permutations.

We can think of our lists as being a permutation written in cycle notation, and our sequences of moves as being more permutations applied to the existing one. As a couple examples:

The moves we make in the first example of the above section can be written in cycle notation as the permutation:
(10, 1, 12)

The moves we make in the second example of the above section can be written as the permutation:
(12, 1, 4)

The moves in the third example can be written as a combination of:
(8, 1, 12) and
(1, 8, 3),
which is just:
(12, 3, 1)

More generally (proof not hard, but left to reader for brevity), we can say that:

Moves of the first kind where we shift $n$ numbers clockwise result in permutations of the form $(a, b, c)$ where $a$ is the number moved to the center, $b$ is the number that was immediately clockwise to it initially, and $c$ is the number that was $n$ spaces counterclockwise to it initially (and ends up immediately clockwise to it after the move). Counterclockwise is similar.
Moves of the second kind where we move the number $a$ at position $m$ to position $n$, rotating numbers that are clockwise from position $n$, where $n, m$ are 3, 6, 9, or 12 and $n \neq m$, give permutations of the form $(a, b, c)$ where $b$ is the number at $m$ and $c$ is the number immediately clockwise from $n$. Counterclockwise is similar.

Note that a property of permutations is that they can be decomposed into transpositions. In our case, this decomposition is especially simple:

$(a, b, c)$ becomes $(a, b)(a, c)$

A word of caution- since permutations have no set starting position, and for example (1, 2, 3) (2, 3, 1) and (3, 1, 2) are all the same, we need to be cautious in finding solutions- it is not sufficient that the end result of the permutations is (1, 2, 3, 4... 10, 11, 12), it must also be the case that the number 12 is at position 12, etc. To ensure this is possible, given our moves defined above (A rigorous proof is again not hard, but omitted for the sake of brevity):

Even if $(a, b, c)$ does not correspond to some valid move of the first type, note that for any $d$ it is true that $(a,b,d)(a,d,c) = (a,b,c)$, and for any $e,f,g$ it is true that $(e,f,g)(a,b,d)(e,g,f)(a,d,c) = (a,b,c)$. Additionally, if $(e,f,g)$ is a valid move of any kind, or if there is an equivalent set of moves which ends by moving $e$ to position 3, 6, 9 or 12, then once $(e,f,g)(a,b,d)$ is applied $(e,g,f)$ is guaranteed to be valid as long as none of $a,b,d$ are equal to $e,f,g$.

In particular for the given starting set (proving Angkor's result, because why not):

Applying (1,12,2) (a type 1 move) would instantly fix the order, as noted by Sechiro. This is equivalent to (12,2,1), which would only work if 12 was already at the top with a 2 next to it, which is equivalent to (12,2,9)(12,9,1), which is the same as (3,4,11)(12,2,9)(3,11,4)(12,9,1) if (3,4,11) is a valid type-2 move since it would ensure the conditions of (12,2,9) are met. It isn't valid since 11 isn't at 3, 6, 9 or 12, but (3,4,2)(3,2,11) at long last is valid, and is equivalent to it, so the full sequence (3,4,2)(3,2,11)(3,4,11)(12,2,9)(3,11,4)(12,9,1) keeps the order of (1,12,2), while ensuring 12 ends up at the top where it belongs.

This method could stand some fine tuning as it still relies a bit on intuition and while it happens to come across an optimal solution in this case I can't think of a reason why it should in general, but it generalizes across any starting or ending position and it should generalize easily with some proof finagling across any layout of clock.

Answer 6

Literal thinking solution:

1. Put the 1 at the center of the clock.
2. Move the 12, and every other number (so anticlockwise). And move the 12 again. At this point you've moved each number once beside the 12 that you moved twice. At this point you should have that:

3. Move the 1 up.
4. take the clock off the wall.
5. Put a new adhesive at the back under the 12 and remove the one under the 1.
6. Put the clock back on the wall.

Answer 7

I must be missing something... Is this the answer?

1. Slip the 1 down into the center spot.
2. Move the 12 anticlockwise one space.
3. Rotate the outer circle anti-clockwise one notch (so now the vacant circle is at the 12 o'clock position).
4. Move the 1 from the center up into the vacant circle.
5. Finally, rotate the outer circle clockwise one notch.

That should end up with a correct clock face...

Aha! I was missing something... Look at comments :-)