倉庫番

《倉庫番》是一款益智遊戲，由日本的Thinking Rabbit公司於1982年首次發行。之後其他遊戲開發者爭相製作仿製或衍生作品。致使倉庫番成為此類遊戲的代名詞。遊戲要求玩家在二維地圖上把箱子推到指定地點，當中牽涉到大量的空間邏輯推理。該遊戲在中國也叫倉庫番。

倉庫番的規則

KDE內建的倉庫番遊戲KSokoban

第一個《倉庫番》的遊戲規則，則是扮演工人的玩家，以「推」的方式，推動箱子。可以在沒有阻礙物（如牆壁等的阻礙物）的情況下，向左、右、上、下的地方移動。將箱子移動到指定點，達到指定數量，即可過關。

但玩家移動箱子，有下列條件要注意：

推到牆壁的箱子，玩家就不可以背對牆壁，把箱子推回到空處。即箱子只能以「推」的方式移動，不能以「拉」的方式移動。但如果玩家推至牆壁後，垂直牆壁的兩側沒有阻礙物，則玩家可以朝這兩個不同的方向推移箱子。
一旦箱子被移動到角落，玩家沒有任何方法再移動這個箱子。
玩家不可同時推動兩個及以上的箱子。假設工人面前有一個箱子，箱子的正前方又有一個箱子，則這兩個箱子是不能推動的。

倉庫番雖然規則簡單，但要完美通關卻需要不少技巧。首先，在開始移動之前，建議你花一些時間仔細觀察整個地圖的布局。注意箱子和目標點的分布，以及可能的障礙物位置。提前在腦海中規劃出大致的倉庫番路線，這樣可以避免走入死胡同。

在推動箱子時，最需要注意的是避免將箱子推到角落或者緊貼牆邊的位置。因為一旦箱子被推到這些位置，通常就無法再將其拉出來，這可能導致整個關卡無法完成。特別要當心的是兩個箱子並排被推到牆邊的情況，這往往會造成死局。

可以在線倉庫番，可以設計自己的關卡。

倉庫番已經通過計算複雜性理論進行了研究。解決倉庫番難題的計算問題首先被證明是NP難的^[1]，進一步的研究證明它也是PSPACE完全的^[2]。

基於基礎的規則，有的遊戲添加了數量有限的炸彈破壞牆壁方可達成目標；重力添加到遊戲中；可以改變特性的牆壁、機關；可以收集的物品（原本是障礙物）。

^ M. Fryers and M.T. Greene. Sokoban. Eureka. 1995, (54).
^ Joseph C. Culberson, Sokoban is PSPACE-complete （頁面存檔備份，存於網際網路檔案館）. Technical Report TR 97-02, Dept. of Computing Science, University of Alberta, 1997. Also: http://web.cs.ualberta.ca/~joe/Preprints/Sokoban^{[永久失效連結]}