Sokoban
So, I was wasting time before going to bed last night, like, by setting up this site, and by playing Sokoban. KSokoboan to be precise. Now, I made it up to level 12 of David W. Skinner’s Microban level set, which is rightfully said to be pretty easy. Well, level 12 wasn’t, at least not to me. (I admit that that’s embarassing, but who cares.)
So, I made it to the “I can prove this unsolvable” stage of puzzle solving. But since I reckoned that someone would have noticed that this level is unsolvable, my mind immediately went to cheating. Unfortunately, nobody had published move sequences to solve Microban. I was absolutely clueless as to how this level might be solvable, and I just had to know. So, I wrote a Python program to solve Sokoban levels. You’ll find sokosolve.py and a few demo levels in the sokoban-solver module of my 2004-public arch tree.
The program itself has two nested applications of A*, a usable (but half-baked) heuristic and a complete game model. In just 215 lines. Python never fails to impress me. Attached to this story you can see a dump of the program solving the level that had me so confused.
| Attachment | Size |
|---|---|
| m12-dump | 1.13 KB |
All content bearing the “inducer” username is hereby licensed under
Creative Commons Attribution-Share Alike 2.5 License.
For the purposes of German law: I am not repsonsible for material on pages linked to from this site.
I found myself in much the same situation with microban level 142 as you did with level 12. Having a budding interest in Python and a need to solve 142, I happen upon sokosolver in a Google search.
Unfortunately, sokosolver seems to be having trouble with 142 (I did get it to work for 12, just to validate correct operation on my machine). While I’m not running on the fastest hardware (by a long shot), I have to think that after several hours that it may have gone infinite. Do you get an answer for 142? Am I just being impatient?
Post new comment