8皇后排列问题

香川群子

国际象棋 棋盘为 8x8=64个方格子
假设在棋盘中放入 8个皇后，要求8个皇后相互之间互不干涉、互不攻击的放置方法。

【注： 皇后的攻击能力为纵、横、斜 即米字格 的8个方向】

通俗点说，也就是每个皇后的8个方向直线内，都不能有其它皇后、相互不干涉。

附件是8皇后问题的一个解，以及其中5号皇后的攻击范围。

请有兴趣的朋友编程计算所有解。（允许包含部分对称，但1号皇后规定只出现在第1行中)各种对称情况有：45度对称、左右对称、上下对称、旋转对称

liyh67

香川群子

1        2        3        4        5        6        7        8
9        10        11        12        13        14        15        16
17        18        19        20        21        22        23        24
25        26        27        28        29        30        31        32
33        34        35        36        37        38        39        40
41        42        43        44        45        46        47        48
49        50        51        52        53        54        55        56
57        58        59        60        61        62        63        64

按上表对棋盘格子编号以后，得到的解如下：


1,13,24,30,35,47,50,60
1,14,24,27,39,44,50,61
1,15,20,30,40,42,53,59
1,15,21,32,34,44,54,59
2,12,22,32,35,41,55,61
2,13,23,25,35,48,54,60
2,13,23,28,33,48,54,59
2,14,17,31,36,48,51,61
2,14,24,27,33,44,55,61
2,15,19,30,40,45,49,60
2,15,21,32,33,44,54,59
2,16,22,25,35,45,55,60
3,9,23,29,40,42,52,62
3,13,18,32,33,47,52,62
3,13,18,32,38,44,55,57
3,13,23,25,36,42,56,62
3,13,24,28,33,47,50,62
3,14,18,29,40,41,55,60
3,14,18,31,33,44,56,61
3,14,18,31,37,41,56,60
3,14,20,25,40,45,55,58
3,14,20,26,40,45,55,57
3,14,24,25,36,47,53,58
3,14,24,25,37,47,50,60
3,14,24,26,36,41,55,61
3,15,18,32,37,41,52,62
3,15,18,32,38,44,49,61
3,16,20,31,33,46,50,61
4,9,21,32,34,47,51,62
4,9,21,32,38,43,55,58
4,10,21,32,38,41,51,63
4,10,23,27,38,48,49,61
4,10,23,27,38,48,53,57
4,10,23,29,33,48,54,59
4,10,24,29,39,41,51,62
4,10,24,30,33,43,53,63
4,14,17,29,34,48,51,63
4,14,24,26,39,41,51,61
4,14,24,27,33,47,53,58
4,15,17,32,37,42,54,59
4,15,19,32,34,45,49,62
4,15,21,26,38,41,51,64
4,15,21,27,33,46,56,58
4,16,17,27,38,42,55,61
4,16,17,29,39,42,54,59
4,16,21,27,33,47,50,62
5,9,20,30,40,42,55,59
5,9,24,28,34,47,51,62
5,9,24,30,35,47,50,60
5,10,20,30,40,43,49,63
5,10,20,31,35,48,54,57
5,10,22,25,39,44,56,59
5,10,24,25,36,47,51,62
5,11,17,30,40,42,52,63
5,11,17,31,34,48,54,60
5,11,24,28,39,41,54,58
5,15,17,27,40,46,52,58
5,15,17,28,34,48,54,59
5,15,18,28,40,41,51,62
5,15,18,30,35,41,52,64
5,15,18,30,35,41,56,60
5,15,20,25,35,48,54,58
5,16,20,25,35,46,50,63
5,16,20,25,39,42,54,59
6,9,21,26,40,43,55,60
6,10,23,25,35,45,56,60
6,10,23,25,36,48,53,59
6,11,17,31,37,48,50,60
6,11,17,32,36,42,55,61
6,11,17,32,37,42,52,63
6,11,21,31,33,44,50,64
6,11,21,32,33,44,50,63
6,11,23,26,36,48,49,61
6,11,23,26,40,45,49,60
6,11,23,28,33,48,50,61
6,12,17,29,40,42,55,59
6,12,18,32,37,47,49,59
6,12,23,25,35,45,50,64
6,12,23,25,40,42,53,59
6,16,18,28,33,47,53,59
7,9,19,32,38,44,50,61
7,10,20,25,40,45,51,62
7,10,22,27,33,44,56,61
7,11,17,30,40,45,50,60
7,11,24,26,37,41,54,60
7,12,18,29,40,41,51,62
7,12,18,32,38,41,51,61
7,13,19,25,38,48,50,60
8,10,20,25,39,45,51,62
8,10,21,27,33,47,52,62
8,11,17,30,34,45,55,60
8,12,17,27,38,42,55,61

aoe1981

首先，我觉得这个问题不难，写蠢代码很容易，按部就班的解决……
然后，对于我而言，有一道坎，有点迈不过去，就是代码的优化……
注意到：=COMBIN(64,8)＝4426165368
显然，这个结果很大，用蠢代码不知要做到何年何月……

aoe1981

这8个皇后显然不同行、不同列，如何根据这一点缩小组合的判断范围，很关键……

aoe1981

关于斜线的判断：x1-x2=yx-y2，如果成立就要排除……基本道理是这样的……只是组合数太大了，如何优化很头疼……我的蠢代码运行的我……焦灼啊……

aoe1981

=FACT(8)＝40320
这绝对是个突破口，先想想……不想得到提示……

aoe1981

就是=8^8＝16777216
也比=COMBIN(64,8)＝4426165368好得多！

aoe1981

　　是这个结果吧：
　　

aoe1981

　　修正下6楼的结果，应该是：abs(x1-x2)=abs(yx-y2)