MY WEB PAGES :
  • Main Page - Turkish
  • Sokoban
       Sokoban 1
       Sokoban 2
       Sokoban 3
       Sokoban 4
       E Sokoban
       Sokoban 5
    - This Page
       Sokoban 6
       Sokoban 7
       Sokoban 8
       Sokoban 9
       Sokoban 10
       Sokoban 11
       Sokoban 12
  • Language - Turkish

  • SEARCH ENGINE :


    Google Search
    www.erimsever.com





    Page Top
    Africaans - South African Albanian Arabic Armenian Azerbaijani Bask - Spain Belorussian Bengal Brunei Bahasa Malay Bulgarian Catalan Andorran Chinese Simplified Chinese Traditional Creole - Haiti Croatian Hrvatska Czech Ceská Republika Danish Danmark Dutch Nederland Estonian Eesti Farsi - Iran Filipino Pilipinas Finnish Suomi French Français Gal Galicia German Deutsch Greek Georgian Hebrew Hungarian Magyarország Icelandic Island Indian Hindi Indonesia Bahasa Irland Italian Italiano Japanese Kannada (Karnataka) Korean Latin - Mexico Latvian Latvija Lithuanian Lietuvos Macedonian Malaysian Malay Maltese Maltese Norwegian - Norge Polish - Polska Portuguese Português Romanian Româna Russian Serbian Slovak Slovencina Slovenian Slovenija Spanish Español Swahili - Jamaica Swedish Sverige Tamil - India Telugu - Sri-Lanka Thai Turkish Turkey Ukrainian Urdu - Pakistan Vietnamese

    SOKOBAN WEB REFERENCES (EDUCATIONAL AND PROGRESSIVE LOOK) (A to Z) :
    You can see full text or a very little summary or index at the bottom of the links



    100 Printable Puzzles and Solutions 1 provides players with 100 puzzles and solutions including crossword puzzles, codeword puzzles, fill-in puzzles, wordsearch puzzles, kakuro puzzles that offer much fun and entertainment. The file is in .pdf format for ease of use.



    A Survey of NP-Complete Puzzles Graham Kendall Andrew Parkes Kristian Spoerer - Nottingham, UK (pdf file page 13-34)



    A “very old” Flash Sokoban prototype November 13, 2007 by Emanuele Feronato



    Alien Sokoban Silverlight Project with codes, fully explains.

    And an other web page about WPF Alien Sokoban fully explains with source codes.



    Automatic Generation of "Sokoban" Problems - Yoshio Murase & Hitoshi Matsubara & Yuzuru Hiraga - Japan IPSJ JOURNAL Contents Vol.39 No.03 Mail Web page closed



    Automatic Making of Sokoban Problems - by Yoshio Murase & Hitoshi Matsubara & Yuzuru Hiraga - 1996



    Chapter 9 PSPACE: A Class of Problems Beyond NP - by Jon Kleinberg & Eva Tardos - 2005



    Computational Complexity of Games and Puzzles - Combinatorial Games, David Eppstein, ICS, UC Irvine

    Many of the games and puzzles people play are interesting because of their difficulty: it requires cleverness to solve them. Often this difficulty can be shown mathematically, in the form of computational intractibility results: every NP-complete problem is in some sense a puzzle, and conversely many puzzles are NP-complete. Two-player games often have higher complexities such as being PSPACE-complete.
    ...
    One caveat: NP-completeness is not a concept that applies to a single puzzle or game position, or even a finite collection of positions. It only makes sense to talk about an infinite family of problems as being NP-complete. For this reason games like chess cannot themselves be NP-complete, as they only have a finite (albeit unthinkably large) number of possible positions. In many cases however there is a natural generalization from some finite game or puzzle to an infinite family of game positions on arbitrarily large game boards, in which it makes sense to talk about NP-completeness. The fact that these infinite generalizations are computationally hard gives us some justification for believing that the original finite games are also hard in some less well-defined sense.
    INDEX :
    Puzzles and solitaire games: Alphametics, Clickomania, Cryptarithms, Cubic, 15-puzzle, Instant Insanity, KPlumber, Mah Jongg, Pearl puzzles, Rush Hour, Shanghai, Sokoban
    Two-player games: Amazons, Bridge-It, Checkers, Chess, Dots and boxes, Draughts, Go, Hex, Mastermind, Othello, Phutball, Reversi, Shannon switching game, Twixt
    ...
    Explains for all these games, and here is the Sokoban part :
    Description : A warehouseman moves around a rectilinear maze, pushing pallets one at a time from initial locations scattered throughout the maze until they are all placed in a designated loading dock.
    Status : PSPACE-complete.



    Distributed Analysis with µCRL: A Compendium of Case Studies
    Stefan Blom (2), Jens R. Calamé1, Bert Lisser (1), Simona Orzan (3), Jun Pang (4), Jaco van de Pol (1,3), Mohammad Torabi Dashti (1), and Anton J. Wijs (1)
    (1) CWI, Amsterdam, The Netherlands
    (2) Institut für Informatik, Universität Innsbruck, Austria
    (3) TU/e, Eindhoven, The Netherlands
    (4) Carl von Ossietzky Universität, Oldenburg, Germany




    Domain- Dependent Single-Agent Search Enhancements Link 2 - Junghanns & Schaffer, 1999



    Domain-Independent Construction of Pattern Database Heuristics for Cost-Optimal Planning by Patrik Haslum and Adi Botea NICTA & Australian National University, Malte Helmert Albert-Ludwigs-Universitat Freiburg, Blai Bonet Universidad Simon Bolývar, Sven Koenig USC



    Enigma Manual for version 1.00 Copyright c 2003, 2004, 2005, 2006 Daniel Heck



    Exercises and problems in Informatics December 2004 - Web page author
    New problem of sign S



    Experimenting with YASG and YASS. One way to do it. - How to make a computer generated level - by Sven Egevad 's very illustrative descriptions with examples.
    Explains with "Yasg" , "Yass" and his own QBasic programs "Washer.bas" , "Gensok.bas"



    Extending PDDL for Hierarchical Planning and Topological Abstraction - Adi Botea & Martin Müller & Jonathan Schaeffer - Universty of Alberta Canada



    Evolving a compact, concept-based Sokoban solver - Master thesis - School of Computer and Communication Sciences - Tom Schaul, April 18, 2005 (pdf file with 53 pages)



    Finding Optimal Solutions to Sokoban & Atomix Web page closed

    ...
    Pushing Blocks in Gravity is NP-hard - Friedman
    Corral Puzzles are NP-complete - Friedman
    Prediction of Regular Search Tree Growth by Spectral Analysis - Edelkamp
    Pushing Blocks is NP-Complete for Noncrossing Solution Paths - Demaine, Hoffmann (2001)
    Complexity Issues in Dynamic Geometry - Richter-Gebert, Kortenkamp
    Domain-Dependent Single-Agent Search Enhancements - Junghanns, Schaeffer (1999)
    PushPush and Push-1 are NP-hard in 2D - Demaine, Demaine, O'Rourke (2000)
    PushPush is NP-hard in 2D - Demaine, Demaine, O'Rourke (2000)
    PushPush is NP-hard in 3D - O'Rourke (1999)
    Sokoban: A Challenging Single-Agent Search Problem - Junghanns, Schaeffer (1997)
    Domain-Dependent Single-Agent Search Enhancements - Junghanns, Schaeffer (1999)
    Sokoban: Evaluating Standard Single-Agent Search.. - Junghanns, Schaeffer (1998)
    Planning Algorithms - LaValle (2004)
    Complexity Issues in Dynamic Geometry - Richter-Gebert, Kortenkamp
    Playing Games with Algorithms: Algorithmic Combinatorial Game.. - Demaine (2001)
    Spiral Galaxies Puzzles are NP-complete - Friedman
    Pearl Puzzles are NP-complete - Friedman
    ...



    From Laboratory to Warehouse: Security Robots Meet the Real World - by H. R. Everett, Douglas W. Gage (1999) Web page closed



    GP-Rush: Using Genetic Programming to Evolve Solvers for the Rush Hour Puzzle - Ami Hauptman, Achiya Elyasaf, Moshe Sipper, Assaf Karmon - Dept. of Computer Science, Ben-Gurion University, Beer-Sheva 84105, Israel



    Hierarchical Planning and Learning for Automatic Solving of Sokoban Problems - by Jean-Noel Demaret, Francois Van Lishout and Pascal Gribomont - Lab for User Cognition & Innovative Design, University of Liege, 4000 Liege, Belgium Montefiore Institute, University of Liege, Liege, Belgium. (English pdf file with 8 pages)



    HIROIMONO is NP-complete BRICS Basic Research in Computer Science - Daniel Andersson University of Aarhus BRICS Report Series RS-07-1 ISSN 0909-0878 January 2007



    How Good is Almost Perfect? - Malte Helmert and Gabriele Roger - Albert-Ludwigs-Universit¨at Freiburg, Germany.



    How to build a good Sokoban level? - Games 4 Brains - Mic © 2005



    How to Solve Sokoban : Alternate Methods - by Jukka Lahtinen - HTML Conversion by Kate Nepveu. Updated September 5, 2002.

    If you want to be able to solve Sokoban without immobilizing any boulders, here are two alternate methods. Boulder symbols are replaced by uppercase letters; all other possible items and monsters removed for clarity.

    Level 2, Version B :
     ABCDEFGHIJKLMNOPQRSTUVWX
     ----          -----------
    --.@--------   |.........|12
    |..........|   |.........|11
    |.A-----B-.|   |.........|10
    |..|...|.C.|   |....<....|9
    |.D.E....F-|   |.........|8
    |.G..H..|..|   |.........|7
    |.----I.--.|   |.........|6
    |..J...K.|.--  |.........|5
    |.---L-...M.------------+|4
    |...|..N-.O.^^^^^^^^^^^^.|3
    |..P......----------------2
    -----..|..|               1
        -------
     ABCDEFGHIJKLMNOPQRSTUVWX
    1. Push P to F3, and finish O. Push N to B2.
    2. Push B down 2, to H8. C left one to H2.
    3. Push M left one, to I4. F up one, to I9. B left two, from H8 to F8.
     ABCDEFGHIJKLMNOPQRSTUVWX
     ----          -----------
    --.>--------   |.........|12
    |..........|   |.........|11
    |.A-----.-.|   |.........|10
    |..|...|CF.|   |....<....|9
    |.D.E.B...-|   |.........|8
    |.G..H.@|..|   |.........|7
    |.----I.--.|   |.........|6
    |..J...K.|.--  |.........|5
    |.---L-..M..------------+|4
    |...|.P.-....^^^^^^^^^^^.|3
    |.N.......----------------2
    -----..|..|               1
        -------
     ABCDEFGHIJKLMNOPQRSTUVWX
    1. K down one, to G4. Finish M.
    2. K up one, back to G5.
    3. P right one, down one, right two, up two to where M was.
    4. Move K down one again, to G4, and finish P like M.
     ABCDEFGHIJKLMNOPQRSTUVWX
     ----          -----------
    --.>--------   |.........|12
    |..........|   |.........|11
    |.A-----.-.|   |.........|10
    |..|...|CF.|   |....<....|9
    |.D.E.B...-|   |.........|8
    |.G..H..|..|   |.........|7
    |.----I.--.|   |.........|6
    |..J.....|.--  |.........|5
    |.---L-K....------------+|4
    |...|...-....@.^^^^^^^^^.|3
    |.N.......----------------2
    -----..|..|               1
        -------
     ABCDEFGHIJKLMNOPQRSTUVWX
    1. Finish K, the moves for that should be trivial by now.
    2. Move N to the right, finishing it like P and M.
    3. Push L to where N is in the picture, finish it the same way as N.
    4. Push J to G5 and finish it. Now the screen looks like this:
     ABCDEFGHIJKLMNOPQRSTUVWX
     ----          -----------
    --.>--------   |.........|12
    |..........|   |.........|11
    |.A-----.-.|   |.........|10
    |..|...|CF.|   |....<....|9
    |.D.E.B...-|   |.........|8
    |.G..H..|..|   |.........|7
    |.----I.--.|   |.........|6
    |........|.--  |.........|5
    |.---.-.....------------+|4
    |...|...-........@.^^^^^.|3
    |.........----------------2
    -----..|..|               1
        -------
     ABCDEFGHIJKLMNOPQRSTUVWX
    1. Now finish I.
    2. Push C one down and one left (to G8) to clear the way between the passage
    3. there and the stairs.
    4. Push G one right, A one up and D one up.
    5. Now push E one right, and move B to I4.
    6. Move C one left, to F4. Finish B.
    7. Finish C like B.
     ABCDEFGHIJKLMNOPQRSTUVWX
     ----          -----------
    --.>--------   |.........|12
    |.A........|   |.........|11
    |..-----.-.|   |.........|10
    |.D|...|.F.|   |....<....|9
    |....E....-|   |.........|8
    |..G.H..|..|   |.........|7
    |.----..--.|   |.........|6
    |........|.--  |.........|5
    |.---.-.....------------+|4
    |...|...-...........@.^^.|3
    |.........----------------2
    -----..|..|               1
        -------
     ABCDEFGHIJKLMNOPQRSTUVWX
    1. Now you can finish E and H, and there you are.
    2. All remaining boulders movable.

    Level 4, Version A
    ...



    How to solve Sokoban levels in 3.3.1? - McDermontt



    ICGA Journal Vol. 25, No. 4 - December 2002
    REVIEW CHIPS CHALLENGING CHAMPIONS GAMES, COMPUTERS AND ARTIFICIAL INTELLIGENCE
    Edited by Jonathan Schaeffer and Jaap van den Herik - ISBN 0 444 50949 6 - Elsevier, 2002; 362 pp.
    $40; € 40 - Reviewed by Dap Hartmann



    Jeu de Sokoban recherche de solutions optiales - by Michael Hoste - 2008 - Universite de Mons-Hainaut Faculte des Sciences Institut d'Informatique (French language pdf file with 96 pages 3,63MB)




    L'intelligence artifcielle et les jeux : cas du Sokoban - by Jean-Noel Demaret - 2007 - Universite de Liege Faculte des Sciences Appliquees Institut Montefiore (French language pdf file with 88 pages 1,3MB)



    Macro Operations



    MGPT Problem 22 - Sokoban with Code - Author : Ashwani Pachauri Web page closed



    Nikita Danilov's Blog

    At the dlvl 10 there was a stairway up leading to the Sokoban branch of the dungeon. This branch extends upward, so the level numbers decrease. As passing this maze is one of the most tedious parts of the same, I took numerous shots, to record required sequence of moves:
    ...



    On the complexity of Sokoban - Stephen Sabey (Unpublished 1996)



    Planning with Pattern Databases by Stefan Edelkamp Institut fur Informatik Albert-Ludwigs-Universitat D-79110 Freiburg - October 19, 2000



    Problem A. Optimal bribing Goryinyich Challenge X (internet version) http://acm.sgu.ru/, October 23, 2009



    Problemdomänen Lloyd’s Puzzle und Sokoban R. Hofstetter, M. Zesiger - FH Bern - 07.01.03 (a German language pdf file with 46 pages)

    1 EINLEITUNG
       1.1 VORGEHEN
    2 LOYD’S PUZZLE
       2.1 EINLEITUNG
          2.1.1 Spielbeschreibung
          2.1.2 Komplexität
       2.2 IMPLEMENTIERUNG
          2.2.1 Spielzüge
          2.2.2 Heuristik
    3 SOKOBAN
       3.1 EINLEITUNG
          3.1.1 Spielbeschreibung
          3.1.2 Komplexität
          3.1.3 Bestehende Implementierungen
          3.1.4 Spielzüge
       3.2 HEURISTIK
          3.2.1 Kostenmatrix 6
          3.2.2 Heuristik Version 1 - Nearest Cost
          3.2.3 Heuristik Version 2 - Minimales Matching
          3.2.4 Heuristik Version 3 - Ungarischer Algorithmus für minimales Matching
          3.2.5 Heuristik Version 4 - Lineare Konflikte Version 1
          3.2.6 Heuristik Version 4 - Lineare Konflikte Version 2
       3.3 PROBLEMSPEZIFISCHE ERWEITERUNGEN
          3.3.1 Erweiterung IDA*: Closed Liste
          3.3.2 Deadlocks & Tote Felder
          3.3.3 Einführung in Makro Züge
          3.3.4 Implementierung Tunnel Makros
          3.3.5 Dynamic Update
          3.3.6 Moveordering
          3.3.7 Messresultate MoveOrdering
          3.3.8 Effizienz der Optimierungen
       3.4 OPTIMIERUNGSMÖGLICHKEITEN
          3.4.1 Vor- und Inkrementelle Berechnungen
          3.4.2 Closed Liste
          3.4.3 Tiefenschranke verbessern?
          3.4.4 Goal Makros
          3.4.5 Pattern Searches
    4 TECHNISCHE DOKUMENTATION DER IMPLEMENTIERUNG
       4.1 EINLEITUNG
       4.2 DESIGN PUZZLE
          4.2.1 Klassenbeschreibung
       4.3 DESIGN SOKOBAN
          4.3.1 Klassenbeschreibung
          4.3.2 Serielle Implementierung der Algorithmen
    5 VERZEICHNISSE
       5.1 ABBILDUNGSVERZEICHNIS
       5.2 TABELLENVERZEICHNIS
    6 QUELLEN
       6.1 XSOKOBAN LEVELS
    7 ANHANG



    Project 1: Classical Planning Robot Intelligence: Planning 8803 - Mike Stilman 8/31/2009 (pdf file with 4 pages)



    Rubik's Cube Design a challenge, Sokoban and challenges from bbs.mf8.com.cn Translate Google Page Chinese to English
    The theme of this floor-based design requirements summary
    I thought for this post an impromptu question is located, the title set a floor effect. I have no idea because at that time the ideal points, so use "current" vision measurement, problem-based is too simple. :)
    In order to update the results of comparison, are a House is no longer updated, 2nd floor into a summary of the design requirements to facilitate the later entry to the design state as early as possible in order to present the results in question is located on the rising demand, increasing the design difficulty, as well as crossing interesting .

    Title set is divided into two kinds of requirements: Approved request and reference requirements.
    Approval requirements: design of barriers must meet the requirements of this requirement be enforced.
    Reference requirements: design of barriers, where appropriate, in line with the requirements of this request no rigid rules.

    With the design of in-depth, theme-based requirement would be an appropriate increase or decrease, and some requirements may be reduced to the approved reference requests, some requests may also be upgraded to refer to approved requirements.
    The overall goal is to continuously improve the problem-based requirements, to increase the design difficulty, as well as crossing interesting.
    ...
    Conversation start with this level
    ...
    At an other page Translate Google Page Chinese to English
    An additional approval requirement: barriers in the person needs to be in open space.
    As tuitui their friends, the idea of release is too BT, leading to a large number of existing barriers to play only a "patch" after a little modification to meet the challenge, I now add a new approval requirements: barriers in the person needs to be in open space.
    Hoping to raise the level design more difficult.
    The so-called open space as opposed to speaking in terms of enclosed space.
    The closed space is released by the tuitui and their friends, the idea embodied.
    Question based on the open space, so I first definition: For the given points will be apart from the first to be driven outside the box to remove all the boxes, people from various angles in promoting the rest of the box.
    (Looking forward to an accurate description.)
    In other words, people should in a multi-channel environment, rather than in a single-channel environment.
    That is, if all boxes are removed, then people can leave this space from multiple channels, instead of only from the only channel to leave the room.
    For example these are the following (including but not limited to) the design of enclosed space.
    For example these are the following (including but not limited to) the open space design.
    Open space (multi-channel) and there is the possibility of increasing difficult to design? Wait and see.
    ...
    At an other page Translate Google Page Chinese to English
    This is a rather boring below and funny, but according to this thinking, at the top of the blank areas can play a number of imagination, so that more interesting and difficult points:
    ##################################
    #              #   #   #   #  #  #
    #  ###########                   #
    # #     #     #  ## ##  # # ##   #
    #   #  #  ### # #   # # ##  # #  #
    #  #  #  #    # ### # # ##  # #  #
    # #  #  #  ####   # # # # # # #  #
    ##  #  #  #     ##   ## # #  ##  #
    #  #  #  #  # #                  #
    # #  #  #  #  #     #            #
    #   #  #  #    # ### ########### #
    #  #  #  #    #    #          # ##
    # #  #  #    #    #          #   #
    ##  #  #    #    # #   #   ##    #
    #  #  #    #    #   #    ##      #
    # #  #    #    # #   #  #   #*   #
    #   #    #    #   #   #   #*  #  #
    #  #    #    #     ##   #*  #  # #
    # #    #    #    ##   #*  ##    ##
    ##    #    #   ##   #*  ##   #   #
    #    #    #   #   #*  ##         #
    #   #    # ##   #*  #  #         #
    #   #   # #   #*  ##    #        #
    #   #  ##   #*  # #  #   #       #
    ###   #   #*  #  #        #      #
    #  $+   #*  # #   #        #     #
    # #   #*  # # ##   #        #    #
    #  ###  # # # #     #        #   #
    #      #  # # #      #        #  #
    ##################################
    
    Conversation finished with this level
    There is also sending out a series of two customs, but the authors did not allow me leak. One of them I did not pass off, pushing the three days, only 11 actually Guobuliaoguan boxes. (Both off the origin is not part of the original wooden box)
    Thank migl President, and above a hurdle of the original author, as well as participate in the design of the Northwest, Mr. Sirius, so I learned a lot.
    ...
    Well, now left "BP and BM of the solution can not be the same as" It's not an instance of the. (Do not know whether there are ) )
    In other words :
    1. The level design without loopholes. (Example: there is no barrier does not meet the design requirements of the solution, there is no box can be transformed into a wall, or open space.)
    2. Hurdle clearance, the more step, then the initial state into a checkpoint.
    3. To promote the first box is a box to promote the last one. (Beginning and ending is the same one box push to promote need to fall into the first hurdle a box in which the initial state servant of the target point.)
    4. Crossing where the number of boxes involved in no less than 2.
    5. Effective way to avoid shamelessly violent actions. (The definition of acts shamelessly from the post experience of the first two pages.)
    6. The people crossing in the open space required. (The specific reference to this quote, 29 F)
    7. To promote the first one in the solution inside the box after only one target point. (Requested by: tuitui [30 F]) to refer to a condition: In addition to the first one outside wooden box, all other boxes move can not be more than one location.
    8. (Requested by: QQ Brother [30 F]) for the first
    9. BP and BM of the solution can not be the same.
    Erim Note : Maybe no.9 means, in addition, the first and the last one driving can still be driven by a different box.
    ...
    Can hair look, and then closed this post.

    Erim Note : Blog with lots of level examples at writings.



    Pushing Blocks Erik Demaine's Combinatorial Games



    Pushing Blocks is NP-Complete for Noncrossing Solution Paths - by Demaine, Hoffmann (2001)



    Pushing the Limits: New Developments in Single-Agent Search - Andreas Junghanns & Jonathan Schaeffer Department of Computing Science University of Alberta Edmonton, Alberta CANADA T6G 2H1 (October 16, 1999)

    OVERVIEW :
    Sokoban - History and Objective
    Sokoban - The Challenge
    Application-Independent Techniques
    Application-Dependent Techniques
    Knowledge Taxonomy/Classification
    Control-Function Knowledge
    Textbook vs Practice
    Single-Agent Search Framework
    Preprocessing
    Contributions, Conclusions and Future Work



    Ruby Quiz & Quiz Solutions

    Re: [QUIZ] Sokoban (#5) -- Games in Ruby Mail at 2 Nov 2004



    Scalable, Parallel Best-First Search for Optimal Sequential Planning by Akihiro Kishimoto Tokyo Institute of Technology and JST PRESTO, Alex Fukunaga Tokyo Institute of Technology,Adi Botea NICTA and The Australian National University.



    Semantic based classification of search enhancements by Hussain, S.J. Zaidi, F.A. - Dept. of Comput. Sci., Mohammad AIi Jinnah Univ., Karachi, Pakistan




    Simple Sokoban Example With Source Codes



    Single-Agent Search in the Presence of Deadlocks - Junghanns & Schäffer



    Soko Learn - Stefan Edelkamp - Universität Freiburg, 20-04-1997 - Mail - Broken Link

    Source : WWW-based documentation of all functions and files.
    Introduction : The Sokoban puzzle is one of the remaining one-person games in which the human solution quality still outperforms all attempts to automatic solving strategies coded in a computer program. In Sokoban n balls are placed somewhere in a maze containing n goal fields which they must eventually reach. The player controls a man which can traverse the board and push the balls onto adjacent empty squares. Three problems can be distinguished: Decide, Pushes and Moves. Decide is just the task to solve the puzzle. Pushes additionally asks to minimize the number of ball pushes whereas Moves request an optimal number of man movements. Although all problems are computational equivalent, the actual search spaces differ. Sokoban is proven to be NP-hard by Culbersone for a growing board and number of balls but polynomial for a fixed number of balls. A solution for Moves and Pushes implies a solution for Decide, but optimal solutions to Moves and Pushes fail to imply each other. Nevertheless, Moves turns out to be far more difficult for both human and machine. Comparing man and machine can be done by studying the the suite of 90 problems for the Sokoban Puzzle provided at xSokoban. Sokoban, especially Pushes, has been studied by Junghanns and Schaeffer (AAAI-1998). They proposed Sokoban to be a challenge to AI search techniques, and emphasized that the problem of deadlocks is critical for any real-time application. Their program manages to solve 29 positions in the optimal number of pushes. Even when minimizing the number of moves the problem space has to be compressed to a weighted graph with each edge corresponding to a ball push. The weight of the edge is given by the shortest path from the current man position to the next ball to move.
    Heuristic : As an heuristic estimate for Pushes Junghanns and Schaeffer propose a perfect weighted matching in the graph of shortest ball distances between each goal and each ball. This is done by using a minimum cost network flow algorithm based on n invocations of Dijkstra's original single source shortest path algorithm, which runs in O(n2). Furthermore, Junghanns and Schaeffer They showed that the heuristic can be refined, e.g., by counting the number of balls that are in a linear alignment. The underlying grid itself can be shortened to a weighted graph by introducing precomputed macro moves. Junghanns and Schaeffer distinguish tunnel macros and goal macros. The former forward a ball throughout a narrow corridor and the latter partition the search space by directly placing balls onto empty goal fields when entering a goal room on an articulation square (i.e., a sole entrance of width one). For the heuristic in Move we can add the heuristic values for the balls to a heuristic for the man. This value can be found using a similar minimum matching heuristic for the man, since he additionally has to cover all distances between goal fields and the balls. The distance of the man to the goal has once to be subtracted for admissibility.
    Stefan Edelkamp, 20-04-1997



    Sokoban and other motion planning problems (extended abstract) Dorit Dor, Uri Zwick, Tel Aviv University, 28 Juni 1995



    Sokoban: Evaluating standard single-agent search techniques in the presence of deadlock Andreas Junghanns and Jonathan Schaeffer 1998



    Sokoban Evolution - Lee Haywood

    Sokoban Evolution's SokHard ink blots - For explain "the number of permutations" with level's solution search tree pictures author Lee J. Haywood
    The starting position is at the bottom, the final moves are at the top.
    Vertical positions represent the number of box pushes made.
    The width represents the number of permutations found in the search tree.
    A solution would be represented as a line running from bottom to top.
    The number of permutations indicated here is not representative in each case.
    The complexity of the patterns is unlikely to reflect actual difficulty.
    The computer actually started with the solution and pulled the boxes back, which results in fewer permutations.
    Not to scale.
            
    These examples from Lee J. Haywood 's SokHard (for only 4 levels). If you want to download the complete set of 1024 × 768 blot images - SokHard_blots.zip (1.9 MB).




    Sokoban for Macintosh - Scott Lindhurst



    Sokoban Oyunu Araþtýrma Raporu
    Ortadoðu Teknik Üniversitesi
    Yapay Zeka Grubu, 2002


    Sokoban Game Research Report
    METU (Middle East Technical University)
    Artificial Intelligence Group 2002

    Source Web Page's Turkish Translates

    SOURCE INDEX :
    Sokoban: A Challenging Single Agent-Search Problem (1997)
    Sokoban: Single-Agent Search in the Presence of Deadlock (1998)
    Sokoban: Evaluating Single-Agent Search Techniques in the Presence of Deadlock (1998)
    Sokoban: Relevance Cuts: Localizing the Search (1998)
    Sokoban: Improving the Search with Relevance Cuts (1999)
    Domain-Independent Single-Agent Search Enhancements (1999)
    Sokoban: A Case-Study in the Application of Domain Knowledge in General Search Enhancements to Increase Efficiency in Single-Agent Search (2000)
    Automatic Making of Sokoban Problems (1996)



    Sokoban: improving the search with relevance cuts - Andreas Junghanns and Jonathan Schaeffer Department of Computing Science, University of Alberta, Edmonton, Alberta, Canada T6G 2H1 (pdf file)



    Sokoban is PSPACE - Joseph Culberson



    Sokoban is PSPACE-complate Draft Technical Report (node1) -(node2) -(node3) -(node4) - Joseph Culberson - Universty of Alberta Canada - For FTP
    Int. Conf. Fun with Algorithms, Elba, June 1998. Proceedings in Informatics 4, Carleton Scientific, Waterloo, Canada, 1999, pp. 65-76.



    Sokoban: Reversed Solving - Frank Takes - Leiden Institute of Advanced Computer Science (LIACS), Leiden University June 20, 2008 (pdf file with 6 pages)



    Sokoban solutions - Vintermann & Harald Korneliussen's weblog. September 14, 2005



    Sokoban Solver for AI course - AI sokoban solver



    Sokoban trace data format



    SokoMind Freeware Logic Puzzles - Phil Shapiro



    Solver Programs Descriptions - Faris Serdar TASEL



    The Educational Value of Sokoban Puzzles - Phil Shapiro. November, 1995

    Children enjoy thinking. One of the miracles of personal computers is that they can help younger and older children develop an appetite for logic puzzles.
    When I first saw the original, freeware Sokoban logic puzzles, I quickly became fascinated in trying to solve them. But the 50 original puzzles are so very difficult that it took me three weeks (and about 25 hours of thinking) to reach puzzle number 12.
    At that point it occurred to me that if the puzzles were made easier, they would have a strong appeal to children as well as adults. The directions for Sokoban said that it was possible to design your own puzzles using a word processor or text editor.
    Ever eager to try something new, I spent two or three hours designing my first "simple Sokoban" puzzle. But it soon occurred to me that I could far more easily modify existing Sokoban puzzles than to design my own "simple Sokoban" puzzles from scratch.
    I was especially intrigued in simplifying the existing puzzles into various "sub-puzzles," so that children who played each of the "sub-puzzles" would then have a fighting chance to attempt the original, "full" puzzles.
    Also, it made sense to have a series of "similar form" puzzles, where kids could say to themselves, "Gee, this puzzles looks somewhat similar to the puzzle I just solved. Let me try and discover what extra steps I need to do to solve this variation of the puzzle I just solved."
    There's a special appeal in playing logic games where each new puzzle is slightly more difficult than the last. In the 1990 book, The Art of Human-Computer Interface Design, educational software designer Joyce makes the following remarks: "Kids love the challenge and excitement of games. When a games is appealing and provides steadily increasing levels of difficulty, a child's interest lasts for a long time." (p. 124). When a logic puzzle is inherently appealing, children will have an inner motivation to want to solve increasingly more difficult versions of that particular type of puzzle.
    One of the reasons I find the Sokoban puzzles so especially interesting is that the puzzles can help students develop the type of visualization and spatial reasoning skills that could serve them well when they later study high school and college physics. Not only can the puzzles help students learn about the concept of "forces acting on a body," but the puzzles can also help sharpen and hone students analytical abilities.
    A few years ago educational researchers spent time interviewing college physics professors to find out the types of intellectual skills students should possess before studying physics. New York City researcher Arnold Peltzer wrote a 1988 article on this subject in the Journal of Research in Science Teaching. In that article, titled: "The Intellectual Factors Believed by Physicists to be Most Important to Physics Students," Peltzer concluded that, "four general intellectual factors are most important to physics students. They are the ability to reason in terms of visual images (visualization), mathematical insight (mathematics), the ability to evaluate the logic of arguments (logic), and the ability to attack problems in potentially productive ways (problem solving)." (p. 726). Volume 24, No. 9.
    Peltzer goes on to comment that the development of these four skills in younger students could pay handsome dividends five or ten years later when they tackle formal physics: "Science curricular from the earliest grades through high school physics could incorporate the cultivation of these four intellectual skills as explicit goals. Monitoring the growth of these intellectual abilities would give a developmental focus to science education to complement the teaching of the subject matter of science." (p. 730).
    Other researchers into this subject have arrived at parallel conclusions. In an article titled, "Enhancing the Visuo-Spatial Aptitude of Students," also published in the Journal of Research in Science Teaching, commentator Thomas R. Lord concludes: "It is the job of our schools to develop the cognitive potentials of its student population --- potentials that include the mental formation and manipulation of images. This study has found that a student's visuo-spatial cognitive potentials can be enhanced through carefully planned interactions. It is hoped that those responsible for creating the course curriculum for our schools include exercises that encourage spatial thinking." (p. 404). Volume 22, No 5.
    Problem solving skills have also received renewed emphasis by the National Council of Teachers of Mathematics (NCTM). In their 1989 "Curriculum and Evaluation Standards for School Mathematics," the NCTM urge that general problem solving skills be incorporated into the elementary and middle school curriculum. The NCTM believes that younger students should be given practice solving problems so that they develop a capacity to: "develop and apply strategies to solve a wide variety of problems." And once children develop a capacity to solve simple problems, they then "acquire confidence in using mathematics meaningfully."
    Similarly, the NCTM urges middle school students to have exposure solving "multistep and non-routine" problems. The Sokoban puzzles fit in well with the NCTM prescription for middle school students. The more difficult puzzles require multistep reasoning capability, and present students with many unique, non-routine problems. For that matter, the easier Sokoban puzzles fill the bill well for elementary level students. These easier puzzles are a gentle introduction to logical reasoning, with the benefit that each solved puzzle helps boost a child's confidence in tackling logic All in all, the Sokoban puzzles are an interesting, engaging way to introduce students to logical problem solving. Once students develop a basic mastery skill at playing the puzzles themselves, they can then try their hand at designing their own original puzzles. Puzzle design, itself, is a skill that calls for an interesting blend of creative and analytical skills.



    The First Answer Set Programing System Competition



    The KSokoban Handbook The link is not active now



    The Lemmings Puzzle: Computational Complexity of an Approach and Identification of Difficult Instances by Kristian Spoerer, BSc - Thesis submitted to The University of Nottingham for the degree of Doctor of Philosophy, 2007



    The Nondeterministic Constraint Logic Model Of Computation, ACM Computing Research Repository. R. A. Hearn and E. D. Demaine

    We present a nondeterministic model of computation based on reversing edge directions in weighted directed graphs with minimum in-flow constraints on vertices. Deciding whether this simple graph model can be manipulated in order to reverse the direction of a particular edge is shown to be PSPACE-complete by a reduction from Quantified Boolean Formulas. We prove this result in a variety of special cases including planar graphs and highly restricted vertex configurations, some of which correspond to a kind of passive constraint logic. Our framework is inspired by (and indeed a generalization of) the ``Generalized Rush Hour Logic'' developed by Flake and Baum.
    We illustrate the importance of our model of computation by giving simple reductions to show that several motion-planning problems are PSPACE-hard. Our main result along these lines is that classic unrestricted sliding-block puzzles are PSPACE-hard, even if the pieces are restricted to be all dominoes (1x2 blocks) and the goal is simply to move a particular piece. No prior complexity results were known about these puzzles. This result can be seen as a strengthening of the existing result that the restricted Rush Hour puzzles are PSPACE-complete, of which we also give a simpler proof. Finally, we strengthen the existing result that the pushing-blocks puzzle Sokoban is PSPACE-complete, by showing that it is PSPACE-complete even if no barriers are allowed.



    The Two Styles Of Sokoban or "The Potential Of Small Puzzles To Fool People" - Games 4 Brains - by David Holland



    Tutorial 2: A* and Genetic Algorithms by Derek Hao Hu - Sep 21, 2007



    Upwards: The Role of Analysis in Cost-Optimal SAS+ Planning - Andrew Coles and Amanda Smith Department of Computer and Information Sciences, University of Strathclyde, Glasgow, G1 1XH, UK (pdf with 4 pages)



    Using Abstraction for Planning in Sokoban Adi Botea, Martin Müllerand Jonathan Schaeffer (pdf file with 16 pages)



    Using Component Abstraction for Automatic Generation of MacroXSokoban



    Using Problem Reduction and Introspective-based Search for Sokoban - by T. Pannérec (France) - Online paper prize is $20.00



    Using Regression Match Graphs to Control Search in Planning - by Boudewijn Waijers with contributions by various others. HTML Conversion by Kate Nepveu Created March 5, 2001.



    Victoria University of Wellington - Computer Science - A Framework for Lightweight Web-based Visual Applications Donald Gordon Mail - Supervisors: James Noble and Robert Biddle .
    In University web page search engine all subjects about this article. And this article's explain PDF document.



    What People Have Said About Sokoban - Scott Lindhurst

    Many people around the world have praised my Sokoban for the Macintosh. It's one of the most advanced sokoban implementations available for any platform, yet uses only 150K of disk space and 250K of memory to run. The following comments are taken from actual e-mail messages.
    ...



    Why Sokoban - Mail

    Our research has a very practical nature: If a method does not work in practise, what is the point? We are not saying there is no value to theory, in fact, we use a lot of other people's theoretic results in our work, but we are primarily interested in systems that solve real problems. We like the immediate feedback of something that works and then works better because of our investigations and ideas.
    What makes Sokoban in particular so attractive to us?
    * Sokoban is easy to understand and visualize. If we want to see where the search makes mistakes or where the search is very efficient, Sokoban is very easy for me to understand as a domain. Many other problems are difficult just alone in how to picture what is going on.
    * The availability of test cases: We have an almost unlimited supply of test cases at our disposal. Industrial domains often lack that because companies are reluctant to share vital company data.
    * Different levels of difficulty: Since Sokoban problems come in all levels of difficulty, we can start with the easier ones, learn and improve the algorithms and thus measure progress on a gradual scale. Most other problems come in one size, you can either solve them or you don't - nothing in between.
    * Different types of problems: Sokoban problems come in an infinite variety of types, and not just size and difficulty. Different concepts are needed to solve different kinds of problems, leading to a very rich domain that never stops being a challenge. After all, that is what draws humans to it!
    * Deadlock: Sokoban offers an interesting feature. If you are not careful, you can create an unsolvable configuration. That is very much like most real world problems, where constraints exist that can create situations where no (good or optimal) solution can be had anymore. It is also interesting from a real-time perspective: if you need to make a move every so often without knowing that you can still produce a solution for sure, how do you minimize the risk of deadlock?
    * And not the least: Sokoban is fun! Why would we want to work on a boring and dry problem when we can work on a domain that humans have a real relationship with: love and/or hate it, loose sleep over it for no other reason but the challenge to tackle a really hard problem!
    Humans are incredibly apt in solving Sokoban puzzles. They are able to take advantage of the structure of the puzzles to develop higher level concepts that allow them to decompose the problems into loosely coupled subproblems or subgoals. This is what Artificial Intelligence is all about. And yet, we are having very limited success in carrying this human ability over into algorithms. Apart from the question if we want to make the machine solve the problem in a similar fashion as the humans, the more important aspect here is that if we want to successfully tackle the exponential nature of Sokoban problems, decomposition is essential and exhaustive search strategies are very ill equipped to decompose problems.
    Humans, however, can successfully solve Sokoban problems. As a testbed for artificial intelligence techniques, Sokoban offers a real challenge to researchers, since most of the core problems of artificial intelligence need to be addressed to build a successful program that rivals best human performance in solving Sokoban problems.



    XSokoban



    XSokoban - Andrew Myers Web page closed



    Zarko's Delphi Programming Blog Sokoban - Delphi (game) full source code to the Sokoban game


    © Erim SEVER from Turkey
    The most auspicious of people is the one who is beneficial to other people. - Hz. Muhammed - from Rumi's testament