推箱子论坛 - Powered by Discuz! Board

标题: 关于一个推箱子问题的悬赏 [打印本页]

作者: sokoban 时间: 2012-3-20 11:45 标题: 关于一个推箱子问题的悬赏

本帖最后由 sokoban 于 2012-4-20 12:22 编辑

在经典的推箱子游戏规则下，满足下面三个条件的关卡至今仍没有找到：
(1)大小在50x50以内，包括作为边界的墙体在内
(2)恰有1个箱子（当然也恰有1个目标）
(3)最佳答案大于或等于100000（十万）步，强调一下是最佳答案，即步数最少的答案。
问题：满足上面三个条件的推箱子关卡存在吗？

若找到一个这样的关卡，则容易验证。
若证明这样的关卡不存在，则用数学方法证明（写出详细的推导过程），或用计算机穷举证明（必须提供c语言源代码，计算时间不能太长），或两者结合。

所以，我个人悬赏人民币500元(伍佰元)给第一个对这个问题给出肯定或否定回答的人。获取这一奖金的方法和条件在下面一楼详细说明。

更新：2012年4月19日，这个问题由20603兄给出了肯定的回答。

作者: sokoban 时间: 2012-3-20 12:34

本帖最后由 sokoban 于 2012-3-20 15:11 编辑

首先是悬赏的目的：

1. 完全出于好奇心，和对这个问题的答案很感兴趣。

2. 虽然推箱子不算什么太严肃的研究对象，但是这个悬赏还是可以勉强归入学术悬赏，所以对社会应该完全没有坏处。著名的匈牙利籍数学家Paul Erdős(保罗·埃尔德什,1913-1996)就以个人名义对许多数学问题公开悬赏，奖金从几十美元到几千美元不等。
以下引用维基百科(wikipedia): http://en.wikipedia.org/wiki/Paul_Erd%C5%91s

Throughout his career, Erdős would offer prizes for solutions to unresolved problems. These ranged from $25 for problems that he felt were just out of the reach of current mathematical thinking, to several thousand dollars for problems that were both difficult to attack and mathematically significant. There are thought to be at least a thousand such outstanding prizes, though there is no official or comprehensive list.

其次，参与方式：

3. 解答者把自己研究得到的解答直接通过电子邮件发送至 yangchao0710@gmail.com
若给出肯定的回答，只需提供xsb格式的关卡文件即可。
若给出否定的回答，则需要给出严格的证明。

4. 解答是否正确，以我的判断为准。提交答案者要赋予我在网络上公开答案的权利（当然，解答的著作权还是归作者）。

5. 对无效、不正确或我没有能力验证（如用超级计算机穷举）的解答，我有权不作任何解释和说明而判定所提交的答案不能获得奖金。

6. 对第一个我确认正确的提交解答，确认后我将支付提交者奖金，奖金为固定金额人民币伍佰元整。提交者须提供在中国大陆的银行开户的人民币银行帐号。确认后三个月内不提供银行帐号（或者我没有收到）视为自动放弃奖金。

7. 在问题被解决之前，本奖金长期有效。

8. 对以上未说明清楚的地方，我有最终解释权。

作者: anian 时间: 2012-3-21 09:35

的确是一个非常有趣的问题。

作者: sokoban 时间: 2012-4-20 09:49

20603兄已设计出超过十万步关卡，问题解决了。

欢迎光临推箱子论坛 (http://sokoban.ws/bbs/)