Predicting Solvability and Difficulty of Sokoban Puzzles

Knowing if a Sokoban level has a solution requires a high investment of computational resources. This also happens when estimating difficulty; heuristics may not be precise, only work for simplified cases, be discontinuous and take much computing time. The calculation of high-fidelity heuristics is expensive and the performance of optimization systems is reduced by the time they take to deliver the result. In this article, two Convolutional Neural Networks (CNN) are implemented, a classifier of resolvable Sokoban boards and a regressor that predicts the number of pushes necessary to solve them. These obtained an accuracy of 79 % and MAE of 28, respectively. Trained models are useful in systems that do not require optimality, but rather guidance within the search space that balances time and quality. These networks can be used as surrogate methods, replacing high-fidelity heuristics that take too long.