这个算法采用的是一维数组,皇后个数即数组长度,数组值即对应行皇后所在的列。

按照每行至上而下,每一行从第一列起尝试放置皇后,每次仅需判断对于已经放置的皇后是否产生冲突。如果某个位置可以放置,则放置皇后(数组赋值),进入下一行判断;如果此行尝试到最后一列都没有可以放置的位置,则回溯到上一行,将上一行的皇后向后移动一列,如果皇后已经在最后一列,则继续向上回溯;终止条件即第一行皇后在最后一列,且就要移出界。


代码如下:

"""
    Python版回溯法求解N皇后问题。
    主程序的循环逻辑判断部分还有很大优化必要。
"""


def suit(x, y):  # 判断第x行、第y列能否放皇后
    if(x == 0):  # 第一行一定可以
        return True
    i = 1
    while(x - i >= 0):  # 循环测试前x行
        if(a[x - i] == y or a[x - i] - y == i or a[x - i] - y == -i):
            return False
        i += 1
    return True


def start():  # 主程序
    count = 0  # 计数解的个数
    global a  # 便于函数访问
    n = int(input("皇后数:"))
    print_map = input("需要打印每个布局吗?(Y/N):")
    a = [0 for i in range(n)]  # 采用一维数组,数组值即此行皇后位置
    i = 0
    while(i < n):  # 以行为大循环,回溯的关键
        j = a[i]  # 回溯时不从第一列开始
        while(j < n):  # 主要的小循环
            if(suit(i, j)):
                a[i] = j
                i += 1
                break
            j += 1
        if(j == n):  # 如果此列不能放置皇后,回溯
            a[i] = 0
            i -= 1
            if(a[i] == n - 1):  # 上一行皇后放在最后一列则不能直接往后移动一列,需要再次回溯
                if(i == 0):  # 回溯到第一列也不存在,则没有更多解
                    break
                else:  # 再次回溯
                    a[i] = 0
                    i -= 1
                    a[i] += 1
            else:  # 上一行皇后向后移动一列
                a[i] += 1
        if(i == n):  # 最后一行找到放置皇后位置,则为一种解
            count += 1
            if(print_map == 'Y'):
                print('第', count, '种解:')
                print_m(n)
            i -= 1  # 继续寻找下一个解
            if(a[i] == n - 1):  # 上一行皇后放在最后一列则不能直接往后移动一列,需要再次回溯
                a[i] = 0
                i -= 1
                a[i] += 1
            else:
                a[i] += 1
    print(n, '皇后问题,共', count, '种解')


def print_m(n):  # 打印出放置皇后的布局
    for i in range(n):
        j = 0
        while(j < a[i]):
            print('O', end=' ')
            j += 1
        print('X', end=' ')
        j += 1
        while(j < n):
            print('O', end=' ')
            j += 1
        print()
    print('------------------------------')

if __name__ == '__main__':
    while(1):
        start()

运行效果:

皇后数:4
需要打印每个布局吗?(Y/N):Y
第 1 种解:
O X O O 
O O O X 
X O O O 
O O X O 
------------------------------
第 2 种解:
O O X O 
X O O O 
O O O X 
O X O O 
------------------------------
4 皇后问题,共 2 种解
皇后数:8
需要打印每个布局吗?(Y/N):N
8 皇后问题,共 92 种解
皇后数:12
需要打印每个布局吗?(Y/N):N
12 皇后问题,共 14200 种解