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
1700507474
计算结果如表11-4所示。可以看出，平均单次试探时间下降为前一次的0.18倍左右。
1700507475
1700507476
表11-4 N皇后问题求解时间（N=15）
1700507477
1700507478
1700507479