Python:四皇后问题_python4皇后问题

概要：

四皇后问题出现在回溯算法里，所以主要采用回溯算法解决

一共有三个函数实现，作用分别是初始化棋盘，选择皇后所在位置，显示出来

第一个函数：InitGrid(d)

def InitGrid(d):
    """
    功能：棋盘初始化
    参数：d表示矩阵的大小
    """
    grid=[[(x+1,y+1) for y in range(d)] for x in range(d)]
    return grid
    # 这里是利用列表推导式初始化棋盘，相当于：
    # grid=[]
    # for x in range(d): # 生成行
    #     a=[]
    #     for y in range(d): # 生成列
    #        a.append((x+1,y+1))
    #     grid.append(a)
    

第二个函数：fill(grid,rowIndex,position,backtracking):

import math
import random
 
def fill(grid,rowIndex,position,backtracking):
    """
    功能：指定行过滤出可选位置，随机选取一个，作为本行“皇后”的填入位置
    参数：grid：棋盘矩阵
         rowIndex：指定矩阵的某一行的序号
         position：已被选的位置
         backtracking：回溯时的排除项列表
    """
    row=grid[rowIndex] # 每次都取一行
    optional=[]
    if len(position)!=0:
        for column in row:
            avaliable=True
            for item in position:
                if column[1]==item[1] or column[0]+column[1]==item[0]+item[1] or\                 
                    column[0]-column[1]==item[0]-item[1] or column in backtracking:
                    # 不可能出现同行，所以是防止出现在同列，同斜线/或\，或位于排除项列表中
                    available=False
            if available:
                optional.append(column)
    else:
        optional=row
    if len(optional)==0:
        return 0
    else:
        radomIndex=math.floor(len(optional)*random.random())
        # math.floor()是直接截取浮点数的整数部分
        # random.random()是随机取[0,1)的中的任意整数或分数
        pick=optional[randomIndex]
        position.append(pick)
        return 1

第三个函数：show(positions):

def show(positions):
    """
    功能：将最终结果用棋盘网格显示出来
    参数：positions：最终挑选的位置列表
    """
    figure=''
    for row in range(4):
        for line in range(4):
            if (row+1,line+1) in positions:
                figure+='Q '
            else:
                figure+='# '
        figure+='\n'
    return figure

总的代码：

import math
import random
 
def InitGrid(d):
    """
    功能：棋盘初始化
    参数：d表示矩阵的大小
    """
    grid=[[(x+1,y+1) for y in range(d)] for x in range(d)]
    return grid
    # 这里是利用列表推导式初始化棋盘，相当于：
    # grid=[]
    # for x in range(d): # 生成行
    #     a=[]
    #     for y in range(d): # 生成列
    #        a.append((x+1,y+1))
    #     grid.append(a)
    
def fill(grid,rowIndex,position,backtracking):
    """
    功能：指定行过滤出可选位置，随机选取一个，作为本行“皇后”的填入位置
    参数：grid：棋盘矩阵
         rowIndex：指定矩阵的某一行的序号
         position：已被选的位置
         backtracking：回溯时的排除项列表
    """
    row=grid[rowIndex] # 每次都取一行
    optional=[]
    if len(position)!=0:
        for column in row:
            avaliable=True
            for item in position:
                if column[1]==item[1] or column[0]+column[1]==item[0]+item[1] or\                 
                    column[0]-column[1]==item[0]-item[1] or column in backtracking:
                    # 不可能出现同行，所以是防止出现在同列，同斜线/或\，或位于排除项列表中
                    available=False
            if available:
                optional.append(column)
    else:
        optional=row
    if len(optional)==0:
        return 0
    else:
        radomIndex=math.floor(len(optional)*random.random())
        # math.floor()是直接截取浮点数的整数部分
        # random.random()是随机取[0,1)的中的任意整数或分数
        pick=optional[randomIndex]
        position.append(pick)
        return 1
 
def show(positions):
    """
    功能：将最终结果用棋盘网格显示出来
    参数：positions：最终挑选的位置列表
    """
    figure=''
    for row in range(4):
        for line in range(4):
            if (row+1,line+1) in positions:
                figure+='Q '
            else:
                figure+='# '
        figure+='\n'
    return figure
"""主运行代码"""
grid=InitGrid(4)
position=[]
backtracking=[[] for i in range(4)]
row=0
while row<4:
    success=fill(grid,row,position,backtracking[row])
    if success==1:
        row+=1
    else:
        row-=1
        backtracking[row].append(position.pop())
        if row<3:
            backtracking[row+1]=[]
print(show(positon))

如果是八皇后问题：

就将数字4改成8，第77行的数字3改成7，就变成了八皇后问题