解法步数随关卡大小成指数增长的关卡

zhenying

原帖由 sokoban 于 2009-6-14 07:40 发表
多谢ChangKai 兄答疑。ChangKai 兄贴的似乎和 jinyou 兄的是一样的。这一关的图如26楼所示。“人”的左边是墙，但是解法的第一步是 l，我百思不得其解。

粗心所致，导出的原关卡与jinyou兄的弄混，对不起sokoban兄了。
同样是李金玉的这一关，答案大约要10W。
################################
#  #  #  #  #  #  #  #  #  #   #
#  #.$   #.$   #.$   #.$   #.$ #
#.$#  #.$#  #.$#  #.$#  #.$#   #
#  #.$#  #.$#  #.$#  #.$#  #.$##
#.$#  #.$#  #.$#  #.$#  #.$#  #
#  #.$#  #.$#  #.$#  #.$#  #.$#
#.$#  #.$#  #.$#  #.$#  #.$#  #
#  #.$#  #.$#  #.$#  #.$#  #.$#
#.$#  #.$#  #.$#  #.$#  #.$#  #
#  #.$#  #.$#  #.$#  #.$#  #.$#
#.$#  #.$#  #.$#  #.$#  #.$#  #
#  #.$#  #.$#  #.$#  #.$#  #.$#
#.$#  #.$#  #.$#  #.$#  #.$#  #
#  #.$#  #.$#  #.$#  #.$#  #.$#
#.$#  #.$#  #.$#  #.$#  #.$#  #
#  #.$#  #.$#  #.$#  #.$#  #.$#
#.$#  #.$#  #.$#  #.$#  #.$#  #
#  #.$#  #.$#  #.$#  #.$#  #.$#
#.$#  #.$#  #.$#  #.$#  #.$#  #
#  #.$#  #.$#  #.$#  #.$#  #.$#
#.$   #.$   #.$   #.$   #.$   #
# @#  #  #  #  #  #  #  #  #  #
###############################
Author: 李金玉

sokoban

多谢 ChangKai 兄。这一关假设有 n 个箱子的话，推动数大概是 n^2 数量级。

[ 本帖最后由 sokoban 于 2009-6-14 15:43 编辑 ]

jinyou

对不起粗心了.
题目是我贴的答案演示到省略号时的图案.

jinyou

又找到一题
level 0
#####
# + ##
##$.$ #
#  *  #
#  *  #
##  ###
####  
level 1
#####
# + #
#$.$#
# * ##
## *  #
#  *  #
#  *  #
##  ###
####  
level 2
#####
# + #
#$.$#
# * #
# * #
# * ##
## *  #
#  *  #
#  *  #
##  ###
####  
level 7
#####
# + #
#$.$#
# * #
# * #
# * #
# * #
# * #
# * #
# * #
# * #
# * #
# * #
# * #
# * #
# * ##
## *  #
#  *  #
#  *  #
##  ###
####  

每一级增加两个箱子，只能是偶数个，奇数个无解

level0="rDrddlLUlldRdrUrruulDuullDDRUdddlUluRurrrddLUruL"

level1="rDDDLUdrrddlLUlldRdrUrruulDuullDDRUdddlUluRurrrddLLUlldRdrUrruulDuuuullDDRUldDDRUdddlUluRurrrddLLUdrruulDlddlUluRuuurrDDLUdrrddLLUlldRdrUrruulDuullDDRUdddlUluRurrrddLUruL"

level2="rDDDLUdrDDLUdrrddlLUlldRdrUrruulDuullDDRUdddlUluRurrrddLLUlldRdrUrruulDuuuullDDRUldDDRUdddlUluRurrrddLLUdrruulDlddlUluRuuurrDDLUdrrddLLUlldRdrUrruulDuullDDRUdddlUluRurrrddLLUlldRdrUrruulDuuuuuullDDRUldDDRUldDDRUdddlUluRurrrddLLUdrruulDlddlUluRuuurrDDLUdrrddLLUlldRdrUrruulDuullDDRUdddlUluRurrrddLLUdrruulDlddlUluRuuuuurrDDLUdrDDLUdrrddLLUlldRdrUrruulDuullDDRUdddlUluRurrrddLLUlldRdrUrruulDuuuullDDRUldDDRUdddlUluRurrrddLLUdrruulDlddlUluRuuurrDDLUdrrddLLUlldRdrUrruulDuullDDRUdddlUluRurrrddLUruL"

box=2X+4=箱子个数
X|box | Total Pushes |   Total Moves |
0|  4 |           15 |            48 |
1|  6 |           57 |           170 |
2|  8 |          167 |           494 |
3| 10 |          455 |         1,346 |
4| 12 |        1,209 |         3,580 |
5| 14 |        3,183 |         9,432 |
6| 16 |        8,351 |        24,756 |
7| 18 |       21,881 |        64,878 |
8| 20 |       57,303 |       169,922 |
9| 22 |      150,039 |       444,934 |
10| 24 |      392,825 |     1,164,928 |
11| 26 |    1,028,447 |     3,049,900 |
12| 28 |    2,692,527 |     7,984,824 |
13| 30 |    7,049,145 |    20,904,626 |
14| 32 |   18,454,919 |    54,729,110 |
15| 34 |   48,315,623 |   143,282,762 |
16| 36 |  126,491,961 |   375,119,236 |
17| 38 |  331,160,271 |   982,075,008 |
18| 40 |  866,988,863 | 2,571,105,852 |
19| 42 |2,269,806,329 | 6,731,242,614 |

这个比较象九连环
以下用FOXPRO写了一个解法计算程序(仅对此题)，从用到两重循环可知，一定是指数级的。

************
set talk off
clear

maxn=9
DIME sa[10],sb[10],sc[10],sz[10]
*Sc[0]=""
*Sa[0]=""
Sa[1]="DDLUdr"
*Sb0="LUlldRdrUrruulDuullDDRUdddlUluRurrrddL"
Sc[1]="LUdrruulDlddlUluRuuurrDDLUdrrddL"
Sb[1]="LUlldRdrUrruulDuu"+"ll"+"DDRUdddlUluRurrrddL"+ "LUlldRdrUrruulDuu" + "uu" +"ll" +"DDRUld" +"DDRUdddlUluRurrrddL"+ Sc[1]+ "LUlldRdrUrruulDuu"+"ll"+"DDRUdddlUluRurrrddL"
Sz[1]="rD"+Sa[1]+ "rddl" +Sb[1] + "UruL"

for n=2 to maxn

  Sa[n]=fm("DDLUdr",n)
  Sc[n]="LUdrruulDlddlUluRu" + fm("uu",n) +"rr"+ Sa[n] + "rddL"
  Sb[n]=Sb[n-1] +"LUlldRdrUrruulDuu" + fm("uu",n) +"ll" +fm("DDRUld",n) +"DDRUdddlUluRurrrddL"

  *Sb[n]=Sb[n] +Sc[1] +Sb[0]
  Sb[n]=Sb[n] +Sc[1] +"LUlldRdrUrruulDuullDDRUdddlUluRurrrddL"
  FOR j=2 to n
    Sb[n]=Sb[n] +Sc[j] +Sb[j-1]
  next
  Sz[n]="rD"+Sa[n]+ "rddl" +Sb[n] + "UruL"

  _cliptext=Sz[n]
  ?"level","box","move and push"
  ?      n,n*2+4, len(Sz[n])
  wait
next

return

func fm(fs,fm)
fss=""
if fm>=1 then
        for fi=1 to fm
                fss=fss+fs
        next
endif
return fss
***********

[ 本帖最后由 jinyou 于 2009-6-15 16:26 编辑 ]

anian

谢谢jinyou兄！ 不知道你的计算程序要用多少时间才算出100个箱子的推动和移动。
  我对FOXPRO不认识， 不然我就自几试试。

jinyou

我的程序只算了十几个箱子．１００个箱子答案长度比魔方的可能状态数还多，我这种字符串累加方法，怎么能用，要是只计算长度那是很快的．极限(L[n+1]/L[n])=2.618=(((根号5)+1)/2) * (((根号5)+1)/2) （n 对应的箱子数=2*n+4） 就是每加两个箱子将增加 黄金比例平方倍 。

xxx821006

31楼的关卡我有答案 50355/23300

migl

你给打了五折

sokoban

欢迎37楼的新朋友

jinyou

37楼朋友说的对，是这个数。50355四舍五入就是10万。