推箱子“死锁”讨论专贴

sokoban

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

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

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

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

Jordi

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

Jordi

Yes ... This case is very interesting and frequent

anian

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

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


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

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

西北天狼

“死锁”基本上分三类：
1、箱子靠墙，没有搬运工身位；
2、空间封闭，搬运工不能到达箱子后面；
3、搬运工和箱子都处于开放空间，目标点位循环（如图）。

老熊

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

anian

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

是这样吧？

老熊

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

anian

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




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

老熊