只有一个箱子的关卡的最佳答案的步数

skyivben

请参阅：推箱子关卡最佳答案的步数

[ 本帖最后由 skyivben 于 2012-4-19 21:23 编辑 ]

sokoban

非常感谢银河兄提出的思路和猜想。

若银河兄的猜想是对的，25 x 25 时，最佳答案的最大值已超过 41,943,040，即B(23, 23)，这已经远远大于100, 000.
那么50 x 50 就不是大一点点了。如果理论值真的这么大，按道理找到一个具体的步数大于100,000的关卡并给出 xsb 格式应该是很有可能的。

另外，银河兄让我发现我的悬赏贴有一处表述不严谨，就是关卡还必须可解(否则步数就是无穷大了)，我在原帖没有强调这一点。

skyivben

左边是原来的关卡地图，最佳答案的步数是 23。
右边是改进后的关卡地图，最佳答案的步数是 25。
实际上 S(n, m) 是确定的，但实际上只有少数的 S(n, m) 的值是已知的，比如说 S(1, 6) = 4。
当 n, m 较大时，我们只知道 S(n, m) 的最小值，比如说：S(3, 6) ≥ 25。
希望各位朋友帮助改进 S(n, m) 的最小值。

skyivben

谢谢 sokoban 兄的指正。已经修正了我在博客园中的随笔，在 S(n, m) 的定义中加入了“可解的”这一限制。

sokoban

补充一个信息，已知 S(48,48) >=  99893  (即加上墙后50 x 50) 的关卡。

skyivben

B(n, m) 函数不必太当真，可能其值增长太快了一点，所以叫SB猜想。
这只是提供一种思路，可能需要寻找一个更靠谱的C(n, m)，增长不要那么快。
我想这个C(n, m)函数虽然增长不那么快，但是C(23, 23)仍然可能超过十万。
这个SC猜想应该更容易证明一点。

skyivben

非常感谢 Cielo 兄和 sokoban 兄的评分和鼓励。

skyivben

如果我们定义一个函数 T(n) = S(n, n)，那么，如果有一个富翁给出一个悬赏：
在 2099-12-31 之前求出 T(123456789) 的值并证明该值的正确性的个人和单位，奖励十亿元人民币。
那么，这笔奖金非常可能发不出去。

sokoban

的确，我觉得这个 T(48) 都已经很困难了。

skyivben

左边是原来的关卡地图，最佳答案的步数是 15。
右边是改进后的关卡地图，最佳答案的步数是 19。

更正：搞错了，右边的关卡地图，最佳答案的步数也是 15。

[ 本帖最后由 skyivben 于 2012-4-16 21:19 编辑 ]