手记

八皇后,肝了好几天。终于出来了,内牛满面

import numpy as np

board=np.zeros(shape=(8,8),dtype=int)#生成一个全零的8*8数组
#print(board)
total=0
#打印函数
def print_queen():
    for i in range(8):
        for j in range(8):
            if board[i][j]==0:      #在8*8的棋盘里检查是否有值,分别标记,END=""参数表示打印完成不换行
                print("□",end="  ")
            else:
                print("■", end="  ")
        print()                     #循环8次打完一行就应该换行了
    print("---------------------------")#完成棋盘后 打出标记段
    global total
    total+=1
    print("一共有{}种方法".format(total))

#判断函数
def can_place(x,y):
   #判断X,Y坐标能否放皇后
    for i in range(0,y): #对行从0到Y列进行检查
        if board[x][i]==1: #因为是从左往右放,对左边进行检查
            return False

    for i in range(0,x):
        if board[i][y]==1:#对Y轴上方的每一个X检查是否有值 I变量接收的是从第零行到第X行
            return False
    for i in range(0,x):#逐行检查正斜线方向

        if x+y-i<=7 and board[i][x+y-i]==1:

            return False
              #对正斜线进行检查,坐标值的总合不会发生变化,在Y轴上的偏移所增加的值是X轴上减少的值,y值为函数传入的纵坐标值
    for index,i in enumerate(range(x-1,-1,-1)):  # 反斜线方向递减从Y轴上反向递减查找,设定步长为1
        s_y=y-(index+1)
        if s_y >= 0:
            if board[i][s_y]==1:
                return False
                    #反斜方向上 X值从X-1开始,Y 从-(执行次数+1)开始 结果为当前坐标的反斜方向
    return True


#主函数执行回溯及递归
def put_queen(step):  #参数为回传的执行次数
    if step==8:  #设置递归退出条件,开始输出结果
        print_queen()
    else:   #不满足退出条件,执行回溯递归
        for i in range(8): #最大执行边界为行的末尾
            #执行判断 该位置能否放皇后,调用判断函数,传入参数为X轴为步长可以理解为第几行,Y轴为I循环的次数,第几次尝试可以理解为列
            if can_place(step,i)==True:
                #设置回溯现场
                board[step][i]=1
                #开始递归,参数为执行步长+1
                put_queen(step+1)

                #恢复回溯现场
                board[step][i]=0

#print_queen()

put_queen(0)


2人推荐
随时随地看视频
慕课网APP