1700507410
1700507411
这种经典算法与数据结构的例子网上有很多，其中queens(8)这一部分是可以修改的，“8”代表的是8×8的棋盘，放置8个皇后。如果改成queens(16)，就是在一个“改造”过的16×16的棋盘上求解一个十六皇后问题了。
1700507412
1700507413
为了展示这种穷举法在八皇后问题扩展上的“缺陷”，需要对刚刚的程序做一下简单的改造，把它改造成一个能够处理“N皇后问题”的程序。
1700507414
1700507415
程序的前部改为：
1700507416
1700507417
import sysnumber=int(sys.argv[1])
1700507418
1700507419
程序的后部改为：
1700507420
1700507421
if __name__==“__main__”: i=0 for solution in queens(number): i+=1 print ‘total test:’ + str(pow(number,number))+ ‘; total solution:’ + str(i)+ ‘\n’
1700507422
1700507423
这样就可以打印出所有的尝试次数和有效解的个数，并且，只在终端输出个数，而不输出具体解出的盘面。
1700507424
1700507425
接下来，就可以用命令行从1开始逐步尝试。
1700507426
1700507427
[root@ann science]# time python eight.py 1total test:1; total solution:1 real 0m0.011suser 0m0.003ssys 0m0.008s[root@ann science]# time python eight.py 2total test:4; total solution:0 real 0m0.010suser 0m0.006ssys 0m0.004s[root@ann science]# time python eight.py 3 total test:27; total solution:0real 0m0.011suser 0m0.008ssys 0m0.005s[root@ann science]# time python eight.py 4total test:256; total solution:2 real 0m0.009suser 0m0.003ssys 0m0.006s[root@ann science]# time python eight.py 5total test:3125; total solution:10 real 0m0.031suser 0m0.017ssys 0m0.014s[root@ann science]# time python eight.py 6total test:46656; total solution:4 real 0m0.011suser 0m0.007ssys 0m0.004s[root@ann science]# time python eight.py 7total test:823543; total solution:40 real 0m0.053suser 0m0.018ssys 0m0.035s[root@ann science]# time python eight.py 8total test:16777216; total solution:92 real 0m0.030suser 0m0.023ssys 0m0.007s[root@ann science]# time python eight.py 9total test:387420489; total solution:352 real 0m0.081suser 0m0.077ssys 0m0.004s[root@ann science]# time python eight.py 10total test:10000000000; total solution:724 real 0m0.320suser 0m0.316ssys 0m0.004s[root@ann science]# time python eight.py 11total test:285311670611; total solution:2680 real 0m1.723suser 0m1.717ssys 0m0.006s[root@ann science]# time python eight.py 12total test:8916100448256; total solution:14200 real 0m10.202suser 0m10.185ssys 0m0.016s[root@ann science]# time python eight.py 13total test:302875106592253; total solution:73712 real 1m3.286suser 1m3.273ssys 0m0.009s[root@ann science]# time python eight.py 14total test:11112006825558016; total solution:365596 real 7m18.573suser 7m18.562ssys 0m0.017s
1700507428
1700507429
再往下测试的话时间就非常长了。在这里我只测试到14个皇后的情况（如表11-2和图11-5所示）。这种单线程的计算效率几乎完全依赖单CPU核心的主频。
1700507430
1700507431
表11-2 N皇后求解时间表
1700507432
1700507433
盘面宽度 穷举次数 解个数 时间（秒） 1 1 1 003 2 4 0 006 3 27 0 008 4 256 0 003 5 3125 10 017 6 46656 4 007 7 823543 40 0.018 8 16777216 92 0.023 9 387420489 352 0.077 10 10000000000 724 0.316 11 285311670611 2680 1.717 12 8916100448256 14200 10.185 13 302875106592253 73712 63.273 14 11112006825558016 365596 438.562 这种试探次数的增加，在N皇后问题场景中随着盘面宽度n的增加而迅速增加（如图11-5所示）。显然，这个时间复杂度是O(nn)，几乎是在二维空间解中效率最差的一种情况了。
1700507434
1700507435
1700507436
1700507437
1700507438
图11-5 盘面宽度-穷举次数
1700507439
1700507440
测试的时间目测也是按照O(nn)来增加的（如图11-6所示）。为了验证我们的观点，下面用“叠加法”来估算单次试探所需要的时间。由于单次试探的时间太短，所以任何一次测量都会产生非常大的误差。我们只看盘面宽度为8以前的各次测试所花费的时间就可以了。
1700507441
1700507442
1700507443
1700507444
1700507445
图11-6 盘面宽度-时间（秒）
1700507446
1700507447
这两组数据几乎看不出任何联系，波动太大，所以不建议参与统计（如图11-7所示）。
1700507448
1700507449
1700507450
1700507451
1700507452
图11-7 穷举次数与花费的时间（秒）
1700507453
1700507454
盘面宽度和单次试探时间的关系像是一条渐近线，随着盘面宽度的增加，单次试探时间无限趋近于0（如表11-3和图11-8所示）。实际上，这个试探时间无论如何是不可能为0的。
1700507455
1700507456
1700507457
1700507458
1700507459
图11-8 盘面宽度-单次试探时间