origin
The Chinese Ring
Zhuo Wenjun, the wife of a talented woman and poet in the Western Han Dynasty, once mentioned the Nine Commandments: "I can't understand it, I can't understand it, I can only blame Lang. ……
Zhuo Wenjun was born in the Western Han Dynasty, and Zhuge Liang was born at the end of the Eastern Han Dynasty, when the Han Dynasty had fallen apart. The difference between the two is hundreds of years. That is to say, in the Western Han Dynasty hundreds of years before Zhuge Liang, the Nine-Chain already existed. Therefore, the statement that "the nine-ring chain was invented by Zhuge Liang" is not correct, and it may have been misinformed by later generations. Others think that the story of Zhuo Wenjun's lyrics seems to have been invented by the Yuan Dynasty, because the style of lyrics is obviously not owned by the Han Dynasty.
On March 8, 2003, Wang of Jiayuguan City, Gansu Province, China successfully solved the Nine-Chain in 3 minutes and 57 seconds, and entered the Guinness Book of World Records.
201210/0/On October 25th, CCTV News Channel reported that Yang Xianyang, a student of Jiangxi University of Science and Technology, set a record for the fastest disassembly of the nine-ring chain, with the time of 16 1 second (blindfolded) [1].
history
Legend has it that the Nine Rings originated from the ancient Han people in China, which was invented during the Warring States Period and the Three Kingdoms Period. But what is certain is that the record of Jiu Lianhuan is the Total Record of Dan and Lead by Yang Shen in Ming Dynasty (1488- 1559, Sheng 'an) (see Sheng 'an Collection, Volume 68), not earlier than Europe.
In China, Hui Shi, a famous figure in the Warring States Period, once wrote the argument of "serial solvability". Hui Shi's serial refers to the jade serial mentioned in the thirteenth volume of Warring States Policy, and the Southern Song Dynasty treasure table notes that this jade serial is "the intersection of two rings", which is obviously not the nine serial mentioned here. It is said that during the Three Kingdoms period, Zhuge Liang often led troops to fight, which was invented to relieve his wife's loneliness. It was popular in the Ming Dynasty and spread widely in the middle of the Ming Dynasty. In the Qing Dynasty, everyone, from literati to peddlers and pawns, loved to play the "Nine-Chain". There are some details about playing nine-ring in the boudoir in A Dream of Red Mansions.
In the west, before16th century, there were 9 chain stores in Europe. 1550, a mathematical literature published in Paris, clearly discussed this "China puzzle". Cardin, a famous Italian mathematician, called it "China's Nine Rings" in his works. 1685, the British mathematician Varis gave a detailed mathematical explanation. /kloc-In the 9th century, Gross gave it a very beautiful answer with binary numbers.
At any time, the Nine Rings have this symbol of wisdom. In ancient times, for people, the nine-ring chain was not a toy, but a symbol of wisdom. People who have watched many TV dramas should have the impression that some foreign countries that send missions to China, some of which are still arrogant, will take out nine chains to make things difficult for the DPRK ministers. When everyone is at a loss and officials are proud of foreign countries, there will always be smarter people to untie the nine chains and save China's face. Therefore, the nine-ring chain will always be labeled with a smart hat.
structure
nine
All kinds of nine-chain (14)
Serialization is very popular, with various forms and specifications. When making, nine small rings are made of metal wires, which are connected and sleeved on strip-shaped transverse plates or various frames. The handle of the frame is sword-shaped, wishful-shaped, butterfly-shaped, plum-blossom-shaped and so on, and each ring is connected with it by copper bars. When playing, all nine rings are connected to the copper ring according to law, or all of them are untied after putting on sleeves. Its solutions are diverse, separable and changeable. The winner needs 8/kloc-0 times to arrange 9 connected rings in a row, and it takes 256 times to untie all 9 rings. In addition, it can also be set into flower baskets, hydrangeas, palace lanterns, etc.
At the same time, the nine-ring chain is also solved in order. It takes a long time to solve the nine chains, and it can also exercise people's patience. Moreover, the nine-ring chain can increase the number of rings as needed to improve the difficulty, but the increase of the number of rings will increase the steps of solving rings geometrically, and the method of solving rings has not changed in essence, so we usually see nine rings.
Disassembly principle
edit
Nine gold-plated rings
It takes 34 1 step to untie the nine rings. Just put the upper ring or the lower ring, even if it is a step, instead of sliding on the frame. I hope everyone can solve this problem through independent thinking. The expansion and nesting of nine chains are a pair of inverse processes. This solution is based on the same principle as computer gray code.
The links of the nine-link chain restrict each other, and only the first link can go up and down freely. In order to get down/up the nth ring, two conditions must be met (except the first ring). 1.n- 1 ring on the rack; 2. None of the rings in front of the n-1ring are on the shelf. Playing nine chains is to try to meet the above two conditions. In essence, to untie the nine-ring chain, we should start from the back ring, and the front ring should be removed before the back ring can be removed. The front ring should be installed, not really removed.
Let's start with the simplest chain. It takes 1 step to solve a chain: in an instant. It takes two steps to solve the two-link problem: twice and once. How to solve the three links problem? It takes five steps: one, three, one, two, one. That is to say, solve a chain, then solve the last chain, then solve a chain, and then solve a chain. Solving a quadruplex requires 10 steps: two, one, four, one, two, one, three, one, two, one. That is, solve a two-chain, then the last chain, then a two-chain, and then a three-chain.
That is to say, to solve an N-2 chain is to solve an N-2 chain first, then the last chain, then the N-2 chain, and then the N- 1 chain.
It takes 1 step to solve a chain, and 2 steps to solve a chain. Therefore, it takes 5 steps to solve a triple chain, 65,438+00 steps to solve a quadruple chain, 265,438+0 steps to solve a quintuple chain, 42 steps to solve a hexamer chain, 85 steps to solve a heptamer chain, and 65,438+070 steps to solve an octamer chain and 3,465,430.
Heat splitting method
edit
basic approach
Separate the frame from the nine rings, such as holding the handle of the frame with the left hand and the ring with the right hand. From right to left, the number is 1-9. Put the ring in the frame as "top" and take it out as "bottom".
9 serial disassembly ***256 steps:
Next 9:
Down 1 (the result is 98765432): down 1.
Lower 3 (the result is above 987654): Lower 3 is above 1 and lower 12.
Lower 5 (the result is 9876): lower 5, upper 12, lower 1, upper 3, upper 1, lower 12, lower 4, upper 12, lower 3, upper/kloc-.
Below 7 (above result 98): down 7 up 12 down 1 up 3 up 1 down 12 up 4 up 12 down/kloc-0 down 3 up/kloc-0 up 5 up/kloc-. 02 Up 6 Up 12 Down 1 Up 3 Up 1 Down 12 Up 4 Up 12 Down 1 Down 3 Up 1 Down 5 Up 12 Down/Kloc
Lower 9 (result 8 is above): lower 9;
Nine-chain solution
Next 8:
Up 2 (result 82 is up): up 12, down 1.
Up 3 (result 83 is up): up 3 up 1 down 12.
Up 4 (result 84 is up): up 4 up 12 down 1 down 3 up 1 down 12.
Up 5 (result 85 is up): up 5 up 12 down 1 up 3 up 1 down 4 up 12 down 1 down 3 up 1 down.
Up 6 (result 86 is up): up 6 up 12 down 1 up 3 up 1 down 12 up 4 up 12 down 1 down 3 up 1 down.
Up 7 (result 87 up): up 7 up 12 down 1 up 3 up 1 down 12 up 4 up 12 down 1 down 3 up 1 up 5 up/kloc-. +02 Up 6 Up 12 Down 1 Up 3 Up 1 Down 12 Up 4 Up 12 Down 1 Down 3 Up 1 Down 5 Up 12 Down/.
Lower 8 (result 7 is above): lower 8;
Next 7:
Up 2 (result 72 is up): up 12, down 1.
Up 3 (result 73 is up): up 3 up 1 down 12.
Up 4 (result 74 is up): up 4 up 12 down 1 down 3 up 1 down 12.
Up 5 (result 75 is up): up 5 up 12 down 1 up 3 up 1 down 4 up 12 down 1 down 3 up 1 down.
Up 6 (result 76 is up): up 6 up 12 down 1 up 3 up 1 down 12 up 4 up 12 down/kloc-0 down 3 up 1 down.
Lower 7 (result 6 is above): lower 7;
Next 6:
Up 2 (result 62 is up): up 12, down 1.
Up 3 (result 63 is up): up 3 up 1 down 12.
Up 4 (result 64 is up): up 4 up 12 down 1 down 3 up 1 down 12.
Up 5 (result 65 is up): up 5 up 12 down 1 up 3 up 1 down 4 up 12 down 1 down 3 up 1 down.
Lower 6 (above result 5): lower 6;
Next 5:
Up 2 (result 52 is up): up 12, down 1.
Up 3 (result 53 is up): up 3 up 1 down 12.
Up 4 (result 54 is up): up 4 up 12 down 1 down 3 up 1 down 12.
Lower 5 (result 4 is above): lower 5;
Next 4:
Up 2 (result 42 is up): up 12, down 1.
Up 3 (result 43 is up): up 3 up 1 down 12.
Lower 4 (result 3 is above): lower 4;
Next 3:
Up 2 (result 32 is up): up 12, down 1.
Lower 3 (result 2 is above): lower 3;
12:
Lower 12 (as a result, the disassembly is completed): upper 1, lower 12.
9 serial installation ***34 1 steps:
Page 98:
Up 2 (result 2 is up): up 12, down 1.
Up 3 (result 3 is up): up 3, up 1, down 12.
Up 4 (result 4 is up): up 4 up 12 down/kloc-0 down 3 up 1 down 1 2.
Up 5 (result 5 is up): up 5 up 12 down 1 up 3 up 1 down 4 up 12 down 1 down 3 up 1 down.
Liter 6 (result 6 is liter): liter 6 12 drop 1 liter 3 1 drop 12 liter 4 12 drop 1 drop 3 liter 1 drop.
Up 7 (result 7 up): up 7 up 12 down 1 up 3 up 1 down 12 up 4 up 12 down/kloc-0 down 3 up/kloc-0 up 5 up/kloc-. 02 Up 6 Up 12 Down 1 Up 3 Up 1 Down 12 Up 4 Up 12 Down 1 Down 3 Up 1 Down 5 Up 12 Down/Kloc
Up 8 (result 8 up): quotient 8 12 summer 1 quotient 3 1 2 quotient 4 12 summer 1 summer/kloc-0. 02 quotient 6 12 summer 1 quotient 3 1 summer 12 quotient 4 12 summer 1 summer 3 quotient 1 summer 5 quotient 12 summer/kloc. 8+02 down 7 up 12 down 1 up 3 up 1 down 12 up 4 up 12 down 1 down 3 up 1 down 12 up 5 up. 38+02 Xia 6 Quotient 12 Xia 1 Quotient 3 Quotient 1 2 Shang 4 Quotient 12 Xia 3 Quotient 1 Xia 12 Xia 5 Quotient 12
Up 9 (Result 98 Up): Up 9
Page 76:
Nine-chain solution
Up 2 (982 is up): up 12, down 1.
Up 3 (983 is up): up 3 up 1 down 12.
Up 4 (984 is up): up 4 up 12 down/kloc-0 down 3 up 1 down 1 2.
Up 5 (985 is up): up 5 up 12 down 1 up 3 up 1 down 4 up 12 down 12 down/down 3 up 1 down.
Up 6 (result 986 is up): up 6 up 12 down/kloc-0 up 3 up 1 2 up 4 up 1 2 down/kloc-0 down 3 up/kloc-0 down/kloc-0.
At 7 (the result is 9876): At 7.
At 54:
Up 2 (98762 is up): up 12, down 1.
Up by 3 (result 98763 is up): up by 3, up by 1, down by 12.
Up 4 (98764 is up): up 4 up 12 down 1 down 3 up 1 down 12.
5 at most (987654 is Up): 5 at most.
32 nd:
Up 2 (9876542 is up): up 12, down 1.
At 3 (the result is 9876532): At 3.
On 1:
On 1 (as a result, the installation is completed): On 1.
Recursive cracking
It is easier to understand and remember the disassembly method of nine-ring chain by "recursion". The so-called recursion is the solution of the nth step, which can be solved by the known method of n- 1 step (or earlier). For the nine-ring chain, the method of removing the n-th ring can be described by removing the n- 1 ring. The problem of removing the nth ring is transformed into the problem of how to remove the nth ring, that is, we will remove the nth ring after removing the nth ring. The following is a description of the specific disassembly method:
N Method of disassembling 1 ring: (D 1)
1. Push the 1 ring out of the crossbar and put it on the crossbar.
N Method of installing 1 ring: (U 1)
1. Put the 1 ring under the crossbar, pull it out and put it in the crossbar.
Method of removing the second ring: (D2)
1. Replace1; (U 1)
2. Push the second ring and 1 ring out of the crossbar together, and pass the second ring through the crossbar; (Remove the second ring)
3. Replace and remove 1. (D 1)
N Method of installing the second ring: (U2)
1. Replace1; (U 1)
2. Put the second ring under the crossbar, pull it to the front and put it in the crossbar; (Install the second ring)
3. Replace and remove 1. (D 1)
Method of dismantling the nth ring: (Dn)
1. Install the n- 1 ring; (Un- 1)
2. Push the N-ring and the n- 1 ring out of the crossbar together, and pass the N-ring through the crossbar; (Remove the nth ring)
3. Remove the n- 1 ring. (Dn- 1)
N Method of installing the nth ring: (Un)
1. Install the n- 1 ring; (Un- 1)
2. Put on the nth ring from under the crossbar, pull it to the front and put it in the crossbar; (Install the nth ring)
3. Replace n- 1 and remove it. (Dn- 1)
N In order to speed up, the n+ 1 ring and the N ring can be removed together: (Dn.n+ 1)
1. Push the n+ 1 and the n ring out of the crossbar, and pass the n+ 1 ring through the crossbar; (Remove n+ 1 ring)
2. Install n- 1 ring; (Un- 1)
3. Push the N-ring and the n- 1 ring out of the crossbar together, and pass the N-ring through the crossbar; (Remove the nth ring)
4. Remove the n- 1 ring. (Dn- 1)
For example:
How to remove the third and fourth rings when the first 1 and the second ring are removed (n=3, D3.4);
1. Push the fourth ring and the third ring out of the crossbar together, and pass the fourth ring through the crossbar; (Remove the fourth ring)
2. Install the second ring; (according to method U2)
3. Push the third ring and the second ring out of the crossbar together, and pass the third ring through the crossbar; (Remove the third ring)
4. Remove the second ring again. (according to D2 method)
Step calculation
edit
Nine-ring is a folk toy of Han nationality in China. It is specified that the ring is represented by 1 on the rod, and the ring is represented by 0 below. It is stipulated that the leftmost ring can move up and down at will, and the rightmost ring in the output data must be 1, that is, 010/00 should be written as 0 10 1.
Today, it is an X-chain. Because "the rightmost part of the output data must be 1", x can be understood as infinity, and the extra zeros on the right are omitted when outputting. Each ring is initialized to 0, and the following are the first 9 steps:
1. 1
2. 1 1
3.0 1
4.0 1 1
5. 1 1 1
6. 10 1
7.00 1
8.00 1 1
9. 10 1 1
What exactly happens after step n is completed in the X-serial loading process?
Answer: Convert N into binary and find its Gray code. Output binary gray code in reverse order, and get the specific situation.
Note: this algorithm reveals the important relationship between traditional nine chains and modern gray codes!
Program realization
A solution
Method 1: First, you keep counting 1, 2, 1, 2, 1, 2, 1 ...
When the number is 1, the 1 ring goes up or down.
When counting 2, look at the number of the first ring in the frame from the first ring, and then go up/down its next ring. For example, 1 ring is on the frame, and only 2 rings need to be up/down;
No.65438 +0 to No.5 are all under the shelf, and the sixth one is on the shelf, directly above/below the Seventh Ring Road.
I have always counted 34 1 before I worked out this number.
Method 2: To solve the nine-ring chain, you must first know how to untie 1 and 2 rings, and you can disassemble 1 and 2 rings (see the first step for how to disassemble), so that you can disassemble the following rings.
Disassembly method
First ring: pick up the first ring from the left and put it down from above. (There are diagrams, and the steps of each cycle are the same) (The green and red squares help to identify the direction, and the arrows guide the moving direction) Important steps!
The second ring: the same as the first ring (the first ring cannot be dropped first).
Disassembly skills (sequence)
Remove the first ring
Remove the third ring.
Remove the second ring.
Take off the fifth ring.
Install the third ring as before, and then remove the fourth ring.
Remove the third ring and the left ring.
Take off the seventh ring.
Put on the fifth ring and take off the sixth ring.
Put on the fourth ring and take off the fifth ring.
..... until the uninstall is complete.
Removing the ninth ring is a step closer to success.
Try to remove the eighth ring.
Try to remove the front ring.
Success (in fact, there are more than 100 steps)