← 都来码 / Dolaima← 例程索引python/school/066.py 原文

python/school/066.py · 1556 字节 · 下载原文

'''八皇后问题。八皇后问题是高斯先生(就是小时候就把1+2+3+...+100转换成(1+100)*50的那个数学家)在60多年以前提出来的,
是一个经典的回溯算法问题,其核心为:在国际象棋棋盘(8行8列)上摆放8个皇后,
要求8个皇后中任意两个都不能位于同一行、同一列或同一斜线上。'''

def isValid(s, col):
    '''这个函数用来检查最后一个皇后的位置是否合法'''
    #当前皇后的行号
    row = len(s)
    #检查当前的皇后们是否有冲突
    for r, c in enumerate(s):
        #如果这一列已有皇后,或者某个皇后与当前皇后的水平与垂直距离相等
        #就表示当前皇后位置不合法,不允许放置
        if c == col or abs(row - r) == abs(col - c):
            return False
 
    return True
 
def queen(n, s=()):
    '''这个函数返回的结果是每个皇后所在列号'''
    #已是最后一个皇后,保存本次结果
    if len(s) == n:
        return [s]
 
    res = []
    for col in range(n):
        if not isValid(s, col): continue
        for r in queen(n, s + (col,)):
            res.append(r)
 
    return res

#形式转换,最终结果中包含每个皇后所在的行号和列号
result = [[(r, c) for r, c in enumerate(s)] for s in queen(8)]
#输出合法结果的数量
print(len(result))
#输出所有可能的结果,也就是所有皇后的摆放位置
#结果中每个皇后的位置是一个元组,里面两个数分别是行号和列号
for r in result:
    print(r)