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


	天痕


	白衣伯爵中大夫

组别	白衣卿相
级别	右将军
好贴	4
功绩	224
帖子	1182
编号	208
注册	2003-8-29

#1

发表于 2005-1-12 08:52 资料主页个人空间短消息只看该作者

不论先后：
做出1得300
做出2得1000

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

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

参加者以附件形式提交程序

谨以第二题纪念逝者~~

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	loranrowe

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

#2

发表于 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

谨以第二题纪念逝者~~

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

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	天痕


	白衣伯爵中大夫

组别	白衣卿相
级别	右将军
好贴	4
功绩	224
帖子	1182
编号	208
注册	2003-8-29

#3

发表于 2005-1-12 09:33 资料主页个人空间短消息只看该作者

幻方是指横竖斜的和都相等？
斜仅指主对角线吧？

是的

第一个纯粹送钱，第二个有时间限制的才有意义。

第一题奖金改少了，不过既然你先发帖了你的就不变吧~~

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	天痕


	白衣伯爵中大夫

组别	白衣卿相
级别	右将军
好贴	4
功绩	224
帖子	1182
编号	208
注册	2003-8-29

#4

发表于 2005-1-12 09:41 资料主页个人空间短消息只看该作者

我先去睡觉
6小时后回来查收

本题1截止于北京时间1月15日零点
题2不设截止时间

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


	loranrowe

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

#5

发表于 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)
该附件被下载次数 229

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


	天宫公主 (司徒家的颖颖)


	虞国公主 ★

组别	限制发言用户
级别	大将军
好贴	6
功绩	517
帖子	11552
编号	1037
注册	2004-10-25
来自	天津
家族	司徒实业

#6

发表于 2005-1-12 10:04 资料主页短消息只看该作者

题目和我上大一时的一个家庭作业一样，我用的是C＋＋，最后算了一夜才出来的。就说当时的电脑还都是奔3一类的，可20秒也忒短的点吧？

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	kulaog

组别	百姓
级别	在野武将
功绩	0
帖子	7
编号	26506
注册	2004-12-2

#7

发表于 2005-1-12 14:46 资料短消息只看该作者

先算出第一题。
第二题只要判断是不是八阶幻方就可以拉，还需要知道“互不同构的八阶幻方至少存在12 631 127 040组”有什么用啊。
现在手懒，做不动，提个小建议。

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	loranrowe

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

#8

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

QUOTE:

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

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

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


	kulaog

组别	百姓
级别	在野武将
功绩	0
帖子	7
编号	26506
注册	2004-12-2

#9

发表于 2005-1-12 15:05 资料短消息只看该作者

先算出第一题，放到内存里面，数量就是有限的，然后判断每一种跳法是不是八阶幻方就可以啦，事情就是一步一步做的啊。为什么要一口吃成胖子啊。
8+8+2=18，只要12次加法就可以算出这种跳发是不是八阶幻方，12*n步，也不多阿。应该比第一个还快啊。

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


	kulaog

组别	百姓
级别	在野武将
功绩	0
帖子	7
编号	26506
注册	2004-12-2

#10

发表于 2005-1-12 16:28 资料短消息只看该作者

只要检验结果是不是八阶幻方，谁要你算出八阶幻方又多少可能啦。

就好像给你10组数字，每组2个数字，问你那组数字加起来等于0。
而你却要求出所有加起来等于0的2个数字，这个也没有解啊。

关键在于是检验不是求解。

[广告] 《精忠报国岳飞传完整版》火热发布


	天痕


	白衣伯爵中大夫

组别	白衣卿相
级别	右将军
好贴	4
功绩	224
帖子	1182
编号	208
注册	2003-8-29

#11

发表于 2005-1-13 04:27 资料主页个人空间短消息只看该作者

loranrowe第一题正确！
loranrowe 2005-01-13 ￥ 500 轩辕通宝

不过建议用C++来，JAVA的速度实在不敢恭惟啊~~

loranrowe能不能把“改进的启发式算法求得可行解的平均步数为73”说详细一点？这个我好像不知道

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	loranrowe

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

#12

发表于 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语言是因为那是以前做的作业题...
从硬盘上翻出来就提交了

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