So back when I first got to use a mobile phone in 2012 I used to play a lot of puzzle games. These were notoriously hard to solve (on high levels), and I always wondered how are these created, how do they find the minimum moves, how do they know its even minimal.
Now after being in a CS major for over 3 years, I finally understand these systems fairly. So I decided to make a klotski solver.
I wanted to make it fun so I stored the whole game board in an integer (uint64_t), as I like integers more than vectors. And then I got the urge to minify the engine to the max extent I could, so shrunk it down to 311 bytes from ~3.5 KB. The engine is only the searching part though.
The solver is a BFS that explores every reachable position. For the classic start it finds the best solution in 116 moves, after exploring all 25,955 reachable states in about 2-4 ms.
Here's the repo; any feedback is welcomed : ) https://github.com/Dream-World-Coder/depuzzled