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

sokoban

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

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

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

sokoban

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

sokoban

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

sokoban

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

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

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

sokoban

S(4,5) ≥ 30

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

sokoban

1. ##################################################
   
2. #---####--#---##--#---##--#---##--#---##--#---#--#
   
3. #---------#-------#-------#-------#-------#------#
   
4. ##-#####--##-###--##-###--##-###--##-###--##-##--#
   
5. #-----##-###--##-###--##-###--##-###--##-###--#-##
   
6. #--#--#-------#-------#-------#-------#-------#-##
   
7. #--#-##---##--#---##--#---##--#---##--#---##--#-##
   
8. ####--#########################################-##
   
9. #-$---#--##---#--##---#--##---#--##---#--##---#-##
   
10. #-##-@#-------#-------#-------#-------#-------#-##
    
11. #-#####--###-##--###-##--###-##--###-##--###-##-##
    
12. #-##--##-##--###-##--###-##--###-##--###-##--##-##
    
13. #--#------#-------#-------#-------#-------#------#
    
14. ##-#--#---#--##---#--##---#--##---#--##---#--#---#
    
15. #--##-############################################
    
16. #-###-##--#---##--#---##--#---##--#---##--#---#--#
    
17. #--#------#-------#-------#-------#-------#------#
    
18. ##-#---#--##-###--##-###--##-###--##-###--##-##--#
    
19. #--#####-###--##-###--##-###--##-###--##-###--#-##
    
20. #-#--#--------#-------#-------#-------#-------#-##
    
21. #-#--#---###--#---##--#---##--#---##--#---##--#-##
    
22. #-#--#####--######--######--######--######--###-##
    
23. #--#-----#-------#-------#-------#-------#-------#
    
24. ##-#-##--#--###--#--###--#--###--#--###--#--##---#
    
25. #--#-#--###-##--###-##--###-##--###-##--###-######
    
26. #-##-#-------#-------#-------#-------#--------#--#
    
27. #--#-#--##---#--##---#--##---#--##---#--###---#--#
    
28. ##-#-###--######--######--######--######--#####--#
    
29. #--#-###--#-------#-------#-------#-------#-----##
    
30. #-#-------#--###--#--###--#--###--#--###--#--##-##
    
31. #-#-#-##-###--##-###--##-###--##-###--##-###--#-##
    
32. #-#---#-------#-------#-------#-------#-------#-##
    
33. #--####---##--#---##--#---##--#---##--#---##--#-##
    
34. ##-#--#########################################--#
    
35. #--#---------------------------------------------#
    
36. #-##--############################################
    
37. #--##-##--#---##--#---##--#---##--#---##--#---#--#
    
38. ##-#------#-------#-------#-------#-------#------#
    
39. #--#---#--##-###--##-###--##-###--##-###--##-##--#
    
40. #-######-###--##-###--##-###--##-###--##-###--#-##
    
41. #-#---#-------#-------#-------#-------#-------#-##
    
42. #---#-#---##--#---##--#---##--#---##--#---##--#-##
    
43. #####-#########################################-##
    
44. #---#-#--##---#--##---#--##---#--##---#--##---#-##
    
45. #-----#-------#-------#-------#-------#-------#-##
    
46. ##-#-.#--###-##--###-##--###-##--###-##--###-##-##
    
47. #--#####-##--###-##--###-##--###-##--###-##--##-##
    
48. #---------#-------#-------#-------#-------#------#
    
49. #--####---#--##---#--##---#--##---#--##---#--#---#
    
50. ##################################################
    
51. Title:一箭十万 b
    
52. Author:20603

复制代码

[ 本帖最后由 sokoban 于 2012-4-20 18:25 编辑 ]

sokoban

感谢20603先生发来的上面关卡。大师一出手，十万大关轻松地过了。20603兄说还能优化。

101451/632，在论坛的java程序里看演示就花了17分钟。建议大家用具有“瞬间移动”功能的程序来演示，如《歪推箱子》，《SokoPlayer HTML5》等等。

下面是静态图片：


[ 本帖最后由 sokoban 于 2012-4-20 18:32 编辑 ]