A port of my old Sokoban solver (written in C) (https://github.com/Astronomy487/sokobansolver) to Rust. I've become that thing that people complain about
The big improvements I wanted to make were
- Allow "future" states to involve several consecutive box pushes. This cuts down on some (but not all) of the unecessary walking between different boxes the old solver would do (i.e. push this box just 1, then push this other box, then go back to the first box). This is the big thing
- Actually implement the Hungarian algorithm for the heuristic to estimate how good a certain arrangement of boxes-and-goals or boxes-and-their-original-positions are. graph theory is important kids
- Split source code into several files so it's all easier to manage
It runs about as fast as the old one for solvable levels, and it still struggles with the same kinds of levels as the old one. I wonder how smarter people solve those levels