Jack Kutilek / Writing / Visual Sokoban Proofs

This is Draknek's Splitting Headache. Have you played it? Do you know the rules?

Yes, you do. In each level, let's map out the different equivalent states of the starting slime. And note where splitting pushes are possible, too.

We are looking for patterns, and insights - taking a step up the abstraction ladder.

There are some cool patterns here. It is easier to search through the state space of each level with these visual maps as our guide.

This is the best one. Level 6*.

Let's take a closer look at this one. See if we can make a complete map.

-- it doesn't seem like we can, at least not in any reasonable amount of time. And it's just becoming a mess.

Maybe we can map out its solutions, though. Here are the ones I found. They are each different in a significant way, but some are more similar to each other than others.

And actually, a lot of this space is not really needed when we are thinking more abstractly... we can unwrap it this way...

And then when we look at the solutions in this format...

Is this simpler? Easier to read? Does it highlight differences in solutions better? I dunno, but it's kinda neat.

~~~

I remembered these drawing when I was working on my own sokoban client. The simple style was perfect for small visuals of moves in the timeline.

But in longer solutions, in bigger levels, the timeline turns into a sea of lines; no clear distinction between moves, no clear representation of intent or order.

I want to group sets of moves into metamoves, show higher level steps of the solution with distinct purposes and sub-goals. I want to prove why moves are made, why this is the solution.

Let's make some drawings again.

~~~

We start with a Sokoban puzzle, and mark the dead tiles. Note the forced moves, even if we can't technically make them yet. Note more dead cells and unreachable areas... and more forced moves. Reorder some of our moves to resolve order-of-operations issues. Rinse and repeat - eventually we reach the solution.

Click the images to open them up big in a new tab.

Let's do some more. We'll start by noting down various observations that will motivate steps in our proof. Here we take note of regions that equivalently close a door, and free loops that are needed to make certain turns. We continue to draw boxes around changes to the sequence in each line.

This next one is pretty similar, though a little more complex.

Now let's try grouping steps by shared sub-goals.

And try reducing distracting repeated steps in the image.

This last one has some fun 'active region' swaps in the solution.

I want to make an application that helps to create these...

~~~

Jack Kutilek
August 2023

<< back