# On Grid Graph Reachability and Puzzle Games

arXiv: https://arxiv.org/abs/2310.01378 · HTML: https://mlsanity.com/paper/2310.01378/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 2 of its 29 references that are in the map.
- First posted on arXiv 2 Oct 2023.

## Builds on (most cited first, 2 of 2)

- [Qualitative Numeric Planning: Reductions and Complexity](https://mlsanity.com/paper/1912.04816/) (2019)
- [SAT Modulo Monotonic Theories](https://mlsanity.com/paper/1406.0043/) (2014)

## Abstract (arXiv)

Many puzzle video games, like Sokoban, involve moving some agent in a maze. The reachable locations are usually apparent for a human player, and the difficulty of the game is mainly related to performing actions on objects, such as pushing (reachable) boxes. For this reason, the difficulty of a particular level is often measured as the number of actions on objects, other than agent walking, needed to find a solution. In this paper we study CP and SAT approaches for solving these kind of problems. We review some reachability encodings and propose a new one. We empirically show that the new encoding is well-suited for solving puzzle problems in the planning as SAT paradigm, especially when considering the execution of several actions in parallel.