8皇后排列问题

香川群子

8种旋转转置变化改为一起处理。速度快一倍。


另外，点选含"，"号的合并字符串、即可在B2单元格区域中填写该对应组合的排列图形。
以及、点选含"_"号的合并字符串序号时，则在B2单元格区域中不清空叠加该单元格左列合并字符串对应组合的排列图形。

香川群子

安排矩阵的不重复排列。

joforn

香川群子 发表于 2014-9-24 00:09
安排矩阵的不重复排列。

N值   结果
1　　1
2      0
3      0
4      2
5      10
6      4
7      40
8      92
9      352
10    724
11    2680
12    14200
13    73712
14    365596
15    2279184
16　14772512　　

香川群子

joforn 发表于 2014-9-27 13:21
N值   结果
1　　1
2      0

我现在的代码是去掉各种镜像重复的结果……当然比你的数字要少很多。

请仔细看完我帖子中的各个楼层内容。呵呵。


8皇后、代码遍历可得到92种，但排除镜像重复后，只有12种。

joforn

香川群子 发表于 2014-9-27 14:04
我现在的代码是去掉各种镜像重复的结果……当然比你的数字要少很多。

请仔细看完我帖子中的各个楼层内 ...

没看代码，因为当N=8时程序一运行就崩溃了。
好像是报1004号错误。

香川群子

joforn 发表于 2014-9-27 14:10
没看代码，因为当N=8时程序一运行就崩溃了。
好像是报1004号错误。

你的意思：我某一楼层的代码开始运行以后就报错了。

几楼的代码或附件？

joforn

香川群子 发表于 2014-9-27 14:37
你的意思：我某一楼层的代码开始运行以后就报错了。

几楼的代码或附件？

我只下载了最后一次的附件。

香川群子

joforn 发表于 2014-9-27 14:38
我只下载了最后一次的附件。

呵呵，恭喜你中奖了！

最后的42楼附件，是我自己存放的，别人的问题的半成品。

……现在已经删除了。呵呵。


如有兴趣，可下载41楼附件。这个才是本帖的最后答案。呵呵。

lee1892

香川群子 发表于 2014-8-22 11:41
第1行只检查1半、这个是正确的。

但是后面行的禁忌没有道理。除非是连续检查每一行的合并位置是否正确 ...

我说的禁忌搜索不考虑镜像重复的问题，大概是这样子的：

1. Option Base 1
   
2. Private Const N_NUM% = 8
   
3. Private Type QUEEN
   
4.     Selected As Integer
   
5.     Available As New Collection
   
6.     Disabled As New Collection
   
7. End Type
   
8. Private aQues() As QUEEN
   
9. Private aRes$(), nCnt&
   
10. Sub EightQueens()
    
11.     Dim i%, j%, sRep$, k%, t#
    
12.     t = Timer
    
13.     ReDim aQues(N_NUM)
    
14.     For i = 1 To N_NUM
    
15.         With aQues(i)
    
16.             For j = 1 To N_NUM
    
17.                 .Available.Add j, CStr(j)
    
18.             Next
    
19.         End With
    
20.     Next
    
21.     ReDim aRes(1, 100)
    
22.     nCnt = 0
    
23.     FindNext 1
    
24.     For i = 1 To N_NUM
    
25.         With aQues(i)
    
26.             Set .Available = Nothing
    
27.             Set .Disabled = Nothing
    
28.         End With
    
29.     Next
    
30.     Debug.Print Format(Timer - t, "0.0000") & "s " & nCnt
    
31.     Erase aQues
    
32.     Erase aRes
    
33. End Sub
    
34. 
    
35. Sub FindNext(ByVal nRow%)
    
36.     Dim i%, j%, nCol, sRep$
    
37.     On Error Resume Next
    
38.     With aQues(nRow)
    
39.         For Each nCol In .Available
    
40.             .Selected = nCol
    
41.             'sRep = "Row " & nRow & " Select " & nCol & " Removed:"
    
42.             For i = nRow + 1 To N_NUM
    
43.                 aQues(i).Available.Remove CStr(nCol)
    
44.                 If Err = 0 Then
    
45.                     .Disabled.Add (i - 1) * N_NUM + nCol
    
46.                     'sRep = sRep & "(" & i & "," & nCol & ")"
    
47.                 Else
    
48.                     Err.Clear
    
49.                 End If
    
50.             Next
    
51.             For j = nCol - 1 To 1 Step -1
    
52.                 aQues(nRow + nCol - j).Available.Remove CStr(j)
    
53.                 If Err = 0 Then
    
54.                     .Disabled.Add (nRow + nCol - j - 1) * N_NUM + j
    
55.                     'sRep = sRep & "(" & nRow + nCol - j & "," & j & ")"
    
56.                 Else
    
57.                     Err.Clear
    
58.                 End If
    
59.             Next
    
60.             For j = nCol + 1 To N_NUM
    
61.                 aQues(nRow + j - nCol).Available.Remove CStr(j)
    
62.                 If Err = 0 Then
    
63.                     .Disabled.Add (nRow + j - nCol - 1) * N_NUM + j
    
64.                     'sRep = sRep & "(" & nRow + j - nCol & "," & j & ")"
    
65.                 Else
    
66.                     Err.Clear
    
67.                 End If
    
68.             Next
    
69.             'Debug.Print sRep
    
70.             If nRow = N_NUM Then
    
71.                 nCnt = nCnt + 1
    
72.                 If nCnt > UBound(aRes, 2) Then
    
73.                     ReDim Preserve aRes(1, UBound(aRes, 2) + 100)
    
74.                 End If
    
75.                 For i = 1 To N_NUM
    
76.                     aRes(1, nCnt) = aRes(1, nCnt) & aQues(i).Selected & ","
    
77.                 Next
    
78.                 aRes(1, nCnt) = Left(aRes(1, nCnt), Len(aRes(1, nCnt)) - 1)
    
79.             Else
    
80.                 FindNext nRow + 1
    
81.             End If
    
82.             'sRep = "Row " & nRow & " UnSel " & .Selected & " Added Back:"
    
83.             For i = 1 To .Disabled.Count
    
84.                 nCol = (.Disabled(1) - 1) Mod N_NUM + 1
    
85.                 aQues((.Disabled(1) - 1) \ N_NUM + 1).Available.Add nCol, CStr(nCol)
    
86.                 'sRep = sRep & "(" & (.Disabled(1) - 1) \ 8 + 1 & "," & nCol & ")"
    
87.                 .Disabled.Remove 1
    
88.             Next
    
89.             'Debug.Print sRep
    
90.             .Selected = 0
    
91.         Next
    
92.     End With
    
93. End Sub

复制代码

其实是一个树的深度优先的遍历搜索，在每次到达新节点时，需要清理其后节点的可能性，返回时则把原先去掉的可能性加回来。

这段代码速度并不快，但算法是对的，可能用字典取代集合会好些。另外每去掉一个可能性时，可以检查节点的剩余可能，提前返回。

aoe1981

香川群子 发表于 2014-8-21 16:37
关于二维数组矩阵的旋转、转置，一共有8种。

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

群子老师指点：
http://club.excelhome.net/thread-1155867-1-1.html