alt Hacker NewsGot me curious: is there some way to approximate solvability of a puzzle in a certain time frame, or is that completely intractable?
Also, what counts as "complexity" in Sokoban puzzles. Does it plateau at a point, where board size/box count starts scaling the solving time more linearly?
Replies
yobbo • today at 3:01 PM
For games in general, one measure of complexity is branching factor. It means average number of possible actions or states at each turn. It is knowable.
"Solvability" would mean number of turns to solve the game. It is known for some puzzles and can be found by brute force, otherwise you need to figure out a proof.
➕ show 1 reply
There's computational complexity, then there's human complexity. I've thought a lot about this over the years (I've made a bunch of puzzle games, and puzzlescript, an engine/language for making grid-based puzzle games), and the only paper I've read that's made me think 'huh' was "Difficulty Rating of Sokoban Puzzle" by Jarušek and Pelánek ( https://www.fi.muni.cz/~xpelanek/publications/stairs2010-fin... ).
While I have a feeling that subject 'difficulty' is necessarily a slippery concept, they focus on 'context switching' as a key element of difficulty. In sokoban terms - how often you have to alternate between pushing one box and pushing another. This too can be gamed/trivialized, but, when I used it as a heuristic is was very good at generating the most horrifically difficult levels, much moreso than just going for 'solution length'.
On more general notions of complexity. In sokoban terms, the number of crates trumps everything else - for solvers I've written you quickly get exponential explosions with the number of crates. Nothing else really is significant.
I've also been working on solvers for more general classes of these games (puzzlescript games) and it's surprising how powerful generic solvers still are. PuzzleScript+MIS https://dekeyser.ch/puzzlescriptmis/ (not by me) is one powerful tool that uses PuzzleScript as a basis. I've worked on speeding up the solver a bunch (not currently integrated), figuring out good general heuristics for different kinds of games ( https://github.com/increpare/puzzlescript-labs has various experiments in this direction, including a modded version of PS+MIS). It's a nice optimizaiton problem for focusing on making numbers go down - there are lots of games to test on.