The N queens puzzle is a well studied toy program in computer science
used mainly to study algorithms and perform benchmarks. It consists in
finding all the solutions for the placement of N queens on an NxN
chess board. The only condition to abide is that no two queens attack
themselves. What this means is that no queen can share a row, a
column, or a diagonal with any other queen.
The most straightforward way of solving this problem in Prolog is by
using constraint logic programming or by using a backtracking
algorithm. If you search for it you will surely find a solution based
on constraint logic programming for this problem.
Though simple, this is a computationally intensive process. What I present here is a parallel version of N-Queens using the task-farm paradigm. Task-farming is the most simple and commonly used way of parallelizing applications. A master is set up, which takes care of creating tasks and distributing them among workers. The workers perform the tasks and send the results back to the master, which reassembles them. For simplifying the task, in this case only the solutions are counted for each problem size. This is largely based on the article ``Task Farming & The Message Passing Interface'', Dr. Dobbs Journal, Vol. 28, pages 32-37, September 2003.
Parallelizing the algorithm is straightforward. In this case, a job consists in a valid placement of queens up until a certain column. A result consists in the number of solutions found for that particular job. A worker must find all the solutions for that board prefix, then send the number back to the master.
The total number of solutions that exists up until 16:
1: 1 total solutions 2: 0 total solutions 3: 0 total solutions 4: 2 total solutions 5: 10 total solutions 6: 4 total solutions 7: 40 total solutions 8: 92 total solutions 9: 352 total solutions 10: 724 total solutions 11: 2680 total solutions 12: 14200 total solutions 13: 73712 total solutions 14: 365596 total solutions 15: 2279184 total solutions 16: 14772512 total solution