从解答步骤还原关卡地图

skyivben

我写了一个程序，可以从推箱子的解答步骤还原关卡地图。可以访问以下网页：Sokoban: Lurd to Xsb 在线使用该程序。

其算法可以参见我的博客：

• 【算法】从推箱子的解答步骤还原关卡地图
• 在 ASP.NET 网页中显示动态生成的图片

sokoban

我那破电脑算n=10就花了好几个小时。而且对 n=10 ，关卡可以说是无比平凡的，意义不大。

skyivben

这是一个很有趣的数学问题，而且好象也很难找到什么数学公式来计算所占的比例。
似乎也只有通过编程来计算了，那么当 n  很大时，计算所需的时间就会太长了，以致于无法完成计算。

sokoban

长为n的lurd串中有多少个是合法的？
在没有任何限制下，长为n的串的总数是8^n。
下面假设对一个合法的串，最后一步一定要是推，即最后一个字母只能是L,U,R,D之一。
若加上这个条件限制，长为n的串的总数为4 x 8^(n-1)

我曾经编程计算(就是对每个长为n的串都跑一遍还原关卡的算法)过比较小的n，合法的串的数目（没有详细反复验证，数字不一定对）

n          合法的串                        串的总数 4 x 8^(n-1)                           占的比例
1              4                                      4                                                          100%
2              24                                    32                                                     75%
3            156                                    256                                                 60.94%
4             912                                 2048                                                  44.53%
5            5536                               16384                                                  33.79%
6           31952                              13,1072                                              24.38%
7           187508                            104,8576                                            17.88%
8          1071696                           838,8608                                            12.78%
9           6168372                          6710,8864                                           9.19%
10        34972576                       5,3687,0912                                         6.51%

[ 本帖最后由 sokoban 于 2011-7-16 21:05 编辑 ]

sokoban

很喜欢用红色背景来辅助报错的设计，看上去很清楚。

skyivben

已经修改程序，对不合法的解法步骤给出相应的提示：Invalid。如下所示：

skyivben

好吧，根据大家的意见，我将修改程序，使之在解法步骤不合法的情况给出相应的信息。

rocwings

显然不报错，问题很多啊。最简单的情况如下：
答案：UuU
关卡：
###
#.#
#$#
#.#
#$#
#@#
###

显然错了

anian

我认为报错比较好。  如果没有提示， 我们会以为还原关卡的答案就是我们提供的LURD。   但事实上是不可以过关的。

skyivben

anina 兄您好，您给出的解法步骤中前六步是：UlLLUu。问题就出在第六步，因为第五步是“U”，表示推着箱子往上走一步，而第六步是“u”，表示不推箱子往上走一步，而这是不可能的，第五步中推着的箱子到哪里去了？我在“[url=http://www.cnblogs.com/skyivben/archive/2011/07/03/2096801.html]【算法】从推箱子的解答步骤还原关卡地图[/url]”这篇文章中“解法步骤不合法的情况”小节作了说明：

上面三幅关卡地图分别是从“LURD”、“Rrr”和“RL”解法步骤中还原出来的。对于这些不合法的解法步骤，本程序也不报错。本程序只保证合法的解法步骤能够还原出正确的关卡地图。此外，本程序还忽略解法步骤中“lurdLURD”以外的所有字符。

也就是说，我的程序对不合法的解法步骤并不报错(XhtXsb.exe应该也是这样)，只保证合法的解法步骤能够还原出正确的关卡地图。
当然，如果大家认为对不合法的解法步骤需要报错的话，我也可以修改程序。
感谢您的指正。