python小练习（068）：回溯法（深度优先搜索）30行代码求解“马踏棋盘”问题

jasonzkz

厉害了，学习了

hanzhi0215

学习了

梦竹风

抱着学习的态度来看

小屿丶

学到了

sinaop

RockZhang9969

感谢分享

python初学者021

学习一下，这个用递归吗？

methanecn

1

klozi

看一下

m936761880

先回复 再学习。噢耶。加油加油加油

python初学者021

我没有用递归，写了一个脚本

但是脚本的执行效率很低

8X8的，感觉算不出来啊

但是6 X 4 这种，倒是 2秒钟就出来了

python初学者021

我的代码

1. #!/usr/bin/python3 -B
   
2. import time
   
3. 
   
4. def next_x_y(point, order):
   
5.         x_y_list = [point[0], point[1]]
   
6. 
   
7.         if order == 1:
   
8.                 x_y_list[0] = int(x_y_list[0]) + 1
   
9.                 x_y_list[1] = int(x_y_list[1]) + 2
   
10.                 return x_y_list
    
11. 
    
12.         if order == 2:
    
13.                 x_y_list[0] = int(x_y_list[0]) + 2
    
14.                 x_y_list[1] = int(x_y_list[1]) + 1
    
15.                 return x_y_list
    
16. 
    
17.         if order == 3:
    
18.                 x_y_list[0] = int(x_y_list[0]) + 2
    
19.                 x_y_list[1] = int(x_y_list[1]) - 1
    
20.                 return x_y_list
    
21. 
    
22.         if order == 4:
    
23.                 x_y_list[0] = int(x_y_list[0]) + 1
    
24.                 x_y_list[1] = int(x_y_list[1]) - 2
    
25.                 return x_y_list
    
26. 
    
27.         if order == 5:
    
28.                 x_y_list[0] = int(x_y_list[0]) - 1
    
29.                 x_y_list[1] = int(x_y_list[1]) - 2
    
30.                 return x_y_list
    
31. 
    
32.         if order == 6:
    
33.                 x_y_list[0] = int(x_y_list[0]) - 2
    
34.                 x_y_list[1] = int(x_y_list[1]) - 1
    
35.                 return x_y_list
    
36. 
    
37.         if order == 7:
    
38.                 x_y_list[0] = int(x_y_list[0]) - 2
    
39.                 x_y_list[1] = int(x_y_list[1]) + 1
    
40.                 return x_y_list
    
41. 
    
42.         if order == 8:
    
43.                 x_y_list[0] = int(x_y_list[0]) - 1
    
44.                 x_y_list[1] = int(x_y_list[1]) + 2
    
45.                 return x_y_list
    
46. 
    
47. def check_legal(next_point):
    
48.         if 1 <= next_point[0] and next_point[0] <= size_of_x and 1 <= next_point[1] and next_point[1] <= size_of_y:
    
49.                 return True
    
50.         else:
    
51.                 return False
    
52. 
    
53. size_of_x = int(input("Please input the size of X :"))
    
54. size_of_y = int(input("Please input the size of Y :"))
    
55. 
    
56. start_point = input("Please input start point : ")
    
57. 
    
58. start_time = time.time()
    
59. 
    
60. main_list = []
    
61. main_order_list = []
    
62. 
    
63. main_list.append(start_point)
    
64. main_order_list.append(1)
    
65. 
    
66. end_of_search = False
    
67. 
    
68. while not end_of_search:
    
69. 
    
70.         if main_order_list[-1] >= 8:
    
71.                 main_list.pop()
    
72.                 main_order_list.pop()
    
73.                 main_order_list[-1] += 1
    
74.                 continue
    
75. 
    
76. 
    
77.         next_point = next_x_y(main_list[-1], main_order_list[-1])
    
78.         next_point_str = "".join([str(x) for x in next_point])
    
79. 
    
80.         if  (not next_point_str in main_list) and (check_legal(next_point)):
    
81.                 main_list.append("".join([str(x) for x in next_point]))
    
82.                 main_order_list.append(1)
    
83. 
    
84.                 if len(main_list) == int(size_of_x * size_of_y):
    
85.                         print ("++++++++++++++++++ Find one solution ++++++++++++++++")
    
86.                         print(main_list)
    
87.                         print(main_order_list)
    
88.                         print ("+++++++++++++++++++++++++++++++++++++++++++++++++++++")
    
89.                         print("")
    
90. 
    
91. 
    
92.         else:
    
93.                 if main_order_list[-1] >= 8:
    
94.                         main_list.pop()
    
95.                         main_order_list.pop()
    
96.                         main_order_list[-1] += 1
    
97.                 else:
    
98.                         main_order_list[-1] += 1
    
99. 
    
100.         shrink_order = list(set(main_order_list))
     
101.         if len(shrink_order) == 1 and shrink_order[0] == 8:
     
102.                 end_of_search = True
     
103. 
     
104. end_time = time.time()
     
105. 
     
106. used_time = end_time - start_time
     
107. 
     
108. print("Use %10.3f second." %used_time)

复制代码

计算 6 X 4 棋盘的结果，2秒多就出来了

但是 8 X 8 ，尝试过10分钟，都没有出结果

Please input the size of X :6
Please input the size of Y :4
Please input start point : 11
++++++++++++++++++ Find one solution ++++++++++++++++
['11', '23', '31', '12', '24', '32', '51', '63', '44', '52', '64', '43', '62', '41', '53', '61', '42', '54', '33', '14', '22', '34', '13', '21']
[1, 4, 7, 1, 4, 3, 1, 7, 4, 1, 6, 3, 6, 1, 4, 7, 1, 6, 7, 4, 1, 6, 4, 1]
+++++++++++++++++++++++++++++++++++++++++++++++++++++

++++++++++++++++++ Find one solution ++++++++++++++++
['11', '32', '51', '63', '44', '23', '31', '52', '64', '43', '24', '12', '33', '14', '22', '34', '13', '21', '42', '54', '62', '41', '53', '61']
[2, 3, 1, 7, 6, 4, 2, 1, 6, 7, 5, 2, 7, 4, 1, 6, 4, 2, 1, 4, 6, 1, 4, 1]
+++++++++++++++++++++++++++++++++++++++++++++++++++++

++++++++++++++++++ Find one solution ++++++++++++++++
['11', '32', '51', '63', '44', '23', '31', '12', '24', '43', '64', '52', '33', '14', '22', '34', '13', '21', '42', '54', '62', '41', '53', '61']
[2, 3, 1, 7, 6, 4, 7, 1, 3, 2, 5, 7, 7, 4, 1, 6, 4, 2, 1, 4, 6, 1, 4, 1]
+++++++++++++++++++++++++++++++++++++++++++++++++++++

Use      2.272 second.

Marcus_c

1

qweasdzxc1

你好，可以看一下代码吗

akaifg

111

joker9420

看看

shabei

学习一下

吃yu不吐骨头

学习了，谢谢