8皇后排列问题

aoe1981

直到现在不明白，您这句：
“允许包含45度对称、但左右对称、上下对称旋转对称就不要了”
到底具指什么？

香川群子

aoe1981 发表于 2014-8-17 22:50
直到现在不明白，您这句：
“允许包含45度对称、但左右对称、上下对称旋转对称就不要了”
到底具指什么？

这一句就忽略吧。

我只是提醒，遍历计算设置不当，可能会得到大量重复解。

香川群子

aoe1981 发表于 2014-8-17 22:44
　　最后补充一点：
　　关于我的结果的表示：
　　我没有采用香川的自然数序号的办法：1～64

8X8的行列坐标，很容易转化为一维坐标的，努力一下吧。

…………
虽然二维行列坐标很直观，但如果让计算机来记录的话，选择一维坐标记录是最好的。
你需要有这个概念。

香川群子

关于遍历检查次数，
首先所有皇后不能同行。
那么如果固定1号皇后在第1行、2号皇后在第2行、……
所有列组合算进去，是=8^8=16777216次。

但考虑到所有不能皇后不仅不能同行、也不能同列，
所以只需考虑全排列组合 =Fact(8)=40320次。

实际加上剪枝，需要检查的次数就大为减少了。
可以在0.01秒以内完成所有计算。
采用递归算法，实际运算次数如下：

aoe1981

香川群子 发表于 2014-8-18 08:52
8X8的行列坐标，很容易转化为一维坐标的，努力一下吧。

…………

主要是我的核心判断部分是依据直角坐标进行的，选择一维是不是也要在这部分进行修改？还是，只是把结果最后转换一下？

香川群子

aoe1981 发表于 2014-8-18 08:58
主要是我的核心判断部分是依据直角坐标进行的，选择一维是不是也要在这部分进行修改？还是，只是把结果最 ...

结果转换即可：

假定结果存放在二维数组b&(7, 7)中，那么代码如下：

1. 
   
2. For x = 0 To 7
   
3.     For y = 0 To 7
   
4.         t = t + 1
   
5.         If b(x, y) Then s = s & "," & t
   
6.     Next
   
7. Next
   
8. c(k) = Mid(s, 2)
   

复制代码

实际转换只需92次，对速度毫无影响。

lee1892

香川群子 发表于 2014-8-17 17:09
1        2        3        4        5        6        7        8
9        10        11        12        13        14        15        16
17        18        19        20        21        22        23        24

8x8有12个基础解，转换方式为：转90度、180度、270度，及上述4个的镜像

楼主代码是找出基础解的吗？

可否扩展到n皇后在nxn的棋盘上吗？n>3

香川群子

lee1892 发表于 2014-8-18 09:44
8x8有12个基础解，转换方式为：转90度、180度、270度，及上述4个的镜像

楼主代码是找出基础解的吗？

左右镜像对称，可以通过约束第1个皇后的检查位置减半来去除。

但其它各种旋转方式，难以事先简单排除。
当然，可以通过相应的转换、转置函数对结果进行字典比较排除重复。

…………
本题仅对初学者做思考练习用，所以暂不要求排除各种旋转和镜像对称。

呵呵。

香川群子

lee1892 发表于 2014-8-18 09:44
8x8有12个基础解，转换方式为：转90度、180度、270度，及上述4个的镜像

楼主代码是找出基础解的吗？

n=1 OK
n=2、n=3 时无解

n=4 有唯一解

…………
以后貌似都有解。

香川群子

本题编程呢有2个关键之处：

1、如何遍历，保证不遗漏但又能减少循环次数

2、如何高效检查本次循环得到的皇后位置是否和之前的有冲突？

理论上需检查纵、横、斜的8个方向，
而实际上只需检查斜线方向……


而斜线的检查，如何高效进行？需要运用一些最基本的直角坐标知识。