python实现八皇后问题和遇见的问题使用深度优先bfs和广度优先dfs

人工智能课程小作业，python用着不习惯，因此写了一下午，这里分享一下，其中dfs使用的是递归。
如果用c 或者java，应该比较快，使用python遇见了很多坑

1.代码实现

print("===============================================")




class Point:
    def __init__(self, x, y, board):
        self.x=x
        self.y=y
        self.board=board


def BFS(n):
    n=int(n)
    queue = []
    for i in range(n):
        board = initBoard(n)
        board[0][i]=1
        point = Point(0,i,board)
        queue.append(point)
    res = 0
    while(len(queue) != 0):
        point = queue.pop(0)
        row=point.x
        col=point.y

        if(row==n-1): #已经最后一行,直接输出
            res  = 1
            print("---------------------------")
            print("第", res, "种结果如下：")
            print(point.board)
        else:
            for j in range(n):
                if(check(point.board, row   1, j, n)):
                    #这个点可以加入到队列之中
                    board=copy.deepcopy(point.board)
                    board[row 1][j] = 1
                    temp = Point(row   1, j, board)
                    queue.append(temp)
    print("当输入为", n, "时，共计", res, "种方式")
    return



def DFS(n):
    n=int(n)
    print("DFS")
    board = initBoard(n)
    print("打印初始化棋盘")


    print(board)
    print("---------------------------------------")



    for i in range(n):
        board[0][i]=1
        dp(n, 1, board)
        board[0][i]=0
    print("当输入为", n, "时，共计", cnt, "种方式")
    return

def dp(n, row, board): #print("调用dp函数")
    if(row == n):
        #能够完成
        global cnt
        cnt =1
        print("第", cnt, "种结果如下：")
        print(board)
        print("-----------------------------------")
        return
    for j in range(n):
        if(check(board, row, j, n)):
            #print("成功",row, " " ,j)
            #修改棋盘
            board[row][j]=1
            row  = 1
            dp(n, row, board)
            row -= 1
            board[row][j]=0
    return


def initBoard(n):
    #初始化全0的2维数组，1代表选择，0代表未被选
    board = np.zeros((n,n),dtype=int)
    return board

#检测新添加的棋子是否合法
def check(board, row, col, n): #向上寻找是否合规
    temp_x=row #行数
    temp_x-=1
    while(temp_x>=0):
        for j in range(n):
            if(board[temp_x][j]==1):
                # print("检测到1的位置",temp_x,",",j)
                # print("原始位置",row,",",col)
                if(j==col or abs(j-col)==abs(temp_x-row)):
                    return False
        temp_x-=1
    return True




while(True):
    choice = input("请选择BFS或者DFS实现(按0代表BFS，按1代表DFS，按q离开)：")
    if (choice == '0'):
        n=input("请输入棋盘大小：")
        BFS(n)
    elif (choice == '1'):
        # global cnt
        cnt = 0
        n=input("请输入棋盘大小：")
        DFS(n)
    elif (choice == 'q'):
        break
    else:
        print("请重新输入！")

2.遇见的坑（主要是不熟悉python语法）

2.1 赋值是浅拷贝

遇到了一个bug，无论怎么赋值都赋值不成功，后来找到问题是浅拷贝，后面的使用了deepcopy成功

2.2 或者运算符是 or

开始以为和c 一样，使用 || 表示，结果报错，改成 | 没有报错，但是程序运行结果不对，找了好久找到问题

2.3 全局变量

python没有指针，写递归没有办法利用指针传值，因此想到了全局变量，但是全局变量不像c 一样写再外面就可以，需要使用global关键字，global关键字的使用也挺复杂的，这里记录一下。

global g
g = 0
def p1():
    c = g 1
    print(c)
def p2():
    g =1
    print(g)
p1()
p2()

上诉代码p1可以运行，但是p2无法运行，结果如下。原因不清楚，希望有大佬解释一下

但是我们再写递归时需要更新这个全局变量，正确的使用方式

g = 0
def p1():
    c = g 1
    print(c)
def p2():
    global g
    g =1
    print(g)
p1()
p2()

把global放进方法里面，而不是在外部定义

这篇好文章是转载于：学新通技术网