提出问题
最近在做一个拼图的小游戏，在如何将拼图打乱的方式上，采用将完整拼图以白块为主体对象，白块可以移动到相邻的位置，这时问题就随之产生，白块要随机移动多少次，才能将拼图变得更乱呢?
我们先定义好几个概念：
模块: 在3x3的拼图中就有9个模块，白块也是一个模块，模块所包含的信息有真实位置和当前位置
匹配:模块的真实位置和当前位置一致时称为匹配
匹配度: 所有模块中匹配的个数除以总模块数再乘100
作出假设
移动n次后，匹配度和模块数，n有关，匹配度先减小然后趋于稳定
验证假设
这里用python编写一个小程序来检验，代码如下:
# 本次升级修复了可恢复性
import random
import numpy as np
import matplotlib.pyplot as plt
# 获取为空的模块
def get_blank(cells_position):
for cell_position in cells_position:
if cell_position["realPosition"][0] == col - 1 \
and cell_position["realPosition"][1] == row - 1:
return cell_position
return None
# 获取模块blank_cell可以移动的位置数组
def get_can_move(blank_cell):
blank = blank_cell["position"]
can_move_cells = []
for cell_position in cells_position:
i = cell_position["position"][0]
j = cell_position["position"][1]
distanceX = abs(i - blank[0])
distanceY = abs(j - blank[1])
if distanceX != distanceY \
and (distanceY == 0 or distanceX == 0) \
and (abs(i - blank[0]) == 1 or abs(j - blank[1]) == 1):
can_move_cells.append(cell_position)
return can_move_cells
# 计算拼图完成匹配度
def get_success_rate():
count = 0
for cell_position in cells_position:
if cell_position["position"][0] == cell_position["realPosition"][0] \
and cell_position["position"][1] == cell_position["realPosition"][1]:
count += 1
return (count * 100) / len(cells_position)
def init_cells_position():
cells_position.clear()
for i in range(col):
for j in range(row):
position = np.array([i, j])
positions.append(position)
cells_position.append({"realPosition": position, "position": position})
col, row = 3, 3
blank = None
positions = []
cells_position = []
init_cells_position()
# 以白块为对象，判断他的移动
rates = []
for n in range(60):
rate = 0
test_count = 3000
for count in range(test_count):
oldPosition = []
init_cells_position()
for i in range(n):
blank_cell = get_blank(cells_position)
can_move_cells = get_can_move(blank_cell)
length = len(can_move_cells)
for index in range(length):
can_move_cell = can_move_cells[index]
if len(oldPosition) != 0 and can_move_cell["position"][0] == oldPosition[0] \
and can_move_cell["position"][1] == oldPosition[1]:
can_move_cells.pop(index)
break
length = len(can_move_cells)
index = random.randint(0, length - 1)
can_move_cell = can_move_cells.pop(index)
position = can_move_cell["position"]
can_move_cell["position"] = blank_cell["position"]
oldPosition = blank_cell["position"]
blank_cell["position"] = position
current_rate = get_success_rate()
rate += current_rate
print("{}次移动的平均匹配度为:{}".format(n, rate / test_count))
rates.append(rate / test_count)
print("匹配度最高为:{},最低为:{}".format(max(rates), min(rates)))
plt.figure() # 定义一个图像窗口
plt.plot(np.array(range(len(rates))), np.array(rates)) # plot()画出曲线
plt.show() # 显示图像
3x3测试结果:
0次移动的平均匹配度为:100.0
1次移动的平均匹配度为:77.77777777778051
2次移动的平均匹配度为:66.6666666666646
3次移动的平均匹配度为:55.5555555555592
4次移动的平均匹配度为:46.29629629629358
5次移动的平均匹配度为:36.98888888888765
6次移动的平均匹配度为:33.403703703702284
7次移动的平均匹配度为:26.137037037036187
8次移动的平均匹配度为:25.977777777777064
9次移动的平均匹配度为:20.522222222221703
10次移动的平均匹配度为:20.762962962962327
11次移动的平均匹配度为:18.214814814814286
12次移动的平均匹配度为:19.411111111110614
13次移动的平均匹配度为:17.09259259259216
14次移动的平均匹配度为:18.77037037036991
15次移动的平均匹配度为:16.62592592592551
16次移动的平均匹配度为:18.281481481481
17次移动的平均匹配度为:16.262962962962543
18次移动的平均匹配度为:17.855555555555163
19次移动的平均匹配度为:14.966666666666255
20次移动的平均匹配度为:16.77037037036992
21次移动的平均匹配度为:14.596296296295892
22次移动的平均匹配度为:15.9370370370366
23次移动的平均匹配度为:13.274074074073699
24次移动的平均匹配度为:15.162962962962522
25次移动的平均匹配度为:13.037037037036711
26次移动的平均匹配度为:14.844444444444006
27次移动的平均匹配度为:12.05185185185155
28次移动的平均匹配度为:14.648148148147737
29次移动的平均匹配度为:11.807407407407124
30次移动的平均匹配度为:13.851851851851498
31次移动的平均匹配度为:11.633333333333058
32次移动的平均匹配度为:13.596296296295936
33次移动的平均匹配度为:11.666666666666405
34次移动的平均匹配度为:13.422222222221894
35次移动的平均匹配度为:10.948148148147922
36次移动的平均匹配度为:13.16296296296261
37次移动的平均匹配度为:10.803703703703478
38次移动的平均匹配度为:13.266666666666293
39次移动的平均匹配度为:10.574074074073843
40次移动的平均匹配度为:12.596296296295979
41次移动的平均匹配度为:10.777777777777567
42次移动的平均匹配度为:12.548148148147819
43次移动的平均匹配度为:10.607407407407207
44次移动的平均匹配度为:12.677777777777461
45次移动的平均匹配度为:10.440740740740535
46次移动的平均匹配度为:12.596296296295948
47次移动的平均匹配度为:10.16666666666646
48次移动的平均匹配度为:12.251851851851546
49次移动的平均匹配度为:10.055555555555364
50次移动的平均匹配度为:12.274074074073763
51次移动的平均匹配度为:10.014814814814606
52次移动的平均匹配度为:12.348148148147823
53次移动的平均匹配度为:9.985185185185005
54次移动的平均匹配度为:12.011111111110802
55次移动的平均匹配度为:10.244444444444246
56次移动的平均匹配度为:12.333333333332998
57次移动的平均匹配度为:10.292592592592403
58次移动的平均匹配度为:12.207407407407104
59次移动的平均匹配度为:10.12592592592572
匹配度最高为:100.0,最低为:9.985185185185005
3x3,0-59结果
0次移动的平均匹配度为:100.0
1次移动的平均匹配度为:87.5
2次移动的平均匹配度为:81.25
3次移动的平均匹配度为:75.0
4次移动的平均匹配度为:69.77916666666667
5次移动的平均匹配度为:63.97708333333333
6次移动的平均匹配度为:59.53541666666667
7次移动的平均匹配度为:55.41458333333333
8次移动的平均匹配度为:52.31041666666667
9次移动的平均匹配度为:47.860416666666666
10次移动的平均匹配度为:45.25833333333333
11次移动的平均匹配度为:41.983333333333334
12次移动的平均匹配度为:39.78333333333333
13次移动的平均匹配度为:37.1
14次移动的平均匹配度为:36.077083333333334
15次移动的平均匹配度为:33.489583333333336
16次移动的平均匹配度为:32.71666666666667
17次移动的平均匹配度为:30.566666666666666
18次移动的平均匹配度为:30.097916666666666
19次移动的平均匹配度为:27.925
20次移动的平均匹配度为:27.497916666666665
21次移动的平均匹配度为:25.9
22次移动的平均匹配度为:25.583333333333332
23次移动的平均匹配度为:24.25
24次移动的平均匹配度为:24.545833333333334
25次移动的平均匹配度为:22.554166666666667
26次移动的平均匹配度为:22.704166666666666
27次移动的平均匹配度为:21.154166666666665
28次移动的平均匹配度为:21.483333333333334
29次移动的平均匹配度为:19.766666666666666
30次移动的平均匹配度为:20.3875
31次移动的平均匹配度为:19.352083333333333
32次移动的平均匹配度为:19.439583333333335
33次移动的平均匹配度为:19.0125
34次移动的平均匹配度为:19.033333333333335
35次移动的平均匹配度为:17.99375
36次移动的平均匹配度为:18.15625
37次移动的平均匹配度为:16.922916666666666
38次移动的平均匹配度为:17.4375
39次移动的平均匹配度为:16.56875
40次移动的平均匹配度为:16.835416666666667
41次移动的平均匹配度为:16.025
42次移动的平均匹配度为:15.947916666666666
43次移动的平均匹配度为:15.227083333333333
44次移动的平均匹配度为:15.589583333333334
45次移动的平均匹配度为:14.9875
46次移动的平均匹配度为:15.079166666666667
47次移动的平均匹配度为:14.35625
48次移动的平均匹配度为:15.154166666666667
49次移动的平均匹配度为:14.172916666666667
50次移动的平均匹配度为:14.36875
51次移动的平均匹配度为:13.55
52次移动的平均匹配度为:14.310416666666667
53次移动的平均匹配度为:13.410416666666666
54次移动的平均匹配度为:13.533333333333333
55次移动的平均匹配度为:12.829166666666667
56次移动的平均匹配度为:13.741666666666667
57次移动的平均匹配度为:12.604166666666666
58次移动的平均匹配度为:13.183333333333334
59次移动的平均匹配度为:12.610416666666667
匹配度最高为:100.0,最低为:12.604166666666666
4x4,0-59结果
在59的位置，图像仍有下降趋势，所以下面加到移动的次数到100次的结果
0次移动的平均匹配度为:100.0
1次移动的平均匹配度为:87.5
2次移动的平均匹配度为:81.25
3次移动的平均匹配度为:75.0
4次移动的平均匹配度为:69.675
5次移动的平均匹配度为:63.7875
6次移动的平均匹配度为:59.7
7次移动的平均匹配度为:55.58125
8次移动的平均匹配度为:52.71875
9次移动的平均匹配度为:48.38125
10次移动的平均匹配度为:45.89375
11次移动的平均匹配度为:41.76875
12次移动的平均匹配度为:40.4375
13次移动的平均匹配度为:37.0625
14次移动的平均匹配度为:35.95625
15次移动的平均匹配度为:34.65
16次移动的平均匹配度为:32.5625
17次移动的平均匹配度为:30.4875
18次移动的平均匹配度为:29.7625
19次移动的平均匹配度为:28.54375
20次移动的平均匹配度为:27.69375
21次移动的平均匹配度为:25.5125
22次移动的平均匹配度为:25.56875
23次移动的平均匹配度为:24.8125
24次移动的平均匹配度为:24.3375
25次移动的平均匹配度为:22.43125
26次移动的平均匹配度为:23.05625
27次移动的平均匹配度为:21.4875
28次移动的平均匹配度为:21.24375
29次移动的平均匹配度为:19.4625
30次移动的平均匹配度为:20.4125
31次移动的平均匹配度为:19.21875
32次移动的平均匹配度为:19.16875
33次移动的平均匹配度为:18.6375
34次移动的平均匹配度为:18.55
35次移动的平均匹配度为:17.5375
36次移动的平均匹配度为:18.275
37次移动的平均匹配度为:16.5875
38次移动的平均匹配度为:17.5375
39次移动的平均匹配度为:16.5625
40次移动的平均匹配度为:16.56875
41次移动的平均匹配度为:15.9125
42次移动的平均匹配度为:15.25
43次移动的平均匹配度为:15.55
44次移动的平均匹配度为:15.61875
45次移动的平均匹配度为:14.55
46次移动的平均匹配度为:14.88125
47次移动的平均匹配度为:14.73125
48次移动的平均匹配度为:14.84375
49次移动的平均匹配度为:13.88125
50次移动的平均匹配度为:14.39375
51次移动的平均匹配度为:12.68125
52次移动的平均匹配度为:13.64375
53次移动的平均匹配度为:13.38125
54次移动的平均匹配度为:13.15
55次移动的平均匹配度为:12.6125
56次移动的平均匹配度为:13.31875
57次移动的平均匹配度为:12.60625
58次移动的平均匹配度为:12.90625
59次移动的平均匹配度为:12.98125
60次移动的平均匹配度为:13.1875
61次移动的平均匹配度为:12.16875
62次移动的平均匹配度为:12.50625
63次移动的平均匹配度为:11.9375
64次移动的平均匹配度为:12.1
65次移动的平均匹配度为:11.8625
66次移动的平均匹配度为:12.1375
67次移动的平均匹配度为:11.3125
68次移动的平均匹配度为:12.06875
69次移动的平均匹配度为:11.3375
70次移动的平均匹配度为:11.4
71次移动的平均匹配度为:10.7875
72次移动的平均匹配度为:12.15625
73次移动的平均匹配度为:11.14375
74次移动的平均匹配度为:11.6375
75次移动的平均匹配度为:10.4875
76次移动的平均匹配度为:11.45
77次移动的平均匹配度为:10.83125
78次移动的平均匹配度为:11.5875
79次移动的平均匹配度为:10.31875
80次移动的平均匹配度为:10.5875
81次移动的平均匹配度为:10.20625
82次移动的平均匹配度为:10.975
83次移动的平均匹配度为:10.1375
84次移动的平均匹配度为:10.2625
85次移动的平均匹配度为:9.7875
86次移动的平均匹配度为:10.35
87次移动的平均匹配度为:9.95625
88次移动的平均匹配度为:10.3375
89次移动的平均匹配度为:9.6
90次移动的平均匹配度为:10.4125
91次移动的平均匹配度为:9.8625
92次移动的平均匹配度为:10.04375
93次移动的平均匹配度为:9.28125
94次移动的平均匹配度为:9.94375
95次移动的平均匹配度为:9.24375
96次移动的平均匹配度为:9.975
97次移动的平均匹配度为:9.38125
98次移动的平均匹配度为:10.10625
99次移动的平均匹配度为:9.4125
匹配度最高为:100.0,最低为:9.24375
4x4,0-100结果
得出结论
最后我们在测试一下200的，结果如下:
0次移动的平均匹配度为:100.0
1次移动的平均匹配度为:87.5
2次移动的平均匹配度为:81.25
3次移动的平均匹配度为:75.0
4次移动的平均匹配度为:69.575
5次移动的平均匹配度为:64.0375
6次移动的平均匹配度为:59.7875
7次移动的平均匹配度为:55.225
8次移动的平均匹配度为:52.425
9次移动的平均匹配度为:47.9125
10次移动的平均匹配度为:46.475
11次移动的平均匹配度为:43.0875
12次移动的平均匹配度为:40.1375
13次移动的平均匹配度为:38.2625
14次移动的平均匹配度为:36.4625
15次移动的平均匹配度为:33.8625
16次移动的平均匹配度为:33.05
17次移动的平均匹配度为:30.65
18次移动的平均匹配度为:29.5125
19次移动的平均匹配度为:27.7375
20次移动的平均匹配度为:27.2
21次移动的平均匹配度为:25.225
22次移动的平均匹配度为:25.5125
23次移动的平均匹配度为:24.1
24次移动的平均匹配度为:23.8375
25次移动的平均匹配度为:23.1375
26次移动的平均匹配度为:22.5375
...........省略n行..................
178次移动的平均匹配度为:7.975
179次移动的平均匹配度为:6.4625
180次移动的平均匹配度为:7.5875
181次移动的平均匹配度为:6.85
182次移动的平均匹配度为:7.1875
183次移动的平均匹配度为:6.45
184次移动的平均匹配度为:7.4375
185次移动的平均匹配度为:6.825
186次移动的平均匹配度为:7.025
187次移动的平均匹配度为:6.5875
188次移动的平均匹配度为:7.1375
189次移动的平均匹配度为:6.8875
190次移动的平均匹配度为:6.725
191次移动的平均匹配度为:6.6375
192次移动的平均匹配度为:6.65
193次移动的平均匹配度为:6.825
194次移动的平均匹配度为:7.3875
195次移动的平均匹配度为:6.7625
196次移动的平均匹配度为:7.0
197次移动的平均匹配度为:6.4875
198次移动的平均匹配度为:7.275
199次移动的平均匹配度为:6.4125
匹配度最高为:100.0,最低为:6.275
4x4,0-200结果
网友评论