8皇后排列问题

aoe1981

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

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

三种基本的变换：平移、旋转、对称。
所谓“12个基础解”是否可以理解为：不能通过旋转与对称（应该就是帖中谈到的镜像吧）彼此得到的结果吧……
（我觉得，本题中自然是不能用到平移变换的……）

aoe1981

　　现在传一个所谓“aoe1981正式版”，主要做了两方面的修改：
　　1.分为“快速筛选”和“分步筛选”两部分，前者一次性快速生成结果，结果统一为香川提出的序列结果；
　　2.解决了分步直观演示时暂停及中断暂停的问题，可以较好的动态直观演示棋盘的情况。
　　附件如下：
　　 8皇后排列问题（aoe1981正式版）.rar (18.68 KB, 下载次数: 45)

2014-8-18 14:02 上传

点击文件名下载附件

香川群子

研究了一下对称性问题……

对于每一个基本图来说，包括自己共有8种对称类型。
镜像4种：135度轴镜像(数组行列转置)、45度轴镜像、左右镜像(90度轴)、上下镜像(180度轴)
旋转4种： 0度旋转(自身)、90度旋转(左右镜像后行列转置)、180度旋转(上下镜像后左右镜像)、270度旋转(上下镜像后行列转置)


…………
排除各种重复以后，我的代码计算8皇后问题，仅需调用递归481次、检查斜线1410次。耗时0.00秒。呵呵。

香川群子

其中检查米字格斜线的函数过程、非常精简、高效：

1. Function Chk(x&, y&) As Boolean '仅需检查米字格中4条斜线部分 纵横可保证不需检查
   
2.     Dim i&
   
3.     For i = 1 To IIf(x < y, x, y)
   
4.         If b(x - i, y - i) Then Exit Function
   
5.     Next
   
6.     For i = 1 To IIf(n - x < y, n - x, y)
   
7.         If b(x + i, y - i) Then Exit Function
   
8.     Next
   
9.     For i = 1 To IIf(n - x < n - y, n - x, n - y)
   
10.         If b(x + i, y + i) Then Exit Function
    
11.     Next
    
12.     For i = 1 To IIf(x < n - y, x, n - y)
    
13.         If b(x - i, y + i) Then Exit Function
    
14.     Next
    
15.     Chk = True
    
16. End Function

复制代码

a20089668

群子，我在获取网页上的内容遇到瓶颈，能帮我看看怎么解决吗？
http://club.excelhome.net/thread-1146364-1-1.html这个是发帖的地址。

aoe1981

香川群子 发表于 2014-8-18 23:42
研究了一下对称性问题……

对于每一个基本图来说，包括自己共有8种对称类型。

我印象中，哪本数学书中曾囫囵吞枣的接触过，平移、旋转、对称变换的矩阵的……当初的感觉是二维的平面坐标系是最简单的一个情况……即使如此，也有点淡忘了，我想得花好些时间补下这方面的课了……发这些的目的是，清静的时间往往很是宝贵的，不知这个方向可有错误？

香川群子

关于二维数组矩阵的旋转、转置，一共有8种。

4个顶点从左上开始，按顺时针合并、则起始基本型记录为：abcd

统一按逆时针旋转、每次90度，则有4种变化：
abcd → bcda → cdab → dabc → abcd（旋转4次以后回到基本型）
0度 → 90度 → 180度 → 270度 →  360度(=0度)

因此旋以后产生4种变化型。

…………

然后，每一种变化，再进行【行列转置】（相当于以135度角的对角线为轴、进行镜像转换）

这样也有4种新类型产生：

A类：         B类：
90度旋转    行列转置
  abcd         adcb
  bcda         badc
  cdab         cbad
  dabc         dcba


几何结果如下图：

香川群子

最后没办法，还是只能用字典检查重复来做的。

lee1892

香川群子 发表于 2014-8-18 23:44
其中检查米字格斜线的函数过程、非常精简、高效：

你不是用的禁忌搜索的办法？

我想象中是按行向下搜索，每选定一个就把后面可能放的格子给去掉，深度优先，回朔的时候再把每步去掉的加回来。

另外，第一行搜索一半就行吧，应该是对称的。

香川群子

lee1892 发表于 2014-8-21 23:32
你不是用的禁忌搜索的办法？

我想象中是按行向下搜索，每选定一个就把后面可能放的格子给去掉，深度优 ...

第1行只检查1半、这个是正确的。

但是后面行的禁忌没有道理。除非是连续检查每一行的合并位置是否正确……这和字典检查最终结果是差不多了。
附图为第1个有效解，进行8种类型的旋转、转置后的重叠部分……没办法作为禁忌参考使用。