Open jmitchell opened 7 years ago
Existing backtracking research may clarify details of the design. I've started a wiki page to collect resources and thoughts on how they do or don't apply to this problem.
Study this optimized, parallel N-queens solver in Rust.
Finish #12 (Generate profiling reports) first.
👀
Backtracking problems are embarrassingly parallel, and
Backtrex
should exploit that internally.After the core API is stabilized, including implementing #2, split the search space into multiple sub-problems and delegate them to a worker pool. As solutions are discovered, have workers report them back so they can be concatenated to the solution stream.
The only clear drawback is the order in which solutions are discovered would no longer be consistent, but providing an API for sequential search (like the existing one) fixes that.
The benefits of supporting parallelism include scaling to the limits of a single BEAM node, and potentially beyond to more nodes until communication latency becomes the bottleneck. If sub-problem delegation and work stealing are implemented in a way that optimizes communication between coordinating processes to other coordinating processes or workers, the potential horizontal scalability could go far.
More detailed walkthrough
Rough sketch of the concept with the Sudoku solver in mind:
Sudoku.Solver
for the next unknown cell and its possible values.Existing tools?
OTP behaviours and newer Elixir behaviours, like GenStage, may be well suited for implementing this concept. They may even offer better strategies. Research what's out there, and consider options while avoiding assumptions about the topology of the search space (number of unknowns, number of values for each unknown, and time require to compute them), the number workers, or the delegation strategy.
Desired invariants
Invariants 1 and 2 may seem obvious, but it can be challenging when processes crash. It may even be impossible when certain coordinating processes crash. Invariant 1 is a strong requirement, whereas bounded compromise on 2 (rework) may be acceptable.