-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathtest_klotski99.py
122 lines (103 loc) · 7.15 KB
/
test_klotski99.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
from klotski import klotski99
numbers = [0, 1, 2, 3, 5, 7, 25, 16, 8, 9, 10, 11, 99, 39, 14, 26, 15, 17, 18, 20, 21, 4, 12, 6, 32, 24, 35, 28, 19, 49,
30, 31, 40, 13, 34, 44, 45, 36, 29, 41, 22, 33, 23, 43, 53, 27, 72, 38, 56, 50, 68, 42, 51, 62, 37, 54, 48,
47, 55, 67, 61, 69, 79, 46, 64, 65, 66, 59, 57, 58, 71, 52, 73, 63, 75, 76, 74, 78, 77, 60, 70]
# 151.8437054157257秒
# 91.57500386238098秒
# 5.013743162155151秒
# 9.509095907211304秒
# 7.042182922363281秒 366
# 43.99808382987976秒 380
# 5.921901702880859秒 368 manhattan_distance加if current_num == target_count:判断
# 7.393173933029175秒 338
# 卡46
# numbers = [10, 0, 11, 2, 3, 13, 6, 7, 8, 1, 28, 20, 12, 5, 4, 16, 17, 26, 19, 9, 39, 21, 38, 14, 25, 35, 33, 18, 29, 49, 30, 23, 31, 50, 32, 15, 27, 37, 36, 41, 24, 44, 40, 53, 34, 45, 56, 47, 42, 22, 51, 43, 60, 61, 54, 46, 55, 58, 48, 59, 52, 99, 62, 72, 64, 66, 57, 67, 77, 68, 79, 70, 65, 63, 73, 74, 75, 76, 69, 78, 71]
# 5.87968111038208秒
# 4.165159225463867秒
# 4.18162989616394秒 393
# 4.343976020812988秒 393 manhattan_distance加if current_num == target_count:判断
# 8.79757809638977秒 317
# numbers = [0, 1, 2, 3, 14, 5, 6, 15, 8, 9, 10, 11, 4, 31, 7, 33, 13, 26, 18, 19, 21, 12, 30, 23, 35, 16, 24, 27, 28, 20, 29, 40, 22, 25, 34, 17, 36, 37, 39, 48, 49, 32, 50, 52, 42, 45, 46, 38, 67, 41, 57, 59, 53, 43, 54, 55, 47, 99, 68, 58, 70, 44, 61, 63, 64, 56, 66, 60, 69, 78, 51, 62, 72, 73, 65, 75, 74, 76, 77, 79, 71]
# 26.121688842773438秒
# 27.186790943145752秒
# 98.94178318977356秒
# 14.906550884246826秒
# 4.032459020614624秒
# 4.8068318367004395秒
# 4.0802130699157715秒 307
# 1.9961750507354736秒 359 manhattan_distance加if current_num == target_count:判断
# 0.9605550765991211秒 285
# 3.1222119331359863秒 263
# numbers = [0, 12, 1, 2, 3, 14, 6, 7, 8, 20, 36, 21, 11, 5, 4, 15, 16, 17, 9, 29, 10, 13, 22, 23, 24, 25, 26, 19, 18, 37, 30, 31, 32, 33, 35, 44, 27, 47, 28, 57, 39, 41, 42, 34, 53, 45, 46, 38, 56, 64, 50, 52, 43, 62, 63, 54, 72, 67, 66, 59, 51, 61, 70, 75, 48, 65, 74, 58, 40, 68, 78, 79, 99, 55, 49, 73, 76, 77, 60, 69, 71]
# 15.028950929641724秒
# 16.173922061920166秒
# 3.7556631565093994秒 286
# 3.47674298286438秒 286 manhattan_distance加if current_num == target_count:判断
# 3.483431816101074秒 302
# 4.406541109085083秒 280
# numbers = [0, 11, 20, 1, 4, 2, 17, 7, 26, 9, 37, 3, 99, 13, 15, 16, 5, 24, 12, 28, 10, 30, 22, 14, 33, 8, 25, 19, 21, 27, 39, 31, 23, 34, 6, 35, 36, 18, 29, 38, 40, 32, 41, 43, 44, 45, 46, 56, 47, 49, 50, 42, 52, 53, 54, 55, 66, 57, 77, 58, 59, 60, 62, 72, 64, 48, 65, 74, 67, 51, 61, 71, 73, 63, 75, 68, 76, 78, 69, 70, 79]
# 36.43762421607971秒
# 26.97661519050598秒
# 25.34320616722107秒
# 17.164334774017334秒
# 3.743338108062744秒 330 manhattan_distance加if current_num == target_count:判断
# 11.082672834396362秒 348
# 19.89375591278076秒 348
# numbers = [0, 2, 3, 4, 23, 15, 5, 6, 8, 9, 1, 10, 22, 12, 13, 24, 7, 17, 18, 21, 11, 30, 31, 14, 25, 16, 34, 27, 19, 20, 40, 52, 41, 32, 35, 33, 28, 37, 29, 38, 66, 50, 42, 99, 26, 45, 36, 46, 39, 58, 49, 62, 43, 44, 54, 56, 57, 65, 59, 78, 70, 51, 53, 72, 55, 73, 47, 74, 77, 69, 61, 60, 64, 63, 67, 76, 75, 48, 68, 79, 71]
# 4.122791767120361秒
# 4.415396213531494秒 359
# 3.5739970207214355秒 423
# 3.6125428676605225秒 339
# numbers = [9, 0, 3, 13, 7, 1, 15, 14, 6, 18, 11, 26, 12, 2, 32, 35, 5, 8, 27, 10, 19, 29, 4, 21, 23, 17, 16, 36, 37, 30, 22, 41, 31, 25, 24, 34, 48, 45, 20, 39, 49, 50, 33, 43, 44, 46, 28, 56, 47, 57, 58, 42, 51, 53, 38, 72, 65, 66, 59, 40, 69, 52, 61, 55, 73, 74, 75, 67, 77, 68, 71, 62, 54, 99, 63, 64, 76, 78, 60, 70, 79]
# 卡2
# 20.794519186019897秒 341 manhattan_distance加if current_num == target_count:判断
# 卡27
# 卡2
# numbers = [1, 11, 2, 5, 13, 6, 16, 17, 25, 28, 0, 10, 3, 12, 7, 23, 8, 35, 18, 19, 29, 20, 21, 30, 14, 26, 34, 36, 38, 37, 4, 40, 24, 44, 31, 15, 9, 27, 47, 48, 39, 32, 33, 43, 53, 45, 56, 55, 58, 49, 22, 51, 41, 52, 54, 64, 46, 57, 67, 50, 60, 42, 70, 63, 73, 66, 59, 68, 69, 99, 62, 61, 72, 74, 65, 75, 76, 77, 78, 79, 71]
# 卡40
# 5.63921594619751秒 421 manhattan_distance加if current_num == target_count:判断
# 6.2067952156066895秒 383
# 7.080444812774658秒 525
# 6.724484920501709秒 395
# numbers = [2, 11, 9, 3, 13, 4, 5, 7, 8, 1, 10, 0, 12, 23, 24, 15, 26, 16, 99, 18, 38, 20, 29, 14, 6, 25, 34, 27, 19, 47, 21, 30, 31, 52, 35, 17, 36, 37, 28, 39, 22, 40, 32, 33, 53, 45, 57, 55, 56, 41, 43, 71, 50, 44, 64, 46, 74, 48, 49, 61, 60, 62, 51, 54, 65, 66, 67, 59, 58, 77, 69, 79, 63, 72, 73, 75, 76, 78, 68, 42, 70]
# 无解 卡30
# 1.3144161701202393秒 252 修复manhattan_distance 的target_num问题
# numbers = [9, 0, 1, 2, 3, 5, 16, 6, 8, 18, 10, 12, 21, 4, 13, 7, 25, 17, 27, 20, 11, 22, 23, 31, 24, 15, 26, 37, 19, 50, 56, 14, 33, 99, 51, 35, 36, 29, 41, 32, 49, 40, 34, 42, 44, 45, 28, 38, 30, 67, 52, 60, 43, 53, 54, 57, 47, 55, 39, 62, 68, 59, 61, 64, 46, 65, 48, 58, 76, 69, 71, 78, 63, 72, 73, 66, 74, 75, 77, 79, 70]
# 卡在42
# 1.4798078536987305秒 275 修复manhattan_distance 的target_num问题
# numbers = [9, 0, 11, 14, 4, 13, 6, 8, 16, 2, 10, 1, 12, 3, 15, 5, 26, 7, 18, 99, 19, 29, 23, 32, 22, 24, 25, 28, 21, 20, 30, 31, 33, 43, 51, 44, 27, 45, 38, 39, 41, 42, 50, 35, 61, 37, 36, 55, 47, 48, 49, 60, 17, 62, 63, 54, 46, 58, 40, 59, 52, 34, 53, 64, 65, 56, 57, 67, 68, 70, 71, 79, 72, 73, 74, 66, 75, 76, 77, 69, 78]
# 卡 18
# 3.584275245666504秒 263
# 4.287180662155151秒 261
# numbers = [21, 20, 1, 2, 3, 4, 5, 7, 8, 9, 0, 40, 18, 12, 14, 16, 25, 17, 19, 11, 10, 29, 6, 22, 23, 15, 35, 28, 36, 31, 39, 13, 24, 42, 43, 33, 45, 27, 37, 48, 30, 58, 34, 26, 44, 54, 46, 38, 57, 51, 41, 32, 52, 53, 55, 56, 47, 99, 50, 49, 60, 61, 62, 63, 64, 65, 66, 67, 59, 68, 69, 70, 72, 73, 74, 75, 76, 77, 78, 79, 71]
# 18.806761026382446秒
# 20.898056030273438秒
# 72.39168286323547秒
# 13.048104047775269秒
# 12.118600845336914秒
# 7.766463041305542秒 465
# 无解 manhattan_distance加if current_num == target_count:判断
# 9.070811986923218秒 411 distance += 20 * (abs(i - row) + abs(j - col))
# 5.798565149307251秒 305 (abs(i - row) + abs(j - col)) * (abs(i - row) + abs(j - col))
# 卡29
# 卡21
numbers = [0, 10, 1, 2, 4, 13, 5, 15, 8, 9, 19, 3, 30, 12, 7, 25, 26, 17, 18, 20, 11, 39, 14, 23, 6, 31, 16, 36, 29, 40, 27, 41, 21, 24, 34, 35, 37, 46, 28, 47, 50, 22, 52, 43, 33, 45, 99, 49, 57, 48, 69, 42, 53, 61, 54, 55, 38, 56, 58, 51, 70, 59, 44, 63, 64, 65, 75, 76, 32, 67, 71, 62, 72, 73, 74, 68, 66, 77, 60, 78, 79]
steps = klotski99.get_path_warp(numbers)
print(len(steps))
print(steps)
print("打印移动")
current_state = numbers
for path in steps:
index = path
zero_index = current_state.index(99)
current_state[zero_index] = current_state[index]
current_state[index] = 99
print(current_state)
expect_result = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27,
28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53,
54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79,
99]
if current_state == expect_result:
print("移动正确")
else:
print("移动错误")