mbrown1413 / Mechanical-Puzzle-Studio

The Swiss Army knife of mechanical puzzle design.
https://puzzlestudio.io/
Mozilla Public License 2.0
1 stars 0 forks source link

[Solver] Dancing Links Implementation #15

Closed mbrown1413 closed 5 months ago

mbrown1413 commented 8 months ago

Make assembler faster by implementing dancing links exact cover algorithm.

After implementing, there are still plenty of other options for a faster solver covered in #45

mbrown1413 commented 5 months ago

Implemented in:

I implemented a bit more than the standard dancing links algorithm, allowing for column ranges. This is what we use for optional voxels, piece instancing, and, in the future piece min/max ranges.

I haven't implemented progress or really tried hard to profile and optimize the algorithm like I originally planned. When I briefly tried profiling, it turns out that the the process of enumerating piece placements is slower than the actual assembly! I'm sure this won't be true for every puzzle, but for now I think this is good enough.