Parallel

[tomsib2001]

Hi, This is very nice work, I have used it to test a combinatorics tiling conjecture and it gave impressively fast results. I was wondering if there could be a way to make the algorithm parallel?

[backtracking]

Hi,

Thanks for the nice words.

Backtracking enumerations on all solutions (based on algorithm such as DLX) are indeed quite easy to parallelize: it suffices to make to make the first decisions ``manually'', and then, run the algorithm for each starting configuration.

In the N-queens problem, for instance, this amounts to place queens on the first rows. If for instance N is 16, then placing queens on the first 2 rows gives you 210 problems that you can then solve with the algorithm of your choice, independently, and then sum the results.

In a tiling problem, for instance, that would mean picking some particular tile(s), considering all their positions, and then solving the remaining tiling problem.

To answer your question, Combine does not do this. It is up to you to implement the above. If you are considering implementing this in OCaml as well, note that there is an OCaml library for distributing computing that you may find useful:

http://functory.lri.fr/About.html

Hope this helps,

Jean-Christophe

On 14/04/2016 15:30, tomsib2001 wrote:

Hi, This is very nice work, I have used it to test a combinatorics tiling conjecture and it gave impressively fast results. I was wondering if there could be a way to make the algorithm parallel?

— You are receiving this because you are subscribed to this thread. Reply to this email directly or view it on GitHub https://github.com/backtracking/combine/issues/3

[tomsib2001]

Thank you very much for this very detailed answer! I will definitely look into it. EDIT: removed comment about four color theorem, it seems to already be there, just need to figure out how to make it work.

[backtracking]

On an unrelated topic, I was thinking of making a pull request to color tiles using the four color theorem

That's a nice idea.

As you have already found by yourself, 4-coloring a map is an application of Combine itself!

Jean-Christophe