An algorithm of moving pieces to become black alternation with white based on dimension reduction

Moving pieces to become black alternation with white (MPBBAW), also known as interval chess, or as the Mandarin Duck game is a kind of a continuous arrangement which involves moving black and white pieces after making the moves n times till the interval arrangement of the game. It is a mathematical game in which black and white pieces represent the laws of object movement. The chess game is essentially a mathematical problem. The Chinese Go has a long history. Go players inadvertently have found a new way to play black and white pieces. During the reign of Shunzhi in the Qing Dynasty (1641–1661), Hu Lizhi used Go to move three black and three white pieces continuously arranged ‘ ’,‘ ’, ‘ ’, ‘ ’. In the KangXi period, Chu Renhuo's “solid bottle collection” recorded: ‘when I was young, I met my friend Hu Lizhi, who divided the black and white pieces into three pieces. I asked, “how much could you move?” Li Zhi said:“ from three to ten, can be moved. More is more.” “return to try, from three to ten fruits alternately and not disorderly”’ [1]. In the late years of the Qing Dynasty, various masters such as Yu Yue made an in-depth study of the game of MPBBAW and further proposed the moving steps of 11 to 20 pairs of pieces. Limited by the lack of mathematical knowledge of permutation and combination, these folk game experts did not delve into the rules of permutation and combination. Xu Baoli, founder of China's probabilistic statistics, and Yu Pingbo increased the number of chessmen up to fifty based on the “solid bottle collection”. A year later, Xu Baoli devised a new law of MPBBAW. Yu Pingbo recorded the matter in the “Method of MPBBAW”: ‘In the night of the second day of the New Year, he called me suddenly. I happened to be away and he called on me the next day. Then he told me about the law of “combining four into one”. This method was concise and the language was clear. Although it had no more roots than the four laws, it was not redundant, and not wrong. This method was clearly and immediately understood by the people and the application was also very convenient.’ [2] The fun of MPBBAW aroused the divergent thinking of scholars. You Baosan and Mo Shaokui promoted black and white to be polychromatic. Two adjacent pieces are moved each time and could be generalised as P (P could be one) pieces. It was proved that the two-colour chess pieces ‘move 2’ each time. They also proved that the minimum number was equal to the log n of the chess piece [3]. Hu Zhuxin studied the MPBBAW from the modern combination theory. He pointed out that the problem of MPBBAW fell under the category of inlay theory. The idea was to recombine one sequence into another under a particular combination rule. For example, several data stored in a one-dimensional form in a computer were stored separately by category, or using the shift method to make or break a code. The principle of the game was connected with the problem of moving chess in some way [4], which the ancient literati women did not expect. Contrary to the research purport of Chinese players and scholars, foreign scholars had studied the inverse problem of MPBBAW.

In 1743, the early Japanese document ‘ double paper of Kan Zhe Yu Jia’ called it ‘Mandarin Duck game’ [5]. Three pairs of black and white pieces spaced apart from each other, through three times moving, became three white pieces and three black pieces in a row. , , , . This was the exact opposite of the MPBBAW of Chinese players and scholars. The rules of the arrangement of more pieces were the same as those which were applicable to the three pieces; these rules required that two adjacent pieces were moved each time and that the position remained the same and did not change after moving. In 1884, the British physicist Tate replaced the black and white pieces with four gold coins (denoted by B) and four silver coins(denoted by A). He proposed how to generate the ‘BBBBAAAA’ alignment through four moves for ‘ABABABAB’. Unlike Chinese and Japanese scholars, Tate used letters instead of black and white pieces, and his method was exactly the same as that of Japanese scholars. In 1887, Delanoy, a French mathematician, proved the inverse problem of MPBBAW by mathematical method for the first time. The article containing this proof was published in the Journal Nature. In 1899, Dr. Lin Heyi, a Japanese scholar, once again tested the inverse problem of MPBBAW by adding one on each side of the black and white pieces [5].

Different from foreign scholars who paid attention to the inverse problem of MPBBAW, Geng Ji, the contemporary Chinese scholar, insisted on studying the problem of MPBBAW which originated in the late Ming Dynasty and early Qing Dynasty. After a systematic review of research results of the Chinese and foreign scholars, Geng Ji thought that c was still an open question. Through the permutation and grouping method, he found that the core problem of MPBBAW was the distribution of fixed terms. If the position of the fixed item could be determined, different shifting methods could be adopted according to the different regional distribution of the fixed item, and then the regularity of MPBBAW could be deduced. That was when the positive integer n≥ 4, there were n times movings between moves (minimum n times movings) to make the initial form become the final form [6, 7]. This made the MPBBAW experience of Chinese ancient players and scholars mathematically concluded and proved. Further, the MPBBAW problem was more formalised and mathematical.

At this point, the mathematical properties of the phase problem are fully confirmed, and the mathematical law of the phase problem is revealed. However, it is still difficult to move the large chess pieces in the phase-shifting problem, and the practical application value of the phase-shifting law has not been explored. Only a few scholars have made some bold attempts to explore the practical application value of the phase-shifting problem. ShaYanFei et al. through their observation found that n = 4, n = 5, n = 6, n = 7 four special structures can set an operator in the n of 8 or in arrangement of the pieces; this is because any number of pieces can be in ‘Divided by 4, leaving 0, 1, 2, 3’, the form of simple operation, which is based on the proposed simple mathematical proof of MPBBAW, and the interval arrangement rule is applied to building design [8]. The phenomenon of simple and static space arrangement is common among people, which is abstracted as the rule of space arrangement in primary school mathematics and modelled by scholars. However, for the complex and dynamic spacer arrangement, it has not attracted wide attention from scholars, and the related applied research is rare. Taking graphic design and display as an example, at present, the application of English letters and Chinese characters with graphic expression has been mature and has the limitation of a small amount, mechanical, monotonous and so on.

The main application scenarios of this chess are thinking, training and LED electronic display. This rule can be applied in many aspects, such as electronic display, building layout, etc. The large-scale movement and commercial application of MPBBAW require the help of computers. Through this research, we find that the solution algorithm of MPBBAW can reduce dimension using stack [9, 10, 11], and continuously reduce dimension for the phase shift problem of the n-order. Also, we carry out a special solution and back-substitution for special-order problem to realise the computer operation of the whole MPBBAW problem of n-order.

The basic rules of MPBBAW are that:(1) in the process of moving, the position of adjacent pieces cannot be exchanged; (2) after a pair of chess pieces move, the original position becomes vacant and (3) the space arrangement finally formed has no vacancy.

We use the black circle for the black and the white circle for the white and set the ‘underline’ only to indicate the two pieces to be moved next.

When n = 3,

When n = 4,

When n =5,

When n = 6,

When n = 7,

For n = 7, we find that the diagram contains a ‘3 black 3 white’, which we call the 7 black 7 white subsets. Marked with a quotation, we mark to distinguish it from the normal 3 black 3 white. In the ‘3 black and 3 white’ movement order, the moving pieces and direction of the ‘first step’ are the same as that of the ‘3 black and 3 white’, and the moving pieces of the ‘second step’ are the same, but in different directions (the second step of the normal 3 black and 3 white is to move to the right, while the ‘3 black and 3 white’ moves to the left because there is a space on the left). So 3 black and 3 white can be considered as special cases.

Referring to the research of Delanoy in 1887 (his article was published in the 15th issue of Nature in 1887), Dr. Lin Heyi in 1899 [5] and Geng Ji in 2010 [6, 7], we believe that for any n > = 4, that is, with n black pieces and n white pieces, MPBBAW can be achieved in at least n steps of movement. When n=4, n=5, n=6, and n=7, the operation steps of the chess pieces are in the basic mode or fixed state. Since the first move, the second move, the penultimate move and the last move are consistent, thus: when n is congruent with 0 (mod4), the intermediate state of the chess piece can be converted to 4 sub-modes. When n is congruent to 1 (mod4), the intermediate state of the chess piece can be converted to 5 sub-modes. When n is congruent to 2 (mod4), the intermediate state of the chess piece can be converted to 6 sub-modes. When n is congruent to 3 (mod4), the intermediate state of the chess piece can be converted to 7 sub-modes.

Initial state:

The first:

The second

……

The penultimate

The last:

If we take 8 pieces as an example, it can be converted into 4 pieces mode:

When n≥ 8, the method of ‘Divided by 4, leaving 0, 1, 2, 3’, by Sha Yanfei et al, [8] can be used for simple treatment, which is in line with the rigorous and complex mathematical proof and movement of Geng Ji [6, 7]. This has laid a foundation for the large-scale computer calculation and commercial application of MPBBAW.

It can be seen from the dimensionality reduction process of the MPBBAW problem that this algorithm can be based on recursive design, but because of the low efficiency of the recursive algorithm, a non-recursive algorithm is adopted to reduce dimensionality by using stack for n-order of MPBBAW problem. With the help of the programme stack, the non-recursive algorithm transforms the programme into a loop and effectively and reduces the time complexity [12, 13, 14] For the n-order of MPBBAW, the problem is continuously processed by reducing the dimension by the 4-order [15, 16]. The feasible interval of the current moving game phase is kept by stack until n<8. Then, the problem of the special MPBBAW problem that is less than 8 is solved in a special way. Also, the problem of the whole n-order moving game phase is solved by back-substitution [17, 18]. The specific algorithm design is as follows:

Create the initial solution data[1 ∼ 2n+2] and the initial interval [low, high], low=1, high =2n+2 for the n-order of MPBBAW problem. (the convention data[I] takes 1 for black, 0 for white, and 2 for empty).

The flow chart of the algorithm is shown in Figure 1.

Fig. 1

The specific steps are: for more than 7 pieces, it can be converted to one of the four cases. The first two steps are to put ‘2, 3’ at the end of the table, and then put ‘2n-5’ (2n means double colour, -5 means penultimate fifth) and ‘2n-6’ in the space so that you get a black and white sequence with an ‘n-4’ in the middle. Then put ‘2n-3’ and ‘2n-2’ in the space, and then put the first two in the space. This is a round operation, which is solved if the middle ‘n-4’ is one of the ‘4, 5, 6, 7’, otherwise continue the above recursive operation for the black and white strings of the middle n-4’.

We take 20 black and 20 white (abbreviated as 20) as an example and explanations. n=20

The running steps of the 20 computer are:

Step 1: place‘2,3’ pieces at the back. (note that there are 20+20+2 Spaces)

Next, repeat steps (each time will be the beginning of a new series of ‘2, 3’, and finally, the new bottom fifth and sixth in the first ‘2, 3’ and each time will get a less than 4 before a series of black and white) until the rest of the series of black and white is one of the ‘4, 5,6,7’. This is a special method to solve the four kinds of circumstances.

After solving the special case, repeatedly put the reciprocal ‘2, 3’ of the current black and white sequence into the current position to the beginning of the current sequence ‘5, 6’. And put the current beginning of the current sequence to the current reciprocal of the current reciprocal ‘2, 3’. Then it becomes possible to solve the current black and white sequence, and then it is necessary to repeat one of the steps to solve the previous black and white sequence. Until it is all settled. The result of ‘n=20’ is shown in Figure 2.

Figure 2

For any n pieces, the running steps and algorithm of the computer are as follows:

n = k, k≥8„ k ∈ N*

Step 1: place ‘2, 3’ pieces at the back. (note the spaces, k+k+2 positions)

Step 2: place the fifth and sixth from the bottom (i.e. 2k+2–5, 2k+2–4) pieces on ‘2, 3’ vacancy. So we get a ‘k-4’ substring starting from the fifth position.

Step 3: treat the ‘k-4 substring’ at the beginning of the fifth digit as an independent sequence. The third move is similar to the first, moving the ‘2, 3’ pieces (actually moving the 6th and 7th pieces). That is the end of the ‘k-4’ substring with the second and third bits in ‘k black and k white pieces’.

Step 4: place the penultimate fifth and sixth place of the ‘k-4’ substring to the ‘2, 3’ place of the ‘k-4’ substring. Then you can get a black and white string of ‘k-4-4’ pieces.

Next, repeat steps (each time will be the beginning of a new series of ‘2, 3’ and finally, the new bottom fifth and sixth in the first ‘2, 3’, and each time will get a less than 4 before a series of black and white) until the remaining black and white sequence is one of ‘4,5,6,7’, which have special solutions.

After solving the special case, repeatedly put the reciprocal of the current black and white sequence to the beginning of the current sequence ‘5, 6’, and put the current beginning of the current sequence to the current reciprocal ‘2, 3’. Then you can solve the current black and white string. Then repeat this step to solve the previous black and white sequence until all the white and black spaces are formed.

To summarise, so far, we think of the three pieces as a special case, and what we’ve concluded is merely a rule, and there should be other rules. This rule can be applied to all aspects of social and economic life.