不论先后：
做出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

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



谨以第二题纪念逝者~~

[quote]原帖由[i]天痕[/i]于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



谨以第二题纪念逝者~~  [/quote]
第一个的代码等一下贴
幻方是指横竖斜的和都相等？
斜仅指主对角线吧？

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

是的

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

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

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

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

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

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

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

[quote]原帖由[i]kulaog[/i]于2005-01-12, 14:46:56发表
先算出第一题。
第二题只要判断是不是八阶幻方就可以拉，还需要知道“互不同构的八阶幻方至少存在12 631 127 040组”有什么用啊。
现在手懒，做不动，提个小建议。 [/quote]
单纯优化跳马问题，可以将解决时间降到毫秒级
可是想要单纯搜索某点所有跳马问题的解，找出其中八阶幻方的解
或者搜索所有某点为1的不同构的八阶幻方，从中找出跳马问题的解
估计时间在小时级
除非找到一个好的解发生算法，能够兼顾两个问题的求解

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

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

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

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

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


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


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

[quote]原帖由[i]天痕[/i]于2005-01-13, 4:27:55发表
[color=blue]“改进的启发式算法求得可行解的平均步数为73”[/color] [/quote]
其实就是用了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语言是因为那是以前做的作业题...
从硬盘上翻出来就提交了