Several changes are an old problem. It is more shallow statement that 3 of 19 is 19 times. It means that there is a single point on the chessboard, black, white three states, a total of 19 * 19 points, so I got this result. But it doesn't actually not so much, because in so many states, a large part is impossible, that is, there is a state in the disk. For example, the state of the chess pieces all over the board is impossible, and this state has 2 19 * 19 times.
So a long time ago I have proposed "There are several changes in the reasonable changes in Go". I originally solved from the perspective of pure combined mathematics, trying to get a simple expression result. But I have no reasonable ideas for a long time. Write a program to calculate it is of course possible, but it seems that everyone seems to say this. I am unwilling, and I have finally written such a coarse shallow program by learning Java. Java.
The algorithm of this program is undoubtedly straightforward. It is a case of N * N's chessboard, enumerates all 3 ^ (n * n) situations, and judge whether each point is active. If each point is active chess, the overall situation is a reasonable situation. The judgment criteria for each point is a recursive: a point survival and only when it is an empty point or with this point adjacent to this point, there is an empty point or colorful play.
The efficiency analysis of this program is as follows:
EnumallStatus function enumerates all situations, perform 3 ^ (n * n) times. In each enumallStatus, you want to call the isvalid function (judgment is whether the current situation is reasonable), it calls: resetVisited function (reset access flag of each point), execute n * n times; isalive function (judgment each point Whether it is alive, also execute n * n times. The isalive function is a recursive function, and its recursive depth is not very good, I feel that it will probably be a number with N linear order. So ISALIVE performs a total of O (n ^ 3), which is mainly role in RESETVISTIED. So the time complexity of the entire algorithm is O (3 ^ (n * n) * n ^ 3).
I have calculated some results, set a chess board of N * N, whose number of reasonable changes is represented by V (n), then v (1) = 1, v (2) = 57, v (3) = 12675 , V (4) = 24318165. On my machine, calculate V (3) for 125ms, calculates V (4) 498907ms, about 8 minutes. And if the time of calculating V (3) and the time complexity estimation of V (4) (ignore the secondary item and the normal coefficient), the result will be 648000ms, and the actual situation is in the same order of the same order, so I feel My time complexity is estimated to be roughly accurate.
In this case, it is estimated that the time required for V (5) is approximately a few hundred days. Another problem is that the current variable I use is to count, and the INT model in Java is 2 ^ 31-1, which can only process N = 4. Even if it is changed to the long type, it can only handle n = 5, you can count it yourself. Of course, this is a secondary issue, and the algorithm is inefficient is the main problem.
Another interesting thinking is to investigate the value of V (n) / 3 ^ (n * n), that is, reasonable changes account for all changes. According to the current results:
n = 2: v (2) = 57, 57/3 ^ 4 = 0.7037
n = 3: V (3) = 12675, 12675/3 ^ 9 = 0.6440
n = 4: V (4) = 24318165, 24318165/3 ^ 16 = 0.5649
It seems to be getting smaller and smaller, will it eventually tend to tend to a constant? I feel that if V (n) / 3 ^ (n * n) will tend to be a value greater than 0.5, at least 1/3, but it does not find prove. I hope who can give a certificate that it does not tend to 0. On the other hand, you can also help me optimize the algorithm, but the main optimization is to make the program do not have to enumerate 3 ^ (n * n) variations, otherwise the program will not improve.
