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
#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