solver-ginsberg: Rework backtrack & Improve performance
Context
Fixes backtracking implementation issues leading to solver claiming grid is impossible while valid branches remain to explore.
Unfortunately, this shows that solver is still too slow to find a solution for the grid presented in #19 (closed). An attempt to improve performance by storing initial candidates per slots inside tries is present in this MR. It improves raw iteration speed by a factor of 10. It is still ~ 100 times slower than xwords-rs speed though.
Fixes #19 (closed), #21 (closed).
What has changed?
Main Changes
croiseur-solver-ginsberg
- Rework dynamic backtrack.
- Remove unused (and wrongly implemented) backtrack strategies.
Side Effects
croiseur-solver-ginsberg
- Dictionary lookup speed improvements, added Trie implementation; Still some room for improvements
- Add a
FineProgressPrinter
as solver listener in order to show backtracking live when debugging (at least when log level is set toFINE
). This is hard to debug without it. See also #33.
Others
croiseur-solver-ginsberg
- Added a
FirstViableCandidateChooser
asCandidateChooser
strategy: Take the first viable candidate without consideration for other candidates bringing potentially less constraints on the grid. Faster but seems to lead to more backtracks in general so keepLeastConstrainingCandidateChooser
as default. - Cosmetic improvements
Edited by Antoine Belvire