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

jasonzkz 发表于 2020-8-28 22:20:02

厉害了，学习了

hanzhi0215 发表于 2020-8-28 23:17:03

学习了

梦竹风 发表于 2020-9-8 21:21:12

抱着学习的态度来看

小屿丶 发表于 2021-1-6 18:22:03

学到了

sinaop 发表于 2021-1-6 19:11:03

{:5_111:}

RockZhang9969 发表于 2021-4-6 11:46:24

感谢分享

python初学者021 发表于 2021-4-6 16:30:36

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

methanecn 发表于 2021-4-6 20:39:10

1

klozi 发表于 2021-4-6 21:38:21

看一下

m936761880 发表于 2021-4-7 03:14:06

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

python初学者021 发表于 2021-4-7 16:18:57

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

但是脚本的执行效率很低

8X8的，感觉算不出来啊

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

python初学者021 发表于 2021-4-7 16:28:03

我的代码

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

def next_x_y(point, order):
        x_y_list = , point]

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

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

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

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

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

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

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

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

def check_legal(next_point):
        if 1 <= next_point and next_point <= size_of_x and 1 <= next_point and next_point <= 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()

        if(not next_point_str in main_list) and (check_legal(next_point)):
                main_list.append("".join())
                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 == 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']

+++++++++++++++++++++++++++++++++++++++++++++++++++++

++++++++++++++++++ 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']

+++++++++++++++++++++++++++++++++++++++++++++++++++++

++++++++++++++++++ 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']

+++++++++++++++++++++++++++++++++++++++++++++++++++++

Use      2.272 second.

Marcus_c 发表于 2021-6-9 23:11:48

1

qweasdzxc1 发表于 2021-10-25 15:37:07

你好，可以看一下代码吗

akaifg 发表于 2022-1-28 19:26:35

111

joker9420 发表于 2022-3-29 11:06:43

看看

shabei 发表于 2022-3-29 15:42:12

学习一下

吃yu不吐骨头 发表于 2022-4-26 13:37:47

学习了，谢谢

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