八皇后问题（Eight queens），是由国际象棋棋手马克斯·贝瑟尔于1848年提出的问题，是回溯算法的典型案例。

问题描述：

在8×8格的国际象棋盘上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用的图论方法解出92种结果。如果经过±90度、±180度旋转，和对角线对称变换的摆法看成一类，共有42类。

实现代码（忽略旋转&对称）：

import random as r
n = 8 # 国际象棋8行8列
a = [] # 保存一种方案
A = [] # 保存所有方案

# 冲突检测
def conflict(k):
    global n, a, A
    # 遍历之前0~k-1行
    for i in range(k):
        # 如果同列or呈正方形对角之势，则冲突
        if a[k] == a[i] or abs(a[k] - a[i]) == abs(k - i):
            return True
    return False

# 摆放第k行皇后
def queen(k):
    global n, a, A
    # 所有行摆放完毕，保存该方案
    if k >= n:
        A.append(a[:])
    else:
        for i in range(n):
            a.append(i)
            if not conflict(k): # 剪枝
                queen(k + 1)
            a.pop() # 回溯

# 显示一种摆法
def show(k):
    global n, a, A
    src = A[k]
    for i in range(n):
        print("⬜" * src[i] + "♛" + "⬜" * (n - src[i] - 1))

if __name__ == "__main__":
    queen(0)
    print(f"八皇后问题共有{len(A)}种摆法")
    show(r.randint(0, len(A)-1))

输出结果：

八皇后问题共有92种摆法
⬜⬜⬜⬜⬜⬜⬜♛
⬜♛⬜⬜⬜⬜⬜⬜
⬜⬜⬜♛⬜⬜⬜⬜
♛⬜⬜⬜⬜⬜⬜⬜
⬜⬜⬜⬜⬜⬜♛⬜
⬜⬜⬜⬜♛⬜⬜⬜
⬜⬜♛⬜⬜⬜⬜⬜
⬜⬜⬜⬜⬜♛⬜⬜