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

jasonzkz

厉害了，学习了

hanzhi0215

学习了

梦竹风

抱着学习的态度来看

小屿丶

学到了

sinaop

RockZhang9969

感谢分享

python初学者021

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

methanecn

1

klozi

看一下

m936761880

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

python初学者021

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

但是脚本的执行效率很低

8X8的，感觉算不出来啊

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

python初学者021

我的代码

#!/usr/bin/python3 -B
import time

def next_x_y(point, order):
        x_y_list = [point[0], point[1]]

        if order == 1:
                x_y_list[0] = int(x_y_list[0]) + 1
                x_y_list[1] = int(x_y_list[1]) + 2
                return x_y_list

        if order == 2:
                x_y_list[0] = int(x_y_list[0]) + 2
                x_y_list[1] = int(x_y_list[1]) + 1
                return x_y_list

        if order == 3:
                x_y_list[0] = int(x_y_list[0]) + 2
                x_y_list[1] = int(x_y_list[1]) - 1
                return x_y_list

        if order == 4:
                x_y_list[0] = int(x_y_list[0]) + 1
                x_y_list[1] = int(x_y_list[1]) - 2
                return x_y_list

        if order == 5:
                x_y_list[0] = int(x_y_list[0]) - 1
                x_y_list[1] = int(x_y_list[1]) - 2
                return x_y_list

        if order == 6:
                x_y_list[0] = int(x_y_list[0]) - 2
                x_y_list[1] = int(x_y_list[1]) - 1
                return x_y_list

        if order == 7:
                x_y_list[0] = int(x_y_list[0]) - 2
                x_y_list[1] = int(x_y_list[1]) + 1
                return x_y_list

        if order == 8:
                x_y_list[0] = int(x_y_list[0]) - 1
                x_y_list[1] = int(x_y_list[1]) + 2
                return x_y_list

def check_legal(next_point):
        if 1 <= next_point[0] and next_point[0] <= size_of_x and 1 <= next_point[1] and next_point[1] <= size_of_y:
                return True
        else:
                return False

size_of_x = int(input("Please input the size of X :"))
size_of_y = int(input("Please input the size of Y :"))

start_point = input("Please input start point : ")

start_time = time.time()

main_list = []
main_order_list = []

main_list.append(start_point)
main_order_list.append(1)

end_of_search = False

while not end_of_search:

        if main_order_list[-1] >= 8:
                main_list.pop()
                main_order_list.pop()
                main_order_list[-1] += 1
                continue


        next_point = next_x_y(main_list[-1], main_order_list[-1])
        next_point_str = "".join([str(x) for x in next_point])

        if  (not next_point_str in main_list) and (check_legal(next_point)):
                main_list.append("".join([str(x) for x in next_point]))
                main_order_list.append(1)

                if len(main_list) == int(size_of_x * size_of_y):
                        print ("++++++++++++++++++ Find one solution ++++++++++++++++")
                        print(main_list)
                        print(main_order_list)
                        print ("+++++++++++++++++++++++++++++++++++++++++++++++++++++")
                        print("")


        else:
                if main_order_list[-1] >= 8:
                        main_list.pop()
                        main_order_list.pop()
                        main_order_list[-1] += 1
                else:
                        main_order_list[-1] += 1

        shrink_order = list(set(main_order_list))
        if len(shrink_order) == 1 and shrink_order[0] == 8:
                end_of_search = True

end_time = time.time()

used_time = end_time - start_time

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不吐骨头

学习了，谢谢