SEARCH ENGINE :

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, fillin puzzles, wordsearch puzzles, kakuro puzzles that offer much fun and entertainment. The file is in .pdf format for ease of use. A Survey of NPComplete Puzzles Graham Kendall Andrew Parkes Kristian Spoerer  Nottingham, UK (pdf file page 1334) 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 NPcomplete problem is in some sense a puzzle, and conversely many puzzles are NPcomplete. Twoplayer games often have higher complexities such as being PSPACEcomplete. ... One caveat: NPcompleteness 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 NPcomplete. For this reason games like chess cannot themselves be NPcomplete, 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 NPcompleteness. 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 welldefined sense. INDEX : Puzzles and solitaire games: Alphametics, Clickomania, Cryptarithms, Cubic, 15puzzle, Instant Insanity, KPlumber, Mah Jongg, Pearl puzzles, Rush Hour, Shanghai, Sokoban Twoplayer games: Amazons, BridgeIt, 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 : PSPACEcomplete. 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 SingleAgent Search Enhancements Link 2  Junghanns & Schaffer, 1999 DomainIndependent Construction of Pattern Database Heuristics for CostOptimal Planning by Patrik Haslum and Adi Botea NICTA & Australian National University, Malte Helmert AlbertLudwigsUniversitat 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, conceptbased 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 NPhard  Friedman Corral Puzzles are NPcomplete  Friedman Prediction of Regular Search Tree Growth by Spectral Analysis  Edelkamp Pushing Blocks is NPComplete for Noncrossing Solution Paths  Demaine, Hoffmann (2001) Complexity Issues in Dynamic Geometry  RichterGebert, Kortenkamp DomainDependent SingleAgent Search Enhancements  Junghanns, Schaeffer (1999) PushPush and Push1 are NPhard in 2D  Demaine, Demaine, O'Rourke (2000) PushPush is NPhard in 2D  Demaine, Demaine, O'Rourke (2000) PushPush is NPhard in 3D  O'Rourke (1999) Sokoban: A Challenging SingleAgent Search Problem  Junghanns, Schaeffer (1997) DomainDependent SingleAgent Search Enhancements  Junghanns, Schaeffer (1999) Sokoban: Evaluating Standard SingleAgent Search..  Junghanns, Schaeffer (1998) Planning Algorithms  LaValle (2004) Complexity Issues in Dynamic Geometry  RichterGebert, Kortenkamp Playing Games with Algorithms: Algorithmic Combinatorial Game..  Demaine (2001) Spiral Galaxies Puzzles are NPcomplete  Friedman Pearl Puzzles are NPcomplete  Friedman ... From Laboratory to Warehouse: Security Robots Meet the Real World  by H. R. Everett, Douglas W. Gage (1999) Web page closed GPRush: Using Genetic Programming to Evolve Solvers for the Rush Hour Puzzle  Ami Hauptman, Achiya Elyasaf, Moshe Sipper, Assaf Karmon  Dept. of Computer Science, BenGurion University, BeerSheva 84105, Israel Hierarchical Planning and Learning for Automatic Solving of Sokoban Problems  by JeanNoel 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 NPcomplete BRICS Basic Research in Computer Science  Daniel Andersson University of Aarhus BRICS Report Series RS071 ISSN 09090878 January 2007 How Good is Almost Perfect?  Malte Helmert and Gabriele Roger  AlbertLudwigsUniversit¨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 :
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 MonsHainaut 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 JeanNoel 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 AlbertLudwigsUniversitat D79110 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 floorbased 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, problembased 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 indepth, themebased 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 problembased 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 socalled 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 multichannel environment, rather than in a singlechannel 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 (multichannel) 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 NPComplete for Noncrossing Solution Paths  by Demaine, Hoffmann (2001) Pushing the Limits: New Developments in SingleAgent 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 ApplicationIndependent Techniques ApplicationDependent Techniques Knowledge Taxonomy/Classification ControlFunction Knowledge Textbook vs Practice SingleAgent 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 BestFirst 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 SingleAgent Search in the Presence of Deadlocks  Junghanns & Schäffer Soko Learn  Stefan Edelkamp  Universität Freiburg, 20041997  Mail  Broken Link Source : WWWbased documentation of all functions and files. Introduction : The Sokoban puzzle is one of the remaining oneperson 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 NPhard 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 (AAAI1998). They proposed Sokoban to be a challenge to AI search techniques, and emphasized that the problem of deadlocks is critical for any realtime 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(n^{2}). 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, 20041997 Sokoban and other motion planning problems (extended abstract) Dorit Dor, Uri Zwick, Tel Aviv University, 28 Juni 1995 Sokoban: Evaluating standard singleagent 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 AgentSearch Problem (1997) Sokoban: SingleAgent Search in the Presence of Deadlock (1998) Sokoban: Evaluating SingleAgent Search Techniques in the Presence of Deadlock (1998) Sokoban: Relevance Cuts: Localizing the Search (1998) Sokoban: Improving the Search with Relevance Cuts (1999) DomainIndependent SingleAgent Search Enhancements (1999) Sokoban: A CaseStudy in the Application of Domain Knowledge in General Search Enhancements to Increase Efficiency in SingleAgent 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 PSPACEcomplate 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. 6576. 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 "subpuzzles," so that children who played each of the "subpuzzles" 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 HumanComputer 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 VisuoSpatial 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 visuospatial 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 nonroutine" 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, nonroutine 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 inflow 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 PSPACEcomplete 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 motionplanning problems are PSPACEhard. Our main result along these lines is that classic unrestricted slidingblock puzzles are PSPACEhard, 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 PSPACEcomplete, of which we also give a simpler proof. Finally, we strengthen the existing result that the pushingblocks puzzle Sokoban is PSPACEcomplete, by showing that it is PSPACEcomplete 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 CostOptimal 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 Introspectivebased 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 Webbased 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 email 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 realtime 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 