使用分布式实现N皇后问题 erlang语言实现

<未完>

对于N皇后问题的算法的设计一般都是基于c语言或者c++算法进行设计的回溯算法，但是当N的值很大的时候，这个时候如果要计算N皇后解的话，是比较费时间的，因此，可以采用并发的方式进行相应算法的设计，以此来提高效率。

下面的算法是使用c语言进行设计的回溯算法：

#include <stdio.h>
#include <stdlib.h>

#define N 11
int sum = 0;
int x[N];

int check(int k)
{
    int i;

    for(i = 0; i < k; i++) {
        if(x[i]==x[k] || abs(k-i)==abs(x[k]-x[i])) {
            return 0;
        }
    }
    return 1;
}

//递归算法
void Backtrack(int t)
{
    int i;
    if(t > N) {
        sum = sum+1;
        printf("%d\n", sum);
    } else {
        for(i = 0; i < N; i++) {
            x[t] = i;
            if(check(t)) {
                Backtrack(t+1);
            }
        }
    }
}

int main()
{
    Backtrack(4);
    printf("sum=%d\n", sum);
    return 0;
}

使用erlang语言进行并行开发，代码的核心算法并未给出，待续完成。

%% nqueensbitv2.erl

-module(nqueensbitv2).

-export([start/1,startSearch/3,collect/3,startAllThread/1]).

-define(LOG(X), io:format("~p  ~p  ~p~n", [?MODULE, ?LINE, X])).

%% 模块的外部调用函数，开始计算N皇后的计算。

%% NQueens：表示的是皇后的个数。

start(NQueens) ->

%% 如果皇后个数小于4的话，不符合N皇后问题的计算，所以直接退出。

if(NQueens < 4) -> 

io:format("Can't solve Nqueens problem less then 4.~n");

true -> 

%% 创建一个收集处理的进程。

CollectID = spawn(?MODULE, collect, [[],0,self()]),

%% 创建NQeens个进程，每一个进程分别处理一种情况。

createNthreads(NQueens ,CollectID ,NQueens),

%% 上面的操作结束之后，该进程等待结束的消息。

receive

{finished,Solutions} ->

io:format("Find Solutions:~w.~n",[Solutions]);

_ ->

ok

end

end.

%% 收集处理进程所干的事情

%% ChildPIDS：记录已经创建好的进程的PID，是一个列表类型

%% Solutions：记录已经计算出来的N皇后问题的解的个数

%% ChildPIDS：记录此进程创建者PID，也就是start进程

collect(ChildPIDS,Solutions,ParentPID)->

receive

startChild -> 

spawn(nqueensbitv2,startAllThread,[ChildPIDS]),

collect(ChildPIDS,Solutions,ParentPID);  

{addchild,ChildP} -> 

collect([ChildP|ChildPIDS],Solutions,ParentPID);  

{finished,ChildP} -> 

LeftPIDS = lists:delete(ChildP,ChildPIDS),

if(LeftPIDS == []) -> 

ParentPID ! {finished,Solutions};

true -> 

collect(LeftPIDS,Solutions,ParentPID)

end;

{found,SolutionPath} ->

collect(ChildPIDS,Solutions + 1,ParentPID);

{found,_} -> collect(ChildPIDS,Solutions + 1,ParentPID);

_ -> ok

end.

%% 创建N个进程，每一个进程都是相互独立的

createNthreads(_,CollectID,0) ->

CollectID ! startChild;

createNthreads(N,CollectID,Nthread) ->

?LOG(N), 

?LOG(CollectID), 

?LOG(Nthread),

ChildP = spawn(nqueensbitv2,startSearch,[N,CollectID,Nthread]),

CollectID ! {addchild,ChildP},

createNthreads(N,CollectID,Nthread - 1).

%% 启动创建好的计算进程，让其开始计算

startAllThread([]) -> ok;

startAllThread([Child|Childs]) -> ?LOG(Childs),

Child ! startSearch,

startAllThread(Childs).

%% 单个独立计算进程所进行的计算

startSearch(NQueens,CollectID,NthThread) ->

%% 核心算法