跳马遍历问题 - 辕门射虎 - 轩辕春秋文化论坛 20周年


	loranrowe

组别	士兵
级别	奋威校尉
好贴	1
功绩	6
帖子	143
编号	17767
注册	2004-9-16

#1

发表于 2005-1-12 09:30 资料短消息看全部作者

QUOTE:

原帖由天痕于2005-01-12, 8:52:06发表
不论先后：
做出1得500
做出2得1000

1：跳马问题
国际象棋盘上某点上有一马，让马遍历整个棋盘没有重复。
输入：马的位置（I，J）（1〈=I〈=8；1〈=J〈=8）
输出：跳法（给棋盘标号）

2：还是跳马问题
在1的基础上按跳的顺序给棋盘上的点编号，最后要求跳出个8阶幻方来
输入：马的位置（I，J）（1〈=I〈=8；1〈=J〈=8）
输出：跳法（给棋盘标号）
时限：20s

谨以第二题纪念逝者~~

第一个的代码等一下贴
幻方是指横竖斜的和都相等？
斜仅指主对角线吧？

[广告] 真诚支持说岳，携手共创辉煌


	loranrowe

组别	士兵
级别	奋威校尉
好贴	1
功绩	6
帖子	143
编号	17767
注册	2004-9-16

#2

发表于 2005-1-12 09:50 资料短消息看全部作者

现已证明：互不同构的八阶幻方至少存在12 631 127 040组。（这个数字我没考证过）
这版程序每秒只能搜索400k步左右，显然构造所有幻方的想法是不成立了
只能通过检验knight tour的solution来解决了
假设solution的平均搜索步数为40k，20s只能有200个可行解
考虑java的效率问题，改编为c++，最多也只有2000个可行解
看来还得优化程序啊

附件: knighttour.rar (2005-1-12 09:50, 2.94 K)
该附件被下载次数 228

[广告] 真诚支持说岳，携手共创辉煌


	loranrowe

组别	士兵
级别	奋威校尉
好贴	1
功绩	6
帖子	143
编号	17767
注册	2004-9-16

#3

发表于 2005-1-12 14:58 资料短消息看全部作者

QUOTE:

原帖由kulaog于2005-01-12, 14:46:56发表
先算出第一题。
第二题只要判断是不是八阶幻方就可以拉，还需要知道“互不同构的八阶幻方至少存在12 631 127 040组”有什么用啊。
现在手懒，做不动，提个小建议。

单纯优化跳马问题，可以将解决时间降到毫秒级
可是想要单纯搜索某点所有跳马问题的解，找出其中八阶幻方的解
或者搜索所有某点为1的不同构的八阶幻方，从中找出跳马问题的解
估计时间在小时级
除非找到一个好的解发生算法，能够兼顾两个问题的求解

[广告] 真诚支持说岳，携手共创辉煌


	loranrowe

组别	士兵
级别	奋威校尉
好贴	1
功绩	6
帖子	143
编号	17767
注册	2004-9-16

#4

发表于 2005-1-13 09:19 资料短消息看全部作者

QUOTE:

原帖由天痕于2005-01-13, 4:27:55发表
“改进的启发式算法求得可行解的平均步数为73”

其实就是用了la Warnsdorff矩阵，这个矩阵记录了棋盘各点的度数
这个是初始矩阵
2,3,4,4,4,4,3,2
3,4,6,6,6,6,4,3
4,6,8,8,8,8,6,4
4,6,8,8,8,8,6,4
4,6,8,8,8,8,6,4
4,6,8,8,8,8,6,4
3,4,6,6,6,6,4,3
2,3,4,4,4,4,3,2
每走一步，将相关点的度数减1
每步尽量先走度数小的点
度数相等的点边角优先
还有其他一些规则
据Dr. Gerald Wildenberg的文章说
在这种原则下，以棋盘上的各点为起始点，求得第一个解的平均搜索步数为73
不过我很怀疑他提供的数据，因为他竟然有两个点fail了，就是在10M步中没有找到解

ps：
第一个题用java语言是因为那是以前做的作业题...
从硬盘上翻出来就提交了

[广告] 真诚支持说岳，携手共创辉煌