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

sokoban

我想是不是可以编个程序来算一下。给定n,m ，算 S(n,m)，当n,m都比较小，应该可以穷举算出来。

给定一个迷宫布局（也就是墙的位置给定），如何安置人，箱子和目标，使得最佳答案步数最大。

然后所有迷宫布局算一遍。 对S(3,5)， 只有 2^15 = 32768 种不同布局(根据对称性，还有重复的)。

skyivben

当 (n, m) 值较小时，编程计算 S(n, m) 是个很好的想法。
目前我还没有研究如何编程自动解答一个推箱子的关卡，所以暂时还无法编程计算 S(n, m) 的值。

skyivben

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

skyivben

其实，对于 S(3, 5)，就算不考虑对称性造成的重复，也不用计算 2¹⁵ 种不同的迷宫布局。

首先，箱子、目标、人这三者至少需要占用两个位置。实际上，箱子需要单独占用一个位置，目标和人可以共同占用一个位置，也可以占用两个不同的位置。

其次，对对 n 和 m 均不小于 3 的关卡而言，如果关卡内部没有墙的话，决不可能是最复杂的。

所以，就算不考虑对称性造成的重复，对于 S(3, 5) 也只需计算 2^{15 - 2 - 1} = 4096 种不同的迷宫布局就行了。

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

skyivben

进一步，我们定义以下函数：

• P(n, m, k) 表示大小为 (n + 2) x (m + 2) 的可解的最复杂的最多 k 个箱子的关卡的最佳答案的步数。
• Q(n, m, k) 表示大小为 (n + 2) x (m + 2) 的可解的最复杂的刚好 k 个箱子的关卡的最佳答案的步数。
• R(n, m) = P(n, m, n * m)，表示大小为 (n + 2) x (m + 2) 的可解的最复杂的关卡的最佳答案的步数。
• S(n, m) = Q(n, m, 1)，表示大小为 (n + 2) x (m + 2) 的可解的最复杂的只有一个箱子的关卡的最佳答案的步数。

显然，R(n, m) ≥ S(n, m)，也更值得研究。

西北天狼

########
#------#
#---.#-#
##-##--#
#--##$##
#------#
#--#--@#
########


[ 本帖最后由 西北天狼 于 2012-4-19 10:38 编辑 ]

西北天狼

---####
####-@#
#--$--#
#--#--#
#-##-##
#-----#
#.#---#
#######

sokoban

S(4,5) ≥ 30

######
#.---#
#-#--#
#-#--#
#-$--#
#-#-@#
######

西北天狼

改进一下：S(4,5) ≥ 32
######
#.#--#
#----#
#-#--#
#-$--#
#-#-@#
######

ssxx

S(4,5) ≥ 35

######
#---.#
#-#-##
#-#--#
#-$--#
#-#-@#
######

加一个图：


[ 本帖最后由 ssxx 于 2012-4-19 12:52 编辑 ]