Nice work Phil for finishing Boxy Boy and to Beejay for finishing it's clone. It took me a while just to solve the first world and some of those later levels look incredibly difficult too.

About doing it in the minimum number of steps, I wonder if it is possible to write a program to solve this game. I did this a long time ago for a similar game but it only worked for certain types of levels.

Cheers, GAZ

-- LordGaz (garyjlee@hotmail.com), September 16, 2001

Answers

Thanks Gary ... As maybe some of you knows, I'm VERY VERY found of this game ; I discovered it more than an year ago, and my recent scores on boxyboy/soukobdx are the fruit of a long study : my only aim is to optimize steps scores (I've improved some of them recently) even if Mame games have a stupid scoring ... the longest distance you walk, the highest points you get :(((( ; that's why BeeJay have a better final score with worst steps scores on soukobdx

To study the game , I used a program Skito sent me one year ago and I have collected in it more than 2000 levels on the net !!! If someone is interested, I can send it to him

Concerning a program solving sokoban levels, I did find one on the web, but for levels with more than 3 boxes, it takes too long (more than 24 hours is sometimes not enough with a P600, I didn't try more) ; and it didn't replace the high pleasure you get when you solve yourself a level :))

But if someone has a better program I'm interested because I still don't manage to solve several levels of my 2000+ collections ...

-- phil (plamat@club-internet.fr), September 16, 2001.

Oh I forgot ... If you want more sokoban levels and highscores (I have some there), go to this adress : http://database.spprod.se/Soko/sokoHighscore.lasso

-- phil (plamat@club-internet.fr), September 16, 2001.

There is a good program (still isn't perfect for larger levels) that will solve optimal pushes, for rooms that have about a 500 square area. I think it's an NP complete problem so there probably isn't a program that will solve all problems perfectly in a reasonable amout of time. Optimizing pushes is probably a more practical application since it's a lot easier to walk/move than it is to push an object depending on how heavy the object is. It definitly finds different solutions if you are concered about optimizing moves only, like sokoban deluxe requires.

the link to this code and algorithm is

http://www.cs.ualberta.ca/~games/Sokoban/

I've been trying to convert the code to optimize moves only but i couldn't get it to work. The real practical way to do this is to have an objective function that optimises both moves and pushes together since moving and pushing require some energy, pushing requires a bit more than moving. If anyone finds a better code link than this please post, this one is the best i could find.

-- Chad (churritz@cts.com), September 17, 2001.

I had a sokoban period a couple of months ago and looked around for a good solver. I found this web pages with a java applet that is faster than most programs I tested. Unfortunately it only handles small problems.

Takaken's sokoban solver: http://www.ic-net.or.jp/home/takaken/so/soko/index.html

Just recently I found a french site with a solver that is using Takaken's algorithms. It is said to be even faster than Takaken's solver. I haven't tested it myself yet.

Solveur Sokoban: http://perso.wanadoo.fr/paul.voyer/sokoban/solveur.html

The fastest solver I found is incorporated in a freeware Sokoban program for OS/2 and Win32. It can handle rather large problems.

http://www.xylo.freeserve.co.uk/sokoban.htm

If anyone has any more solver I would be interested. I tried to write one myself a year or so ago. I never did implement all of the optimizations I had planned, though, and it turned out too slow for larger problems.

And Phil, I _did_ manage an eagle once in Mario's Open Golf in the form of a hole-in-one. As I remember it I put two balls out of bounds right after that and never finished the round.

-- Abbe (Albin@518.nu), September 18, 2001.

I think these solvers don't find optimal solutions, but they do find solutions which is cool. I wouldn't go to the french site (maybe site down.) I branch and bound algorithm might be possible to find optimal sokoband pushes/moves, i also tried and never got around to finishing a sokooptimalsolver.

-- Chad (churritz@crash.cts.com), September 18, 2001.

Paul Voyer is not french but canadian if I remember correctly ; his solving program is the "solve.exe" I sent you, Skito

And Abbe : congrats for your hole-in-one ; I know now IT is possible

-- phil (plamat@club-internet.fr), September 18, 2001.

oops i typed i "wouldn't" but i meant I "couldn't" I can now. thanks phil.

-- Chad (churritz@crash.cts.com), September 18, 2001.

A* pathfinding finds the optimal solution but I have no clue about sokoban solvers, help?

-- ed (pc_devil_2000@hotmail.com), July 14, 2002.