Solvable Sokoban Without a Solver via Diffusion

Sina Baghal

Deciding whether a Sokoban puzzle is solvable is PSPACE-complete (Culberson, 1997): solutions can be exponentially long and there is no short certificate to check. Solvability is a…