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:
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()