# How to parallelize OEIS A319284?

**URL:** <https://discourse.julialang.org/t/how-to-parallelize-oeis-a319284/63220>\
**Category:** General Usage\
**Tags:** parallel\
**Created:** [June 20, 2021, 9:09am UTC](https://discourse.julialang.org/t/how-to-parallelize-oeis-a319284/63220 "2021-06-20T09:09:17Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![leiteiro](https://avatars.discourse-cdn.com/v4/letter/l/b5e925/32.png) [@leiteiro](https://discourse.julialang.org/u/leiteiro)\
**Post date:** [June 20, 2021, 9:09am UTC](https://discourse.julialang.org/t/how-to-parallelize-oeis-a319284/63220/1 "2021-06-20T09:09:17Z")

</div>

[Don Knuth](https://en.wikipedia.org/wiki/Donald_Knuth), in chapter 7.2.2. ‘Backtrack programming’ of his [TAOCP](https://en.wikipedia.org/wiki/The_Art_of_Computer_Programming), discusses the [backtracking](https://en.wikipedia.org/wiki/Backtracking) tree for the n [queens problem](https://en.wikipedia.org/wiki/Eight_queens_puzzle).

[OEIS A319284](https://oeis.org/A319284) records the profiles of these backtracking trees for n in 0:19 and references a Julia [program](https://oeis.org/A319284/a319284.jl.txt).

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.)

---

<div class="post-metadata">

**Author:** ![tkf](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tkf/32/17635_2.png) [@tkf](https://discourse.julialang.org/u/tkf)\
**Post date:** [June 22, 2021, 11:42pm UTC](https://discourse.julialang.org/t/how-to-parallelize-oeis-a319284/63220/2 "2021-06-22T23:42:48Z")

</div>

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.