Skip to content

solver-ginsberg: Rework backtrack & Improve performance

Antoine Belvire requested to merge bugfix/21_solver_backtrack into master

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 to FINE). This is hard to debug without it. See also #33.

Others

croiseur-solver-ginsberg

  • Added a FirstViableCandidateChooser as CandidateChooser 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 keep LeastConstrainingCandidateChooser as default.
  • Cosmetic improvements
Edited by Antoine Belvire

Merge request reports