Trying to solve a Sokoban level with brute force

Before you even think this script will solve a Sokoban level, I must warn you: this script won’t solve a sokoban level, it won’t even recognize whether a level is solved or not.

This script, part of an old project I am going to bring to life again, will just make Sokoban wander around the maze eventually pushing crates here and there, according to Sokoban’s rules.

Feel free to add some backtracking to make it more interesting, but I have to say coding a Sokoban solver could be a nightmare.

If you want to see another Sokoban script (this time to play the game), read Javascript Sokoban game script.

Sokoban levels are shown and created this way:

# = wall
$ = crate
. = place
* = crate in place
@ = man
+ = man in place

And now the script…

And this is the result:

Feel free to do something interesting with the script…

  • It has not…

    … been solved yet. but i can!

  • First off, I appologize if this offends you, but are you a boy or a girl?

    I ask only because First i thought you were a guy, because your name is Emanuele. But then you got your new logo and it looks like you are a girl. So i figured, “i guess Emanuele could be a girls name”. Now i see at the bottom of this post, “the geek has spoken… share HIS words”. This causes confusion for me.

    It really doesnt matter, i just want clarification. Either way, Great post. Love your work. Look forward to seeing more of your work

  • lol… Alex.

  • Alex, after this post ( http://www.emanueleferonato.com/2009/01/14/improve-your-brand-with-a-logo-part-2/ ) not even the regulars are sure anymore.

    :P

  • What use is this script?

  • Xodus

    lol, he is a guy, the logo is a bit misleading but read this post:
    http://www.emanueleferonato.com/2009/01/14/improve-your-brand-with-a-logo-part-2/

  • The first thing I would do with this script is breaking out of the loop once is_solved() returns true.

    It is not a big optimization but the script wouldn’t print many useless iterations of the map.

  • dim

    i think, gilrs will never be interested with these kind of things :) this answer at half for the question i guess :)

  • dim

    oh, and thanks a lot for good posts Emauele … i’m yure fan !

  • Good job. Now you are just a step away from an evolutionary algorythm for generating Sokoban puzzles by the thousands.

  • Hey its that guy

    Anyone know how I can contact Emanuele? I think someone may be trying to steal Emanuele’s games and put them under their own name.

  • Hey its that guy

    Whoop, nevermind. Its not there anymore so I assume they did the right thing and removed it.

  • Looks good :)

    First the Soduku and now this. Keep up all these “classic” engines. I really am interested in learning how to make these type of common well used generic engines.