n皇后编程问题

n皇后编程问题 是一个经典问题。在2018年，北京航空航天大学计算机学院的博士招聘上，出现了这个问题作为上机题目。以下是几种实现方法：

import time
import itertools

Num =  8
# Num = 12   # 8

def f1():
    # f1()函数实现
    ...

def f2():
    # f2()函数实现
    ...

def f3():
    # f3()函数实现
    ...

# 运行时间测试
...

上面的实现中，当n=8时，f1()函数实现、f2()函数实现、f3()函数实现的运行时间如下（单位为秒）：

92
11.19756269454956
92
0.005673408508300781
92
0.019522428512573242

可以看到f1()函数的实现是f2实现的2000倍的用时，因此在下面的n=12时我们只给出f2()和f3()函数实现下的用时：

14200
4.591862201690674
14200
295.7449884414673

可以看到，f3()的实现下用时是f2()实现下的60倍。

总结：

f2()方法实现是运行时间最短的方法。

f3()方法是f2()用时的60倍。

f1()方法是f2()用时的2000倍。

不过在n=8时，也就是8皇后问题下，f2()和f3()的用时都是符合一般要求的（1秒以内或5秒以内）。

由于f2()中使用了yield，这一点并不通用，于是将其改为return，并加入sss=[ ]作为状态保存，具体代码如下：

import time
import itertools
 
Num =  8

 
def f2():
    # 修改后的f2()函数实现
    ...

不过考虑到即使把f2()中的yield改为return也是需要使用递归算法的，而递归算法是可以使用循环算法来替代的，于是使用循环算法修改f2()中的递归，得到如下代码：

import time
 
 
def f2():
    # 使用循环算法修改f2()中的递归
    ...

个人github博客地址：
https://devilmaycry812839668.github.io/