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

yanyongyu 发表于 2019-2-27 19:27:55

{:7_113:}

dee422 发表于 2019-5-7 05:17:12

学习

苟或dd 发表于 2019-7-11 12:11:43

看看

终焉☆轮回 发表于 2019-7-12 18:41:54

请教一下你这个除了输入0,0有输出之外其他的好像都没输出

qaz123765 发表于 2019-7-16 08:42:27

看看

tangoing 发表于 2019-10-4 17:33:07

HAHH

Wolveriner 发表于 2019-10-7 23:28:41

n = 5 # 8太慢了，改为5
p = [(-2,1),(-1,2),(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1)] # 状态空间，8个方向


entry = (2,2) # 出发地

x = *(n*n) # 一个解，长度固定64，形如[(2,2),(4,3),...]
X = []      # 一组解


# 冲突检测
def conflict(k):
    global n,p, x, X
   
    # 步子 x 超出边界
    if x < 0 or x >= n or x < 0 or x >= n:
      return True
   
    # 步子 x 已经走过
   
    if x in x[:k]:
      return True
   
    return False # 无冲突



# 回溯法（递归版本）
def subsets(k): # 到达第k个元素
    global n, p, x, X
   
    if k == n*n:# 超出最尾的元素
      print(x)
      #X.append(x[:]) # 保存（一个解）
    else:
      for i in p: # 遍历元素 x 的状态空间: 8个方向
            x = (x + i, x + i)
            if not conflict(k): # 剪枝
                subsets(k+1)



# 测试
x = entry # 入口
subsets(1)   # 开始走第k=1步

kaibin051525 发表于 2019-10-8 21:54:12

i love fishc

821218213 发表于 2019-11-8 14:52:09

参考一下谢谢

焦焦焦 发表于 2019-11-9 10:53:49

咦

leige111 发表于 2019-11-9 12:29:27

学习一下

ghoob321 发表于 2020-1-3 16:47:16

从任意位置出发，不重复地走完所有64个格子.py求源码

小小小菜菜菜 发表于 2020-1-7 14:12:34

观摩学习

806863 发表于 2020-1-13 07:31:01

想看

xz_liuyj 发表于 2020-1-15 13:22:18

{:10_254:}

fenytk 发表于 2020-1-15 16:40:03

学习学习

569000802 发表于 2020-1-17 16:55:56

想学习

dqgwm 发表于 2020-2-16 10:25:10

good!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

shanjiwan 发表于 2020-5-18 18:43:40

{:5_102:}

shanjiwan 发表于 2020-5-18 21:39:08

楼主我按小甲鱼c的思路用python写了代码，但找不出哪里错了，能帮忙看下吗

global X
global Y

X=8
Y=8

global board

board=[ for i in range(Y)]

def nextxy(temp,count):
    if count==0:
      if (temp-1>=0 and temp-2>=0 and board-1]-2]==0):
            temp=temp-1
            temp=temp-2
            return 1
      else:
            return 0
    if count==1:
      if (temp+1<=X-1 and temp-2>=0 and board+1]-2]==0):
            temp=temp+1
            temp=temp-2
            return 1
      else:
            return 0
    if count==2:
      if (temp+2<=X-1 and temp-1>=0 and board+2]-1]==0):
            temp=temp+2
            temp=temp-1
            return 1
      else:
            return 0
    if count==3:
      if (temp+2<=X-1 and temp+1<=Y-1 and board+2]+1]==0):
            temp=temp+2
            temp=temp+1
            return 1
      else:
            return 0
    if count==4:
      if (temp+1<=X-1 and temp+2<=Y-1 and board+1]+2]==0):
            temp=temp+1
            temp=temp+2
            return 1
      else:
            return 0
    if count==5:
      if (temp-1>=0 and temp+2<=Y-1 and board-1]+2]==0):
            temp=temp-1
            temp=temp+2
            return 1
      else:
            return 0
    if count==6:
      if (temp-2>=0 and temp+1<=Y-1 and board-2]+1]==0):
            temp=temp-2
            temp=temp+1
            return 1
      else:
            return 0
    if count==7:
      if (temp-2>=0 and temp-1>=0 and board-2]-1]==0):
            temp=temp-2
            temp=temp-1
            return 1
      else:
            return 0
    return 0

def TravelChessBoard(x,y,tag):
    count=0
    board=tag
    if tag==X*Y:
      return 1
    temp=
    flag=nextxy(temp,count)
    while flag==0 and count<X-1:
      count+=1
      flag=nextxy(temp,count)
    while flag==1:
      x1,y1=temp,temp
      if TravelChessBoard(x1,y1,tag+1):
            return 1
      count+=1
      temp=
      flag=nextxy(temp,count)
      while flag==0 and count<X-1:
            count+=1
            flag=nextxy(temp,count)         
    if flag==0:
      board=0
    return 0

TravelChessBoard(2,0,1)

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