21
$\begingroup$

I have recently started to spend time on http://www.puzzlopia.com/, which is a puzzle site. If you are not logged in, you are greeted with a "gear turning" puzzle, where you want all the "gears" oriented the same way.

Gear Puzzle

If, for whatever reason, you don't want to try it right now, I will describe it. The goal is to make all 9 gears oriented in the same direction (Those "dots" resemble the goal orientation). You can rotate all gears at the same time, 120 degrees in the same direction. However, you may also "lock" some gears, so they will not be affected while you orient the rest. Equivalenty, one may note that this is equivalent to rotating the locked gears in the oppoosite direction.

Rotate ex.

Here, I have locked the upper left gear. This consequently locks the two gears it's "pointing" at, to it's upper right and lower right.

Often, I have managed to orient all gears correctly, with the exception of one rebellious gear that won't comply. Trying to deliberately screw up the rest of the puzzle to tinker with the "dark forces" that prevent me from completing the puzzle, did not seem to help. After restarting about 5 times, I solved the puzzle in very few moves (The puzzle is randomly generated).

So, this is really interesting. Is this puzzle always solvable, no matter the starting orientations of the gears? Is there an algorithm to rotate just one specific gear? If it is not always solvable, what conditions are required to make it solvable? I suspect the dark magic of modular arithmetic is involved (I've never been good with that stuff).

(For those interested in wasting even more time in life, I'll note that I have found this site very enjoyable)

$\endgroup$
  • 2
    $\begingroup$ What happens if you lock the top gear? Is it locked by itself? $\endgroup$ – frodoskywalker Nov 21 '16 at 8:04
  • 2
    $\begingroup$ For those who have no access to the site: locking the top gear will lock the one on the right in the second row. This should be apparent from the first image, but not from the second where there is a rotation in progress. $\endgroup$ – Matsmath Nov 21 '16 at 8:11
  • 1
    $\begingroup$ A suggestion: calling these "gears" is confusing. They don't act at all like gears. The site refers to them as "pieces". $\endgroup$ – Tokkot Nov 21 '16 at 11:36
17
$\begingroup$

A random configuration of gears is solvable 1/3 of the time*

For details on what kind of configuration is solvable, refer to the claim after the image below.

Your hunch is right, we can use modular arithmetic here.

Let's mark each gear with a letter, starting with the top one as A, going from top to bottom, left to right, as in this figure:

Gears with letters

Let's denote with lowercase letters the state of each gear: 0 for correct position, 1 for the correct position rotated clockwise, 2 for the correct position rotated counter-clockwise.

So the image above has the following states:

a=2
b=1
c=1
d=2
e=0
f=2
g=0
h=1
i=1

Claim: An initial configuration is solvable if and only if the sum of states of gears A+F+I is the same as the sum of states of gears C+E+H (modulo 3) (proof comes later at the bottom)

This means, given the states of five gears from ACEFHI, there is only one possible state of the other gear that leads to a solvable state.

Now to the solution.

As OP noticed, and this is one important observation, locking one gear (and its connected gears) and then rotate all gears clockwise is the same as rotating those locked gears counter-clockwise followed by rotating all gears clockwise. Let's denote by capital letters the number of clockwise rotations required by the respective gear so that we reach a solved state.

Now we note what are the gears that are rotated if we rotate each gear:

A -> A C
B -> AB  E
C ->  BC  F
D ->  B D  G
E ->   CDE  H
F ->     EF
G ->     E G I
H ->      FGH
I ->        HI

Notice that rotating A+D+F+I once results in rotating all gears once. So we can safely assume that I=0 and later rotate all gears once to compensate for this.

Now we can identify that to make gear A correct, we can only influence it by turning gear A and B. So we need A + B = -a in order to make gear A to be in the correct state. Following that, we need to solve the following equations:

A+B = -a
B+C+D = -b
A+C+E = -c
D+E = -d
B+E+F+G = -e
C+F+H = -f
D+G+H = -g
E+H+I = -h
G+I = -i

Since we assumed I=0, we get G=-i. And, ignoring B+E+F+G=-e for a while, we can continue to solve the rest of the variables, working in modulo 3, to arrive at:

A = ( a-b+c      +g-h-i) mod 3
B = ( a+b-c      -g+h+i) mod 3
C = (-a+b+c-d          ) mod 3
D = (       d    +g-h-i) mod 3
E = (       d    -g+h+i) mod 3
F = ( a-b-c-d  -f-g-h+i) mod 3
G = (                -i) mod 3
H = (      -d    +g+h-i) mod 3
I = (0                 ) mod 3

For example, inputting the example above, we get:

A=0
B=1
C=1
D=0
E=1
F=2
G=2
H=1
I=0

Which means we don't need to rotate gear A, and we need to rotate gear B (and its connected gears) clockwise once (achieved by locking gear B and rotating counter-clockwise). Similarly, we need to lock gear F and rotate the rest clockwise once. Then at the end all the gears should be in the same state, but not necessarily in the correct state. One single global rotation might be required.

I can prove that the upperbound of the number of rotations is 8. As previously noted, rotating A, D, F, I rotates all gears exactly once. I'll prove that A+D+F+I <= 2. By pigeonhole principle, since there are 4 variables and 3 values (0, 1, 2), there are one value that is assumed by two of the variables. If it is 0, then two of the gears do not need rotation. So maximum 7 gears need rotations + maximum 1 from global rotation, so maximum 8 rotations. If it is not 0, then we can make them 0 by changing the global rotation direction. So maximum 8 rotations.

I don't know (so far) how to prove that a configuration that requires at least 8 rotations, so it might be that all solvable configuration can be solved in 7 rotations maximum. One example of initial state that my solution says it requires 8 rotations is this:

2 2 2 1 2 0 2 0 2

I believe following the solution above (plus the heuristic to ensure that at least two of A, D, F, I are zero) will always lead to the minimum number of rotations required, but I don't have proof (yet).


However, notice that previously we ignore one equation. Plugging in the values we obtained into the equation, we have:

B+E+F+G    = -e
-a+c-f+h-i = -e
c+e+h = a+f+i

This means the sum of the states of the gears C+E+H must equal to the sum of states of the gears A+F+I. And this is the only requirement for solvability.

You might notice that the state e is missing from the solution. This is because knowing a, c, f, h, and i gives a unique e for which there is a solution, and so the state of e is immaterial to our solution that already uses the other 8 states.


*However, in the Puzzlopia gear puzzle, as the other answer noted, I think it should always be solvable since the initial configuration is not random, but, similar to how one generate 15-puzzle (the sliding puzzle), the puzzle can be created by starting from a solved state and then performing a sequence of random rotations.


Code to calculate

Below I give the code in Python to calculate the solution as above, including the heuristics to minimize the number of rotations.

"""
21 Nov 2016
To solve the GEAR puzzle at puzzlopia (if not logged in)
"""

# Import statements
from builtins import input
from itertools import product

def count_zero(arr):
    return sum(1 if val==0 else 0 for val in arr)

def add_one(arr):
    return [(val+1)%3 for val in arr]

def compute(*vals):
    a,b,c,d,e,f,g,h,i = vals
    A = ( a-b+c      +g-h-i+9)%3
    B = ( a+b-c      -g+h+i+9)%3
    C = (-a+b+c-d          +9)%3
    D = (       d    +g-h-i+9)%3
    E = (       d    -g+h+i+9)%3
    F = ( a-b-c-d  -f-g-h+i+9)%3
    G = (                -i+9)%3
    H = (      -d    +g+h-i+9)%3
    I = (0                 +9)%3
    arr = [A,D,F,I]
    if count_zero(arr) < 2:
        arr = add_one(arr)
    if count_zero(arr) < 2:
        arr = add_one(arr)
    A,D,F,I = arr
    return (A,B,C,D,E,F,G,H,I)

def main():
    a, b, c, d, e, f, g, h, i = map(int, input('Enter values:').split()) #(0, 1, 0, 1, 0, 1, 0, 1, 0)
    A,B,C,D,E,F,G,H,I = compute(a,b,c,d,e,f,g,h,i)
    print('A={}\nB={}\nC={}\nD={}\nE={}\nF={}\nG={}\nH={}\nI={}'.format(A,B,C,D,E,F,G,H,I))

if __name__ == '__main__':
    main()
$\endgroup$
  • 1
    $\begingroup$ So one in three configurations are solvable, and we can rotate B, D, and G independently? (oh, by the way your count_zero could be replaced with arr.count(0)) $\endgroup$ – Jonathan Allan Nov 21 '16 at 11:09
  • $\begingroup$ When you say "Notice that rotating A+D+F+I once results in rotating all gears once. So we can safely assume that I=0 and later rotate all gears once to compensate for this." it is odd, because in the puzzle I see, you can only rotate all "gears" (unless you lock something). $\endgroup$ – Tokkot Nov 21 '16 at 11:35
  • 1
    $\begingroup$ I suggest you to write an executive summary in the beginning of your post, stating when (if and only statement) the configuration is solvable. Then the interested reader can go on and start reading the details. Now the answer is hidden deep down amongst the lines of the reasoning (=proof of the claim). $\endgroup$ – Matsmath Nov 21 '16 at 11:38
  • 5
    $\begingroup$ So "almost always solvable" means "solvable with probability 1/3 if states are chosen randomly"? $\endgroup$ – Henning Makholm Nov 21 '16 at 14:01
  • $\begingroup$ Wow, I didn't know this answer attracts so much traction. I'll update the answer as your good and constructive comments suggested. $\endgroup$ – justhalf Nov 22 '16 at 2:06
5
$\begingroup$

The puzzle is not solvable from an arbitrary configuration, but the version on the site almost certainly is always solvable. Why? An easy way to generate these puzzles is to start from the solved state and make random moves, which ensures a solution.

You can isolate pieces B, D, and G (labeling them left-to-right, top-to-bottom). For example, you can turn only B with the sequence A-A-B-C-F-F (i.e. lock A, turn twice, lock B, turn once...).

More detail: This is a version of the lights out puzzle and solving it boils down to solving system of linear equations modulo 3. We describe the current state of the puzzle, x_i by a length 9 vector where each entry is either 0, 1, or 2 and encodes the orientation of the corresponding piece. Locking a piece and rotating rest adds one (mod 3) to the unlocked pieces. We can summarize the 10 possible moves in a matrix:

A =[ ...
 0 0 1 1 1 1 1 1 1 1
 1 0 0 0 1 1 1 1 1 1
 0 1 0 1 0 1 1 1 1 1
 1 1 1 0 0 1 1 1 1 1
 1 0 1 1 0 0 0 1 1 1
 1 1 0 1 1 0 1 0 1 1
 1 1 1 0 1 1 0 0 1 1
 1 1 1 1 0 1 1 0 0 1
 1 1 1 1 1 1 0 1 0 1];

Where each column corresponds to locking one piece, and the last row is locking nothing. To solve a puzzle, you solve the equation Ax + b = 0, where b is the current configuration and x is the vector of moves to take. In MATLAB:

b = [2 0 0 0 2 1 0 0 2]';
x = gflineq(A, mod(-b, 3), 3)

You can use the same code to search for which pieces can be isolated (by making b have only one non-zero element).

$\endgroup$
  • $\begingroup$ Good point of isolating some gears. And yeah, using MATLAB will give you solution real quick, haha. Btw, I don't think you will ever need to turn something twice, as turning something twice is equivalent to turning to the other direction. $\endgroup$ – justhalf Nov 22 '16 at 2:20
  • $\begingroup$ @justhalf Good point! "Turn twice" is equivalent to "turn once in the opposite direction". $\endgroup$ – Tokkot Nov 22 '16 at 9:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.