【求助】n皇后问题,在网上看到的解法,求解
mathematica吧
全部回复
仅看楼主
level 2
Thomsoni 楼主
这是在微信公众号Wolfram上看到的一个n皇后解法,网址:https://mp.weixin.qq.com/s/yH2UpAWKIlywIhhw7tNzbQ
里面给出了看起来很厉害的mma使用方法,我不大懂啥意思,
比如,f:_Or:>Sort[f],还有/.{iter__}:>以后的部分。
我自己写的运行速度比它慢了不少,真的很想弄懂这个n皇后的代码。
Clear["Global`*"]
n=15;
cf=With[{X=Symbol["x"<>ToString[#]]&},
Table[{X[j+1],
If[Or@@Table[X[j]==X[j-i]||Abs[X[j]-X[j-i]]==i,{i,j-1}]/.
f:_Or:>Sort[f],
0,Evaluate@If[j<n,n,1]]},{j,n}
]
]/.{iter__}:>
Compile[{{x1,_Integer}},
Module[{cnt=0},Do[cnt++,iter];cnt],
CompilationTarget->"C",RuntimeOptions->"Speed",RuntimeAttributes->{Listable}
]
Total@cf@Range[n]//AbsoluteTiming
2Total@Most[#]+If[OddQ[n],Last[#],0]&@cf@Range[n/2+1]//AbsoluteTiming
最后俩行是测试两种不同算法的运算时间
2020年03月05日 14点03分 1
吧务
level 10
用With把所有X[i]换成x1,x2等符号是因为Do这些迭代函数一般只支持符号迭代变量,属于元编程经典操作。而且这对Compile来说也很重要。除去这些干扰实现的东西,其实整个程序只有两个Table、一个If和一个Do。
双层Table构造迭代器。外层迭代变量j代表行数+1,取2~n+1,这个+1只是为了方便,你当然完全可以改成1~n。内层迭代变量i代表要检验是否与第j行冲突的行的序号),取1~j-1。
行列指标可以确定一个逻辑函数X[j] == X[j-i] || Abs[X[j] - X[j-i]] == i,Or的两端分别判断是否有列冲突或色冲突,若有任何冲突则返回True。
内层的Table用1~j-1行对第j行进行了检验,返回的是一个逻辑值的列表。现在应用一个Or上去,如果有任何一行与第j行冲突,就给出一个True,仅当完全没有冲突的时候给出False。
这时使用If对冲突的情况给出迭代范围0,对无冲突的情况给出n(除非是最后一个迭代器,这时给出1,因为这时只需要检验冲突而不需要为下一行作考虑了)。迭代范围n是遍历所有列的自然要求,而迭代范围0意味着这条分支不存在。
于是,外层Table为每个j都给出了一个形如{x2, If[...]}的迭代器,现在只需把这个Table的List这个Head去掉、拼接到Do里面去就能进行所有分支的迭代计算。他这里没有使用Sequence而是使用了更随意的ReplaceAll。
要收集坐标,可以使用Sow和Reap的组合。为了更高的效率可以使用功能基本相同的的Internal`Bag。
2020年03月06日 16点03分 2
万分感谢!!![真棒][真棒][真棒]仔细看了你的讲解,琢磨了好久,终于知道咋回事儿了[太开心][太开心][太开心]
2020年03月07日 01点03分
第一句不太对,参3楼。
2020年04月04日 04点04分
[真棒]
2020年05月02日 10点05分
吧务
level 15
“用With把所有X[i]换成x1,x2等符号是因为Do这些迭代函数一般只支持符号迭代变量……”这说法其实不太对,其实很多函数都支持非原子型变量,包括Do和Compile,故此代码可简化为
Clear["Global`*"]
n=5;cf=Table[{X[j+1],If[Or@@Table[X[j]==X[j-i]||Abs[X[j]-X[j-i]]==i,{i,j-1}]/.f:_Or:>Sort[f],0,Evaluate@If[jCompile[{{X[1],_Integer}},Module[{cnt=0},Do[cnt++,iter];cnt],RuntimeOptions->"Speed",RuntimeAttributes->{Listable}]
Total@cf@Range[n]//AbsoluteTiming
2Total@Most[
#]+If[OddQ[n],Last[#
],0]&@cf@Range[n/2+1]//AbsoluteTiming
注意我为了在WolframCloud上测试改小了n,也去掉了编译为C的选项。
关于Compile的这个特性,可参考SE帖子编号145991。
不过,据@无影东瓜 测试,使用上述方法写出的代码虽然可以完全编译,但执行速度却逊于顶楼方法,理由暂时搞不清楚……(我自己一直没逮到机会详细测……)
2020年04月04日 04点04分 3
在Block中使用非符号定义的话会报错,而Do号称通过Block进行局域化,所以我当时这么判断了。
2020年04月04日 09点04分
我分别测试了符号迭代器和非符号迭代器。迭代计算千万次平方,x[1]的迭代器的耗时是x1的4.5倍。
2020年04月06日 11点04分
至于为什么慢,我也测试了一下。赋下值比赋值差不多慢一倍,调用下值也比调用值慢一倍。迭代器每次都要重新赋值,算平方的也要调用,所以总共大概慢4倍。
2020年04月06日 12点04分
这似乎表明虽然Do是核函数,其中并没有额外的优化(如果有的话感觉会搞出问题),那么直接访问符号表的x1当然就要比多访问一层表达式的x[1]慢了。而且x[1]的赋值应该不只是多访问一层这么简单,OwnValues不支持模式匹配而TagSet这些就不一样了。如果调用时要进行模式匹配,显著慢于哈希表就不奇怪了。
2020年04月06日 12点04分
level 8
都是高手
进来观摩。。。
2020年04月07日 07点04分 4
1