Jiu Lian Huan 九连环

Last edit: 3 Jan 2025

How many steps needed to solve Jiu Lian Huan?

Let me represent a ring when locked as 1 and when unlocked as 0. Starting out all 9 rings are locked as "111 111 111", the goal is to get them all unlocked as "000 000 000". The spaces between every 3 binary levels are just for readability.

Starting out: 111 111 111

111 111 110
111 111 010
111 111 011
111 111 001
111 111 000
111 101 000
111 101 001
111 101 011
111 101 010
111 101 110
111 101 111
111 101 101
111 101 100
111 100 100
111 100 101
111 100 111
111 100 110
111 100 010
111 100 011
111 100 001
111 100 000

To get 1 ring out, need 1 step.
To get 3 rings out, need 1 + 4 = 5 steps.
To get 5 rings out, need 1 + 4 + 16 = 21 steps.

Notice the pattern?

4^0 = 1
4^1 = 4
4^2 = 16
4^3 = 64
4^4 = 256

So, to get 7 rings out, need 1 + 4 + 16 + 64 = 85 steps. To get all 9 rings out, need 1 + 4 + 16 + 64 + 256 = 341 steps! What an exponential increase in its number of steps for every 2 more rings.

How many steps needed to solve n Lian Huan with n odd number of rings?

n = 1, 3, 5, 7, 9, 11, 13, 15...

Sum of steps for n rings = 1 + 4 + 16 + 64 + 256 + ... can be written as a geometric series:

First term 'a' = 1
Common ratio r = 4

But, we still need a linear function to map n rings to the number of terms in the geometric series. For instance:

1 ring -> 1 term
3 rings -> 2 terms
5 rings -> 3 terms
7 rings -> 4 terms
n rings -> k terms
n rings -> (n+1) / 2 terms

So, k = (n+1) / 2

Using formula of geometric progression, steps needed for n odd rings, or sum of terms up to k term:
a * (r^k - 1) / (r - 1)
1 * (4^k - 1) / (4 - 1)
(4^k - 1) / 3
(4^((n+1) / 2) - 1) / 3

Using this formula, theoretical steps needed for 11 rings = (4^((11+1) / 2) - 1) / 3 = 1365. We can see it quickly become unrealistically unmanageable playing it by hands given this ridiculous amount of steps.

Page updated

Google Sites

Report abuse