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 盘面宽度-单次试探时间
1700507460
1700507461
表11-3 N皇后求解盘面宽度为N与N-1时的单次试探时间比
1700507462
1700507463
盘面宽 b单次试探时间（秒） 盘面宽度为N与N-1时的单次试探时间比 9 1.9875E-10 0.144977364 10 3.16E-11 0.158993344 11 6.01798E-12 0.190442413 12 1.14232E-12 0.189817095 13 2.08908E-13 0.182881075 14 3.94674E-14 0.188922486 这就表明，N每增加1，平均每次试探的时间就会变为之前的0.18倍左右（如图11-9所示）。这样我们可以猜测：当N=15时，单次的平均时间可能还会继续以这个比例下降。
1700507464
1700507465
1700507466
1700507467
1700507468
图11-9 盘面宽度为N与N – 1时的单次试探时间比
1700507469
1700507470
N=15的情况如下。
1700507471
1700507472
[root@ann science]# time python eight.py 15total test:437893890380859375; total solution:2279184 real 52m46.628suser 52m46.265ssys 0m0.094s
1700507473