python八皇后问题的两种解法源代码

如本文章标有价格,需议价或其它事情商议请加微信pythonxia

帮国外留学生写的代码,这代码写了很多次。正所谓,温帮而知新,可以为师矣。
解法一:

import time

def init(n):
    n = int(n)
    row = [0] * (n+1)
    box = []
    for i in range(n+1):
        box.append(list(row))            # 每一行的索引为0的值缺省为1,记录此行皇后索引号的
    
    return box

def is_safe(B,i,j):
    n = len(B)-1    
    direction = [(-1,-1),(-1,0),(-1,1)]
    
    for d in direction:
        dx,dy = d
        r = i                # 行
        c = j                # 列  
        while True:
            r = r + dx
            c = c + dy
            if r>=1 and r<=n and c>=1 and c<=n:
                if B[r][c]==1 :                    
                    return False
            else:               
                break    
    return True
            
def printBoard(B):
    
    n = len(B)-1
    s = [B[i][0] for i in range(1,n+1)]
    print(tuple(s))
        
def removeQueen(B,i,j):
    """移除i行的皇后"""
    
    for x in range(1,len(B)):
        B[i][x] = 0
        
def placeQueen(B,i,j):
    """放皇后,首先移除i行的皇后"""
    removeQueen(B,i,j-1)

    B[i][j] = 1
    B[i][0] = j


def findSolutions(B,i,mode=None):
    
    global acc_sum    
    n = len(B)-1
    if i > n:
        if mode=='-v':            
            printBoard(B)        
            acc_sum += 1
        return 1
    else:
        for j in range(1,len(B)):           
            if is_safe(B,i,j):                 
                placeQueen(B,i,j)                
                findSolutions(B,i+1,mode)
          
    return acc_sum

def main():
    import sys
    p = sys.argv
    p = ['Queen.py','-v','5']
    if len(p)==1:
        print("Usage: python3 Queens.py [-v] number")
    elif len(p)==2:
        if p[1].isnumeric():
            a = init(p[1])            
            findSolutions(a,1)
            print(f"{p[1]}-Queens.py has {len(box)} solutions")
        else:
            print("Usage: python3 Queens.py [-v] number")
    else:
        a = init(p[2])
         
        findSolutions(a,1,p[1])
         
        print(f"{p[2]}-Queens.py has {acc_sum} solutions")
        
if __name__ == '__main__':
   acc_sum = 0
   main()

      

八皇后问题解决法二:

import sys

def no_conflict(board,row,col):
    """检测row行,col列上的皇后是否和其它的皇后有冲突"""
    i = 0
    while i < row:
        if abs(col-board[i]) in (0,abs(row-i)):
            return False
        i += 1
    return True

def EightQueen(board,row):
    global box
    blen = len(board)
    if row == blen:               # 索引为8了,则输出一个方案
        box.append(tuple(board))
        return True
    col = 0
    while col < blen:
        if no_conflict(board,row,col):  # 如果没有冲突,则摆一颗皇后
            board[row] = col
            EightQueen(board,row+1)     # 摆下一行                
        col += 1                        # 同一行,下一列

def main():
    global box    
    p = sys.argv
    p = ['Queen.py','-v','7']
    if len(p)==1:
        print("Usage: python3 Queens.py [-v] number")
    elif len(p)==2:
        if p[1].isnumeric():
            a = [None]*int(p[1])
            EightQueen(a,0)
            print(f"{p[1]}-Queens.py has {len(box)} solutions")
        else:
            print("Usage: python3 Queens.py [-v] number")
    else:
        a = [None]*int(p[2])
        EightQueen(a,0)
        for b in box:
            print(b)
        print(f"{p[2]}-Queens.py has {len(box)} solutions")
            
if __name__== '__main__':

    box = []
    main()
    
    
    

本站所有作品,教程等皆为原创,版权所有。只供个人及单位内部研究使用,对外展示或传播必需经本站同意,且注明来自本站。培训机构等用本站资源培训学生,需经本站授权。一旦付款,表示同意本站知识付费原则:数字商品,不支持退款。亦可直接向微信号scratch8付款购买。入住QQ群:225792826 和爱好者共同交流,并且能下载免费提供的Python资源(需提供真实姓名才可入群)
李兴球的博客_Python创意编程技术前沿_pygame » python八皇后问题的两种解法源代码
scratch

学本领,探索更大的世界!

李兴球博客 风火轮编程主页