Sokoban

Invented in 1981 by Hiroyuki Imabayashi

• Sokoban Touch
• Sokoban in JS

Proved PSPACE-complete in 1997

• able to emulate a linear bounded automata
• solvable if only if the LBA halts

Pull or PushPull Sokoban proved PSPACE-complete in 2016

• reductions are from Nondeterministic Constraint Logic
• PushPull-1-P and Pull-1-P are PSPACE-complete and Push-1-p is NP-hard

Many different types of deadlocks.

Festival solver

Curry has minimal handcoded knowledge, learns from solving simpler cases.

Benchmark for several solvers

Which Sokoban boards have the longest shortest solutions?

Solving in reverse by pulling boxes, avoid deadlocks.

Patrick’s Parabox

• adds blocks which are levels you can enter
• trailer

Block Pushing Puzzle Game But You Can Time Travel

• adds time travel portals

Give Up the Ghost

• movable portals and other tiles

Heroes of Sokoban

• Part 2
• Part 3

Handshakes

• get two hands to reach each other