New Level -- Sokoban: Proof of Concept (10 boxes)

Post, download, and discuss custom levels for Return To Wonderland.
Post Reply
Muzozavr
Rainbow Spirit Chaser
Posts: 5648
Joined: Wed Jan 11, 2006 2:55 pm

New Level -- Sokoban: Proof of Concept (10 boxes)

Post by Muzozavr » Wed Aug 31, 2011 8:04 am

This is not a very hard level, nor would it be special if it weren't for one simple thing...

It's a Sokoban level with more than nine boxes. There's ten. You can count them, if you're curious. :wink:

How do we usually do Sokoban-like puzzles in Wonderland? With boxes and buttons, of course. It's the norm. It's the easiest, most obvious way to replicate the Sokoban mechanics in Wonderland, with one glaring flaw... you can't have more than nine buttons. So if we do it like that we can only have nine boxes or less.

Sometimes that's a good thing -- not everyone wants to walk around a huge level pushing piles of stuff -- but there's many great Sokoban puzzles out there which just need a few more boxes...

Back in "Just One Coin Is Easy" I have figured out that you can replace buttons with open gates. When they all snap shut, the boxes get destroyed and you use a box generator then. But in that level (and in my conversion of "Supasoka" too) the gate placement itself is incredibly obvious, you don't really need to see them visually.

How do you convert levels in which the gates are placed "wherever"? They're too hard to see when they're open, which would make it needlessly confusing. And you can't even replace the floor tiles underneath them to make the floor itself look different.

And then I figured out: why not replace all other floor tiles? :wink:

... sometimes, the best ideas are the simplest.

This is a level with the "Garden" texture, and everything else is covered with the "D" floor tile. The difference between them and the gates (which still have the default, green "A" floor tile underneath them) is incredibly visually obvious, allowing me to do a Sokoban level with 10 boxes.

The level itself is pretty simple, I don't think you will have many problems with it. Just download it to see how Sokoban levels should be done in Wonderland.
You do not have the required permissions to view the files attached to this post.
Rest in peace, Kym. I hardly knew ya.
Rest in peace, Marinus. A bright star, you were ahead of me on my own tracks of thought. I miss you.
User avatar
dig 222
Rainbow Star
Posts: 1279
Joined: Sat Jan 15, 2011 11:44 am

Post by dig 222 » Wed Aug 31, 2011 9:29 am

Downloaded and enjoyed the level.
Thanks for the fun!
:)
Amnon
Rainbow Spirit Seeker
Posts: 6576
Joined: Wed Mar 22, 2006 5:29 am

Post by Amnon » Wed Aug 31, 2011 4:14 pm

Nice level and not as easy as you said - thanks for the fun!

However, you already used this idea in "Supasoka", where you had 12 boxes: http://www.pcpuzzle.com/forum/viewtopic.php?t=11463
Muzozavr
Rainbow Spirit Chaser
Posts: 5648
Joined: Wed Jan 11, 2006 2:55 pm

Post by Muzozavr » Wed Aug 31, 2011 5:21 pm

But in that level (and in my conversion of "Supasoka" too) the gate placement itself is incredibly obvious, you don't really need to see them visually.
Yes, I did use that in my conversion of Zjeraar's "Supasoka" level, and also in "Just One Coin Is Easy". The thing that's new here is changing all the other floor tiles, allowing you to visually SEE the proper spots for the boxes. You don't have to strain your eyes staring at the screen anymore. :lol:
Rest in peace, Kym. I hardly knew ya.
Rest in peace, Marinus. A bright star, you were ahead of me on my own tracks of thought. I miss you.
Marinus
Rainbow AllStar
Posts: 4686
Joined: Sun Dec 16, 2007 2:20 pm

Post by Marinus » Wed Aug 31, 2011 7:58 pm

Fun level, indeed not so very hard. Thanks for the fun.

Good idea to use different floortiles.

I'm trying the other one for a little one, but that's pretty much harder.
Image
Muzozavr
Rainbow Spirit Chaser
Posts: 5648
Joined: Wed Jan 11, 2006 2:55 pm

Post by Muzozavr » Wed Aug 31, 2011 8:28 pm

If by "other one" you mean Supasoka, then yes, it's very much harder despite the simpler initial appearance. It's not actually my level, it was made by someone with a username "Zjeraar" for a different game. I wasn't able to solve it back then, and I wasn't able to solve it after posting it here either -- I had to use a solver program to give others a hint.
Rest in peace, Kym. I hardly knew ya.
Rest in peace, Marinus. A bright star, you were ahead of me on my own tracks of thought. I miss you.
Marinus
Rainbow AllStar
Posts: 4686
Joined: Sun Dec 16, 2007 2:20 pm

Post by Marinus » Wed Aug 31, 2011 9:05 pm

Yes, that's what I meant, because Amnon posted the link to that level. I guess, to do this "SupaSoka", I need "SupaPowa" to push 4 or 5 boxes all at once. :lol:

But well, I will try a little while longer. :)
Image
Amnon
Rainbow Spirit Seeker
Posts: 6576
Joined: Wed Mar 22, 2006 5:29 am

Post by Amnon » Thu Sep 01, 2011 2:30 pm

But in that level (and in my conversion of "Supasoka" too) the gate placement itself is incredibly obvious, you don't really need to see them visually.
Just to clarify, I failed to read this part of the post before I rushed into the level, then I thought the idea was familiar and remembered Supasoka without seeing you mentioning it first. Meanwhile I managed to redo Supasoka!
User avatar
|Cookie|
Rainbow Star
Posts: 1991
Joined: Mon Mar 21, 2011 8:34 am

Post by |Cookie| » Thu Sep 01, 2011 3:09 pm

it's nice level. :D
Previously known as "kidkidaaa1"
My level list
My hub: TTN
Woof Woof
User avatar
doodlebug
Rainbow Master
Posts: 799
Joined: Fri Mar 14, 2008 5:01 pm

sokoban ten boxes

Post by doodlebug » Thu Sep 01, 2011 8:05 pm

Easy level. Thanks for the fun

Annie
User avatar
VirtLands
Rainbow Master
Posts: 756
Joined: Thu Dec 29, 2005 1:49 am

re: 10Boxes

Post by VirtLands » Thu Sep 01, 2011 11:39 pm

quote="Muzozavr" { .. I have figured out that you can replace buttons with open gates.
When they all snap shut, the boxes get destroyed and you use a box generator then. }

Fascinating concept.

Sokobans are hard for me, so
I used Sokoban Automatic Solver for this one.

So far, it's 150moves, 37pushes, 12carries, ... :shock:

http://www.ic-net.or.jp/home/takaken/e/soko/index.html
Last edited by VirtLands on Sat Sep 03, 2011 8:17 pm, edited 2 times in total.
Muzozavr
Rainbow Spirit Chaser
Posts: 5648
Joined: Wed Jan 11, 2006 2:55 pm

Post by Muzozavr » Fri Sep 02, 2011 4:00 am

LOL. It's actually quite simple despite the number of moves: once you figure out a few key tricks, everything else just completely falls into place.

I actually have no idea what "carries" are. Does that solver explain?
Rest in peace, Kym. I hardly knew ya.
Rest in peace, Marinus. A bright star, you were ahead of me on my own tracks of thought. I miss you.
User avatar
VirtLands
Rainbow Master
Posts: 756
Joined: Thu Dec 29, 2005 1:49 am

10Boxes reply continuued...

Post by VirtLands » Sat Sep 03, 2011 8:15 pm

I searched that website and I couldn't figure out what "carries" are.

I'm lucky to find sokoban solvers, but there are some
sokobans that are so complex that these can
neither be solved by machine nor human.

Anyone listing such a complex puzzle as the following
in this forum should be sokobanned, ha,ha.
☹

❉❉❉❉❉❉❉❉❉❉❉❉❉❉❉❉❉❉❉❉❉❉❉❉❉❉❉❉❉❉❉❉❉❉❉❉❉❉❉❉❉❉❉❉❉❉❉❉❉❉❉❉❉ ☮
Last edited by VirtLands on Sat Sep 03, 2011 10:45 pm, edited 1 time in total.
Marinus
Rainbow AllStar
Posts: 4686
Joined: Sun Dec 16, 2007 2:20 pm

Post by Marinus » Sat Sep 03, 2011 8:24 pm

there are some sokobans that are so complex that these can neither be solved by machine nor human.
I thought a computerprogram can simply try out every single possibility, no matter how many milli- or megaseconds it takes.

BTW, if no one can solve them, how can there be evidence that they can be solved?
Image
User avatar
VirtLands
Rainbow Master
Posts: 756
Joined: Thu Dec 29, 2005 1:49 am

solving sokobans

Post by VirtLands » Sat Sep 03, 2011 10:41 pm

quote="Marinus" { BTW, if no one can solve them, how can there be evidence that they can be solved? }

Hi M.,
(Where do you find those megasecond terms? :) )

I started up Jsoko, which is probably the best sokoban solver ever.
http://sourceforge.net/projects/jsokoapplet/

Then I entered this complex sokoban test which is UpTight Hamlet:
Image

I temporarily shut down FireFox, allowing that extra (~200MB) RAM to be
used by Jsoko; The more complex the sokoban level
is, the more computer RAM is used in an attempt to solve it.

My laptop has 2.5 gigabytes RAM, and that was apparently not enough.

The Jsoko program ran well for about 25 minutes, and finally
faild to solve it due to an insufficient memory error. :shock:

At the point of failure the Jsoko consumed an amazing
531 megabytes. SO, then my PC had no more free mem
to offer it, and the program stopped.
Image

So, my computer tried to solve it during the period of
0.0015 megasecond = 1.5 kiloseconds =
41⅔ % hour.

If anyone would like to make a more efficient sokoban solver,
and share the code with us,... I'll be waiting.

So, I have faith it can be solved, just not today.


ᖗ »»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»» ᖘ
Amnon
Rainbow Spirit Seeker
Posts: 6576
Joined: Wed Mar 22, 2006 5:29 am

Post by Amnon » Sat Sep 03, 2011 11:15 pm

BTW, if no one can solve them, how can there be evidence that they can be solved?
One way is if the author worked their way backwards when creating the puzzle. There may also be a clever logical principle which must be understood, whereas a machine can only go by trial and error of an extreme number of possibilities, possibly including red-herrings which a human can see and ignore.
Marinus
Rainbow AllStar
Posts: 4686
Joined: Sun Dec 16, 2007 2:20 pm

Post by Marinus » Sat Sep 03, 2011 11:24 pm

Hi Andy

I actually don't remember that I ever heard or read the word "megasecond" before; I just combined the words "mega" and "second". :lol:

My IMac says it has 4 GB of memory, but I didn't shut down the other programs (Chrome, Itunes, and DVD-player). Though it could not solve your level either.

If I understand you right, there is no evidence that it can be solved; it's just a matter of faith. 8)


Amnon, yes, I think you're right, but then a human can solve it. Even if the author is the only one who can solve it, which is very unlikely in my opinion, because in that case he/she must be the best sokoban-level-creator, and the best solver, both at the same time.
Image
Amnon
Rainbow Spirit Seeker
Posts: 6576
Joined: Wed Mar 22, 2006 5:29 am

Post by Amnon » Sat Sep 03, 2011 11:49 pm

Even if the author is the only one who can solve it, which is very unlikely in my opinion, because in that case he/she must be the best sokoban-level-creator, and the best solver, both at the same time.
Not necessarily: he/she could have worked backwards when creating the level, starting from the solution and pulling boxes instead of pushing them, then kept the reverse-code of what they did, which nobody else has.
Marinus
Rainbow AllStar
Posts: 4686
Joined: Sun Dec 16, 2007 2:20 pm

Post by Marinus » Sun Sep 04, 2011 12:02 am

True, but then it's just a matter of a happy coincidence, that it became such a hard level that no one else could solve. Otherwise the author still must be the best creator/solver.

Besides, I think it doesn't make any difference. If you want to solve a Sokobanlevel, you also have the choice to do it forward or backwards. There's no difference, except that there may be a few different end-positions for the push/pullcharacter.
Image
Muzozavr
Rainbow Spirit Chaser
Posts: 5648
Joined: Wed Jan 11, 2006 2:55 pm

Post by Muzozavr » Sun Sep 04, 2011 7:02 am

Some levels are hard to the point of impossibility for solvers but not so for us humans. Sometimes it's vice-versa, when there aren't that many different positions, but the author has cleverly applied some misdirection, making the solution difficult to see.

If it's both, then it's ultra-hard...

By the way, regarding your "Uptight Hamlet" level -- it's really not that bad. True, computer solvers are going to have a hard time with it (I just tested it with YASS and it couldn't solve this either) but for a Sokoban-playing human, it's really not all that hard. I just solved it in a completely unoptimized 385 moves and 54 pushes by myself. Took me two tries and... what, ten minutes? First time I did the wrong thing at the bottom.

However, that solver did manage to solve the "Supasoka" level (I think) but I couldn't get it no matter how hard I tried...

EDIT: I found it, here's an example of a level that humans would struggle a lot to solve it and my YASS took only a few seconds:

http://sokobano.de/results/display.php? ... gen&lvl=26 (I can't save the picture, it's generated there)

It's "Zeus" from the YASGen set. See the number of moves/pushes it takes? That's the best known solution.
Rest in peace, Kym. I hardly knew ya.
Rest in peace, Marinus. A bright star, you were ahead of me on my own tracks of thought. I miss you.
Marinus
Rainbow AllStar
Posts: 4686
Joined: Sun Dec 16, 2007 2:20 pm

Post by Marinus » Sun Sep 04, 2011 11:34 pm

Good job, solving the level that no computer can solve! :D

There's one thing I don't understand: If I'm right, then since the time they made pretty sophisticated chess programs, not even world champions chess were able to win from a computer. While chess pieces have so many more possible moves then Sokoban boxes, can a Sokoban level be so much more complicated then a chess game? Or perhaps those Sokoban solve programs are far less sophisticated then chess programs are?

Edit: BTW the Zeus level you mentioned is also on the website you posted before in the off topics: http://www.letslogic.com/puzzle_play.php?id=6850
Image
Amnon
Rainbow Spirit Seeker
Posts: 6576
Joined: Wed Mar 22, 2006 5:29 am

Post by Amnon » Mon Sep 05, 2011 5:22 am

While chess pieces have so many more possible moves then Sokoban boxes, can a Sokoban level be so much more complicated then a chess game?
Yes: no computer program can solve a full chess game, but looking forward 7-8 moves in advance plus another 4-5 moves on the most interesting combinations should be sufficient do defeat any human, but in sokoban, although the moves themselves are simpler, you do need to work all the way to the end, which may involve 100's of moves. Also, the chess board has only 64 squares and so many pieces, while sokoban can have more.

The more situations are searched, the more have to be stored to prevent duplication (and therefore endless repetitions), which means an extreme demand for memory.
Marinus
Rainbow AllStar
Posts: 4686
Joined: Sun Dec 16, 2007 2:20 pm

Post by Marinus » Mon Sep 05, 2011 8:33 am

Thanks! Seems logical to me.
Image
Muzozavr
Rainbow Spirit Chaser
Posts: 5648
Joined: Wed Jan 11, 2006 2:55 pm

Post by Muzozavr » Mon Sep 05, 2011 11:22 am

Regarding "UpTight Hamlet": it's really not that hard if you're a Sokoban player, most of the level runs on common sense and simple tactics. There's just a ton of moves and the number of possible positions makes sure that trial-and-error gets nowhere. The only difficult part is the bottom, you have to make sure that you're filling the right targets in the right order.

"Zeus", on the other hand, is bloody difficult for a human player. Not so many positions for a solver to calculate, but a huge amount of strange, counterintuitive and just plain odd moves required that no sane player would ever want to make. I actually used a solver for it (YASS) and lord, was the solution insanely complicated! I can't even REMEMBER what had to be done, lol.

If someone wants to be really evil, they can combine both levels into one ultimate nightmare. Nigh unsolvable by computer programs and incredibly hard for a human player! There's just one question... why would you want to do that? :?
Rest in peace, Kym. I hardly knew ya.
Rest in peace, Marinus. A bright star, you were ahead of me on my own tracks of thought. I miss you.
Post Reply