×

工业设计互动平台

手机短信,快捷登录

微信登录,快人一步

QQ登录

只需一步,快速开始

大家来思考10-八皇后手工算法,抛砖引玉

发布于 2013-8-23 0 点赞 41 评论 9346 浏览

本帖最后由 wyx10022 于 2015-1-5 15:47 编辑

关于八皇后问题
未标题-1 拷贝.jpg
相关视频
http://www.xuexiniu.com/forum.php?mod=viewthread&tid=35933
算法不难,简单的算法重复7次而已
2.jpg
个人认为,最终的布点方式应为8的倍数,因为每种布局都可以进行四次镜像+三次旋转,再加自身,共8种可能,
当然没有全试出来只能是推测而已……
未标题-1 拷贝.jpg
手工拖动参数虽然稍微费点力气,不过比起没有电脑的时代,效率还是要高很多……
过程还是比较有趣的……
22.jpg
当然,算法还有其他多种,有的会比较费内存,但是不会费力……
如之后谈讨的八皇后排除算法:http://www.xuexiniu.com/thread-62921-1-1.html
希望涌现其他多种算法,网校GH高级班学员请积极参与思考……
源文件 八皇后0.rar (32.41 KB, 下载次数: 172)

本帖被以下淘专辑推荐:

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

精彩回复

文明上网理性发言、请文明用语

wyx10022 | 网校特聘讲师 | 发表于 2013-8-25 09:59:08
hippo100312 发表于 2013-8-24 23:57
手动算法求出所有解比较消耗时间,我用代码求8皇后问题92个解,9皇后问题352个解。
...

二位都是用的python吗? @hskcool
1 回复

举报

hskcool · 发表于 2013-8-25 10:23 点评

我用的是Python

hskcool · 发表于 2013-8-25 10:23 点评

我用的是Python

hippo100312 · 发表于 2013-8-25 10:11 点评

哦,我用的是C#

zucckai | 设计助理 | 发表于 2015-1-4 21:52:44
。。。。惊现我们老板的视频。。。
0 回复

举报

xiaoen | 实习生 | 发表于 2015-1-6 15:21:06
:dizzy:看不懂。
0 回复

举报

476589523 | 实习生 | 发表于 2013-8-24 10:19:47
抢沙发,其实我没看懂,不过感觉挺深奥!顶一个……
0 回复

举报

黑头发 · 发表于 2013-8-26 17:52 点评

哈哈,在这看见了····

高山 | 实习生 | 发表于 2013-8-24 15:59:06
算了10来种,就不敢再往下摆了,全乱套了[s:161]
0 回复

举报

wyx10022 · 发表于 2013-8-25 12:56 点评

这类回溯算法还是代码比较快,用GH手工也有点麻烦……

再见的寂寞 | 设计助理 | 发表于 2013-8-24 17:10:19
没看懂 貌似很厉害
0 回复

举报

jettyyy | 实习生 | 发表于 2013-8-24 18:21:13
有看沒有懂
0 回复

举报

hskcool | 设计师 | 发表于 2013-8-24 19:12:12
并不一定的8的倍数。有可能出现轴对称或者是中心对称图形。
0 回复

举报

hf0419001 · 发表于 2013-8-25 12:54 点评

是不可能会有自身轴对称的情况的吧,那样不是互相能攻击了吗?

wyx10022 · 发表于 2013-8-24 19:48 点评

轴对称,就是镜像,中心对称,就是旋转…… 原文的意思是一样的,可以再看看

wyx10022 | 网校特聘讲师 | 发表于 2013-8-24 19:48:43
本帖最后由 wyx10022 于 2013-8-24 20:03 编辑
hskcool 发表于 2013-8-24 19:12
并不一定的8的倍数。有可能出现轴对称或者是中心对称图形。

“个人认为,最终的布点方式应为8的倍数,因为每种布局都可以进行四次镜像+三次旋转,再加自身,共8种可能,
当然没有全试出来只能是推测而已……”

轴对称,就是镜像,有四种,中心对称,就是旋转,加上自身共四种……
原文的意思是一样的,可以再看看

不过据我推测,总的可能是96种,但是存在4种既是中心对称又是轴对称的情况,所以就变成92种了……
0 回复

举报

hskcool · 发表于 2013-8-24 21:00 点评

轴对称就说明镜像与自身相同,是同一种。那镜像就不能产生新的,只能算旋转产生4种。 中心对称就代表旋转镜像都是同一种。 所以说不一定是8的倍数种。

hskcool | 设计师 | 发表于 2013-8-24 21:00:10
本帖最后由 hskcool 于 2013-8-24 21:05 编辑
wyx10022 发表于 2013-8-24 19:48
“个人认为,最终的布点方式应为8的倍数,因为每种布局都可以进行四次镜像+三次旋转,再加自身,共8种可能 ...

轴对称就说明镜像与自身相同,是同一种。那镜像就不能产生新的,只能算旋转产生4种。
中心对称旋转镜像也可能不产生新的形式,至少转180°是产生不了新图形的而且90与-90度也是一样的图形。
所以说不一定是8的倍数种。
0 回复

举报

hskcool | 设计师 | 发表于 2013-8-24 22:26:38
360软件小助手截图20130824222533.jpg


0 回复

举报

hskcool | 设计师 | 发表于 2013-8-24 23:41:04
360软件小助手截图20130824234026.jpg
0 回复

举报

wyx10022 · 发表于 2013-8-25 09:43 点评

如果按你说的镜像和旋转都是一样的,那你的这92种里有大量重复的,可以仔细观察下……

hippo100312 | 设计助理 | 发表于 2013-8-24 23:57:54
本帖最后由 hippo100312 于 2013-8-26 13:50 编辑

手动算法求出所有解比较消耗时间,我用代码求8皇后问题92个解,9皇后问题352个解。

电池

电池
QQ截图20130826134529.png
QQ图片20130824235017.jpg
0 回复

举报

hf0419001 · 发表于 2013-8-25 12:52 点评

都是用代码啊!

wyx10022 · 发表于 2013-8-25 09:59 点评

二位都是用的python吗? @hskcool

wyx10022 · 发表于 2013-8-25 09:45 点评

不错,这类问题还是语言更快些……

参与人数 1经验 +6 大洋 +10 收起 理由
wyx10022 + 6 + 10 很给力!

查看全部评分

hskcool | 设计师 | 发表于 2013-8-25 01:11:20
本帖最后由 hskcool 于 2013-8-25 01:13 编辑

360软件小助手截图20130825010653.jpg

x*y(y<=x)的 N 皇后,“Cal”里只用了15行code,还是python最给力。

0 回复

举报

二十八画生 · 发表于 2013-9-7 20:51 点评

cal是什么

参与人数 1经验 +6 大洋 +10 收起 理由
wyx10022 + 6 + 10 很给力!

查看全部评分

hippo100312 | 设计助理 | 发表于 2013-8-25 10:11:49
wyx10022 发表于 2013-8-25 09:59
二位都是用的python吗? @hskcool

哦,我用的是C#
0 回复

举报

wyx10022 · 发表于 2013-8-25 10:18 点评

额,电池图上有显示,忘了,C语言用了多久了?我在高级课程训练营QQ群里给你留言了

wyx10022 | 网校特聘讲师 | 发表于 2013-8-25 10:18:33
hippo100312 发表于 2013-8-25 10:11
哦,我用的是C#

额,电池图上有显示,忘了,C语言用了多久了?我在高级课程训练营QQ群里给你留言了
0 回复

举报

hskcool | 设计师 | 发表于 2013-8-25 10:23:29
wyx10022 发表于 2013-8-25 09:59
二位都是用的python吗? @hskcool

我用的是Python
0 回复

举报

hskcool | 设计师 | 发表于 2013-8-25 10:23:35
wyx10022 发表于 2013-8-25 09:59
二位都是用的python吗? @hskcool

我用的是Python
0 回复

举报

乌龙 | 设计总监 | 发表于 2013-8-25 12:19:46
围观。。。
0 回复

举报

hf0419001 | 资深设计师 | 发表于 2013-8-25 12:52:49
hippo100312 发表于 2013-8-24 23:57
手动算法求出所有解比较消耗时间,我用代码求8皇后问题92个解,9皇后问题352个解。
...

都是用代码啊!
0 回复

举报

wyx10022 · 发表于 2013-8-25 12:57 点评

试试新版的hoopsnake能否实现回溯算法?

hf0419001 | 资深设计师 | 发表于 2013-8-25 12:54:32
hskcool 发表于 2013-8-24 19:12
并不一定的8的倍数。有可能出现轴对称或者是中心对称图形。

是不可能会有自身轴对称的情况的吧,那样不是互相能攻击了吗?
0 回复

举报

hskcool · 发表于 2013-8-25 13:34 点评

hf 说的没错。在皇后问题里面不能出现轴对称。

wyx10022 · 发表于 2013-8-25 12:59 点评

hskcool同学是说的两个解之间,会存在相似性,看看我列举的那9个,里面有几个是旋转其他的解得到的

wyx10022 | 网校特聘讲师 | 发表于 2013-8-25 12:57:56
hf0419001 发表于 2013-8-25 12:52
都是用代码啊!

试试新版的hoopsnake能否实现回溯算法?
0 回复

举报

hskcool | 设计师 | 发表于 2013-8-25 13:34:40
hf0419001 发表于 2013-8-25 12:54
是不可能会有自身轴对称的情况的吧,那样不是互相能攻击了吗?

hf 说的没错。在皇后问题里面不能出现轴对称。
0 回复

举报

hf0419001 | 资深设计师 | 发表于 2013-8-25 23:41:54
本帖最后由 hf0419001 于 2013-8-25 23:53 编辑

H.png
用hoopsnake嵌套简单做了一个,但是这个新版本好像有很多问题,调了好半天也不是很理想,而且算的过程实在是太慢了,recorder还会重复记录,好在电脑还能承受。

G.png
后来想了下用galapagos算了一遍,速度比hoopsnake快,但是估计与某个参数设置有关,很多种情况都不会算进去,调了两遍,第一次得到了25种情况,第二次得到了如图所示的36种情况,也懒得调了,这种问题用图形方式算可能优点就是更直观,速度就不说了,伤神。

Frame.png
这是得到的其中一种情况




0 回复

举报

hf0419001 · 发表于 2013-8-26 16:29 点评

有时候循环重启后F输出的不是S端的值,不知道是什么问题

wyx10022 · 发表于 2013-8-26 08:44 点评

真是下了功夫啊…… hoopsnake的新功能需要更深入的研究……

参与人数 1经验 +4 大洋 +8 收起 理由
wyx10022 + 4 + 8 很给力!

查看全部评分

小甲 | 设计助理 | 发表于 2013-8-26 03:04:21
本帖最后由 小甲 于 2013-8-26 03:09 编辑

7+6+5+4+3+2+1=28 28*2+14*2 即28*3=84
完全心算明天起床验证
0 回复

举报

wyx10022 | 网校特聘讲师 | 发表于 2013-8-26 08:44:11
hf0419001 发表于 2013-8-25 23:41
用hoopsnake嵌套简单做了一个,但是这个新版本好像有很多问题,调了好半天也不是很理想,而且算的过程实在 ...


真是下了功夫啊……
我也测试了下新版hoopsnake,其新功能需要更深入的研究……
0 回复

举报

hippo100312 · 发表于 2013-8-26 10:14 点评

新版主要是能做嵌套循环,手动是看不出效果的,必须自动循环才行

hippo100312 | 设计助理 | 发表于 2013-8-26 10:14:53
wyx10022 发表于 2013-8-26 08:44
真是下了功夫啊……
我也测试了下新版hoopsnake,其新功能需要更深入的研究…… ...

新版主要是能做嵌套循环,手动是看不出效果的,必须自动循环才行
0 回复

举报

wyx10022 · 发表于 2013-8-26 13:45 点评

恩,9皇后那个图,感觉有共线的皇后,还是我看错了?

GREAT123456 | 设计助理 | 发表于 2013-8-26 13:24:36
各种高端,c#/python各种算法,单用GH能实现不
0 回复

举报

wyx10022 | 网校特聘讲师 | 发表于 2013-8-26 13:45:29
hippo100312 发表于 2013-8-26 10:14
新版主要是能做嵌套循环,手动是看不出效果的,必须自动循环才行

恩,9皇后那个图,感觉有共线的皇后,还是我看错了?
0 回复

举报

hippo100312 · 发表于 2013-8-26 13:52 点评

果然有问题,所有的最后一个皇后都是共线,忘记关联一个参数,已经更新了

hippo100312 | 设计助理 | 发表于 2013-8-26 13:52:02
wyx10022 发表于 2013-8-26 13:45
恩,9皇后那个图,感觉有共线的皇后,还是我看错了?

果然有问题,所有的最后一个皇后都是共线,忘记关联一个参数,已经更新了
0 回复

举报

参与人数 1大洋 +5 收起 理由
wyx10022 + 5 很给力!

查看全部评分

hf0419001 | 资深设计师 | 发表于 2013-8-26 16:29:42
hf0419001 发表于 2013-8-25 23:41
用hoopsnake嵌套简单做了一个,但是这个新版本好像有很多问题,调了好半天也不是很理想,而且算的过程实在 ...

有时候循环重启后F输出的不是S端的值,不知道是什么问题
0 回复

举报

12下一页
推荐学习