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

yanyongyu

dee422

学习

苟或dd

看看

终焉☆轮回

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

qaz123765

看看

tangoing

HAHH

Wolveriner

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 = [None]*(n*n) # 一个解，长度固定64，形如[(2,2),(4,3),...]
X = []        # 一组解


# 冲突检测
def conflict(k):
    global n,p, x, X
   
    # 步子 x[k] 超出边界
    if x[k][0] < 0 or x[k][0] >= n or x[k][1] < 0 or x[k][1] >= n:
        return True
   
    # 步子 x[k] 已经走过
   
    if x[k] 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[k-1] 的状态空间: 8个方向
            x[k] = (x[k-1][0] + i[0], x[k-1][1] + i[1])
            if not conflict(k): # 剪枝
                subsets(k+1)



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

kaibin051525

i love fishc

821218213

参考一下谢谢

焦焦焦

咦

leige111

学习一下

ghoob321

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

小小小菜菜菜

观摩学习

806863

想看

xz_liuyj

fenytk

学习学习

569000802

想学习

dqgwm

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

shanjiwan

shanjiwan

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

global X
global Y

X=8
Y=8

global board

board=[[0 for i in range(X)] for i in range(Y)]

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

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

TravelChessBoard(2,0,1)