Don Knuth, in chapter 7.2.2. ‘Backtrack programming’ of his TAOCP, discusses the backtracking tree for the n queens problem.
OEIS A319284 records the profiles of these backtracking trees for n in 0:19 and references a Julia program.
What is the best way to parallelize this program (to extend the sequence)?
(I propose for comparison the test cases for n in 10:12 and 20:22.)
I’m no specialist in parallel backtracking but depth-first search sounds hard for parallelization. I wonder if you can turn this into a partially breadth-first algorithm? i.e., depth-first-searches-in-breadth-first-search? Or, equivalently, is there a way to “jump ahead” in the search tree? It’d cut data dependencies and let us use the canonical divide-and-conquer approach. If the “caching” aspect was important, we may need some concurrent data structures.