Title: Sokoban YASC
Author: Brian Damgaard
Sokoban is an ubiquitous puzzle game. The first version came out in early 80s. Over the years there have been many clones and variants. I have wasted a bit of time with ksokoban which comes with most linux distros while I should have been working. But, for some reason which I cannot explain, I have never been a huge fan of sokoban. It has a simple idea and gives rise to some great puzzles which be really tough. Objectively, I should be a huge fan. Personal taste is a funny thing.
Just in case you have never played sokoban, here is a quick description. The goal is to get each crate, box, or stone to one the destination spaces. To do this, you use the man or bulldozer to push the crates about the maze. You can only push one crate at time into an empty space. Simple rules but some levels require thousands of moves.
Among the many windows clones, I like YASC (Yet Another Sokoban Clone) the best. It has a simple interface and controls, and comes with all the features you would expect: 1521 levels, unlimited undos, solution recording, and a level editor in case you solve all 1521 levels. There is deadlock detection which keeps you from doing really bone head moves. There are a dozen skins if you do not like the default graphics.
There are two unusual features of YASC which put it on top. The first is reverse mode. In this mode, the destinations and crates are flipped. Instead of pushing crates to destinations, you pull destinations to the starting positions of the crates. The reverse mode is logically equivalent to the forward mode. Strangely, some puzzles seem easier working in reverse.
The other unique feature of YASC is YASS (Yet Another Sokoban Solver). It turns out that solving sokoban puzzles can be quite hard. For some problems, the search space gets unmanageably large. YASS cannot solve all 1521 levels, but it does a pretty good job, and I have enjoyed playing with it.
A while back, I wrote my own sokoban solver using a best-first A* algorithm approach. I was surprised how difficult these problems can get. So, YASS impressed me. The University of Alberta gaming group have also taken stab at sokoban.
One odd feature of YASC is a built in music player. There is nothing like solving puzzles while listen to a little Moby.
I wish YASC recorded completed levels in a clearer fashion. I have no other complaints.
There are many other good sokoban programs. I have not tried them all, but one of the best is Sokoban++. The oxyd clone Enigma contains a set of sokoban levels. Another interesting program is Spherical.