话说昨儿个写了个DLX，今天准备用DLX写个N皇后问题

一开始在POJ找到个300皇后问题，直接就写了，然后悲剧了……无限TLE

后来发现这道题目是要用构造法的……

写了的程序不能浪费，在SPOJ上面找到一个50皇后问题，稍微小改了一下就提交了

然后TLE了……悲剧的……话说本地都不会TLE……

于是百度……找到一个代码，那个代码很顺利的过了……

百思不得其解，除了代码风格，感觉两个人的代码没什么差别

一开始我以为是由于回溯的时候恢复链表的顺序导致出现错误，但是仔细一想发现即使按照顺序恢复也是能够正确还原的

为了验证，特意改了个程序，最后发现没有问题……

但是实在没办法，就把我的N皇后还是改成first do ，last undo的结构，再次提交，再次TLE……

悲剧的啊……

仔细看了一下百度到的代码，发现百度到那个代码输出的结果字典序明显偏大，而我输出来的头几位尤其是第一位几乎都是1，难道问题在这里？仔细看了一下代码，发现那个代码在sum相同时优先取后面的点，而我的是优先取前面的点，灵机一动，把我的<改成了<=，发现速度居然飙升！提交，直接居然就过了……

回过头，把最初那个TLE的程序拿出来，把<改成<=，还是AC，而且速度比改过这个还快！

于是很奇怪为什么会有这种情况……

决定测试一下

设置了一个全局变量g_op，记录cover的次数来估计搜索树的大小。

在题目的要求下，即只输出一个解的条件下，对于，测试了下面一串N的cover次数

10 11 12 13 14 15 25 31 32 33 34 35 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56
，在<的情况下，程序运行结果是
110 245 290 422 238 125 196 2250 328 267 355 657 441 652 5261 570 632 613 274 10 783 633 234 3276 147849 7378 97766 955
而<=的情况下，结果是
110 191 325 429 379 125 734 556 3672 670 165 366 325 2309 651 296 634 887 11073 629 982 946 930 9164 1179 1342 371
并且跟百度到的程序一模一样！
可以发现，其实两种情况下大部分的cover次数都比较接近，但是在<=的时候最大的只是1W多，总体相对于<的时候平缓许多，在<的时候出现了10W多的情况，估计就是这几个情况导致了TLE
接着我在想到底是为什么呢？
突然想到测试算出所有解的情况
于是小改一下程序，分别测试N为下列值时，算出所有解需要的次数
4 5 6 7 8 9 10 11 <的时候，结果为
59 191 403 1383 4447 17376 61048 258523
<=的时候，结果为
59 191 403 1383 4447 17376 61048 258523
两者一模一样！
突然又想到如果不管大于小于的情况，直接取最前面一个跟最后面一个会是怎样的情况，说干就干，再改一下程序，还是测试求出所有解的情况
还是那些n，取最前面一个的时候结果为
59 199 559 2011 7489 30637 129379 606625
取最后面一个，结果为
59 199 559 2011 7489 30637 129379 606625
居然一模一样！
现在凭我的感觉分析一下
取所有解的时候出现了两次一模一样，应该是由于棋盘的对称性
但是直接取第一个跟取sum最小相比还是慢很多，说明DLX的剪枝还是比较暴力的，基本上剪掉了2/3
最搞不懂的就是第一组比较数据了
为什么优先取后面的会快那么多呢
如果用对称性来说明的话后面的点跟前面的点应该是完全对称的啊
我感觉我想不到了……
求大牛解释……