魔方吧·中文魔方俱乐部

标题: 推箱子“死锁”讨论专贴 [打印本页]

作者: sokoban 时间: 2010-12-10 13:05:55 标题: 推箱子“死锁”讨论专贴

先引用anian兄提出的推箱子的一个重要技巧。

原帖由 anian 于 2010-12-10 09:41 发表
认识“死锁” (即是无论如何也无法过关的狀態) 和避免死锁。

无论是解小关卡还是难度大的关卡，这一技巧都会发挥作用。
另外“死锁“在计算机暴力解关中也会起到重要作用，可以通过发现死锁而
减小搜索空间。

因此我觉得有必要开个专贴供大家讨论。大家可以分享自己解关时是否有意识
地使用避免死锁的方法，如何使用这一方法，贴一些常见的死锁图，新发现的死锁图，等等。
任何和死锁相关的内容都可以讨论。

作者: anian 时间: 2010-12-10 13:22:50

应该还有很多死锁例子，我就列出几个常见的：

[soko=0,0]
HHHHHHHHHHHHHHHHHHHHHHHHHHHHHH
H____________________________H
H_$$_H__HH_H$_H__H____$H__$$_H
H_$$_$H_$$_$$_$$_$$__$_$_$_$_H
H______________H__$H_H$__$$__H
H____________________________H
H_HHHHH__HHHHH_HHHH_HHH_HHH__H
H_H_$_H__$___$__$_H_$_$__$H__H
H_H___H__HHHHH___$H_$$____H__H
H____________________________H
H_HHHHH__HHHHHHHHHH__________H
H___$_H__H_HH_____H__________H
H__$__H__H_.__H_$_H__________H
H_HHHHH__H_HH_____H__________H
H________H________H__________H
H____________________________H
HHHHHHHHHHHHHHHHHHHHHHHHHHHHHH
[/soko]

作者: stopheart 时间: 2010-12-10 13:50:04

anian兄的死锁图对初学者理解确实有帮助。
sokoban兄，要不搞一个小而精简的关卡，供大家在线推推玩？这样的关卡而又值得推得很多哦

作者: sokoban 时间: 2010-12-10 16:51:28

stopheart 兄的意思是搞一个小而精简的关卡，放在论坛上给大家推？还是什么其他形式？

作者: stopheart 时间: 2010-12-10 17:01:25

小而有难度的关卡集，让大家能在线推推

作者: laizhufu 时间: 2010-12-10 17:20:01 标题: 回复 5# 的帖子

小而难的关卡是多数人向往的。
每关最好能有一点提示（即注意事项）提供给不同层次的箱子迷，以提高过关的可能性和参与性。

作者: anian 时间: 2010-12-11 00:00:41

David W. Skinner的Microban系列都是很适合入门推箱子的人玩的。

Yoshio Murase的auto和handmade关卡集也很好，可以说精简。
但难度比Microban高了很多，适合给那些推完了Microban系列的人玩。

作者: 老熊 时间: 2010-12-11 10:40:58

[sokojava=320,340]
[param='level']------------------#@|-$$-$$-$#-#$-$#---##|-$$-#$-$#-$#-##----#|-------------------#|#------#####-------#|#*----.$---$.---####|#-$.---#####----#-.#|#-$.------------#--#|#*----------#####--#|#-----------#--$---#|#--------##-#-######|#.-----#-.#--------#|#$------$##--------#|#-*----------------#|#####--------------#|#---------------#--#|#*------.------#-.-#|#-$---#-$-#---#--$-#|#.-*--#*-*#------###|####################[/param]
[/sokojava]

作者: anian 时间: 2010-12-11 13:50:20

8#楼发的图好像有显示问题，你想发的是这个死锁例子图吗？

[soko=0,0]
__________________Ha
_$$_$$_$H_H$_$H___HH
_$$_H$_$H_$H_HH____H
___________________H
H______HHHHH_______H
H*____.$___$.___HHHH
H_$.___HHHHH____H_.H
H_$.____________H__H
H*__________HHHHH__H
H___________H__$___H
H________HH_H_HHHHHH
H._____H_.H________H
H$______$HH________H
H_*________________H
HHHHH______________H
H_______________H__H
H*______.______H_._H
H_$___H_$_H___H__$_H
H._*__H*_*H______HHH
HHHHHHHHHHHHHHHHHHHH
[/soko]

如果是的话，左下角的摆设不对，那个不是死锁例子。

作者: 老熊 时间: 2010-12-11 13:57:33

o 对，那里还有一堵墙的应该是。。。

作者: anian 时间: 2010-12-11 14:02:11

原帖由老熊于 2010-12-11 13:57 发表
o 对，那里还有一堵墙的应该是。。。

是这样吧？

[soko=0,0]
HHHHHHHHHHHHHHHHHHHH
H__________________H
H_$$_$$_$H_H$_$H___H
H_$$_H$_$H_$H_HH___H
H__________________H
H______HHHHH_______H
H*____.$___$.___HHHH
H_$.___HHHHH____H_.H
H_$.____________H__H
H*__________HHHHH__H
H___________H__$___H
H________HH_H_HHHHHH
H._____H_.H________H
H$______$HH________H
H_*________________H
HHHHH______________H
H_______________H__H
H*_____._______H_._H
H_$__H_$_H____H__$_H
H._*_H*_*H_______HHH
HHHHHHHHHHHHHHHHHHHH
[/soko]

作者: 老熊 时间: 2010-12-11 16:52:10

对。。。。。。。。。。
第一行是田字形。
其余是要靠着墙壁的

作者: 西北天狼 时间: 2010-12-13 09:33:57

“死锁”基本上分三类：
1、箱子靠墙，没有搬运工身位；
2、空间封闭，搬运工不能到达箱子后面；
3、搬运工和箱子都处于开放空间，目标点位循环（如图）。
[soko=9,7]
HHHHHHHHH
H_______H
H_._x_._H
H__$$$__H
H_*_*_*_H
H_______H
HHHHHHHHH
[/soko]

作者: anian 时间: 2010-12-13 12:36:16

Matthias Meger在这个网页也提到不少的“死锁”例子：

http://sokobano.de/wiki/index.php?title=Deadlocks

有些关卡，如果推错了一个箱子就会形成死锁。
无论如何推也无法过关，虽然所有箱子都可以动。
如下面这关：如果中间上面先推一个箱子下来就无法过关。

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

[soko=18,16]
_______HHHHHHH____
_HHHHHHH_____H____
_H_____H_$a$_H____
_H$$_H___HHHHHHHHH
_H_HHH......HH___H
_H___$......HH_H_H
_H_HHH......_____H
HH___HHHH_HHH_H$HH
H__H$___H__$__H_H_
H__$_$$$__H_$HH_H_
H___$_$_HHH$$_H_H_
HHHHH_____$___H_H_
____HHH_HHH___H_H_
______H_____H___H_
______HHHHHHHH__H_
_____________HHHH_
[/soko]

作者: Jordi 时间: 2010-12-13 21:42:03 标题: 回复 13# 的帖子

Yes ... This case is very interesting and frequent

[sokojava=112,128]
[param='level']#######|#-----#|#-.-*-#|#--$--#|#-*-*-#|#--@--#|#######[/param]
[/sokojava]

作者: Jordi 时间: 2010-12-13 21:50:44

-#####--
##---#--
#-.$.###
#-$@$--#
#-.$.--#
########
Author: Erim Sever
Title: erim097

[sokojava=128,112]
[param='level']-#####--|##---#--|#-.$.###|#-$@$--#|#-.$.--#|########[/param]
[/sokojava]

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)