n皇后问题

线上风

在n行n列的棋盘上，如果两个皇后位于棋盘上的同一行或者同一列或者同一对角线上，则称他们为互相攻击。现要求找出使n元棋盘上的n个皇后互不攻击的所有布局。
采用回溯算法，搜索整个解空间。求出所有解。
递归回溯
C语言风格
#include iostream>
using namespace std;
long sum=0;
bool Place(int k,int *p){//判断是否有冲突发生。k是当前摆放行
    for(int j=0;jk;j++)//p[j]==p[k]说明第j行与第k行放在同一列
        if(abs(k-j)==abs(p[j]-p[k])||p[j]==p[k])
        //abs(k-j)==abs(p[j]-p[k])说明斜率为+-1,说明在同一列
            return false;
    return true;
}

void Backtrack(int t,int *p,int n){
    if(t>=n)//棋盘共有n行，用0~n-1表示，故如果t到达n，递归返回
        sum++;//增加一次成功次数
    else
        for(int i=0;in;i++){//对第t行进行摆放尝试，可能情况是0~n-1
            p[t]=i;
            if(Place(t,p))Backtrack(t+1, p,n);//如果无冲突，摆放t+1行
        }
}
int nQueen(int n){
    int *p=new int[n];//数组p表示棋盘第i行皇后的位置
    for(int i=0; in;i++)
        p=0;//将棋盘数组初始化为0；
    Backtrack(0, p, n);//回溯求解，从第0行开始摆放
    delete [] p;
    return sum;
}
int main(){
    coutnQueen(8);
    return 0;
}

C++风格

#include
using namespace std;
class Queen{
    friend int nQueen(int);//执行函数
private:
    bool Place(int k);//测试第k行摆放后，是否有冲突发生
    void Backtrack(int t);//回溯
    int n,*x;//n为棋盘行数，x为记录每行的摆放位置的数组
    long sum;//记录成功次数
};
bool Queen::Place(int k){//同上
    for(int j=0;jk;j++)
        if(abs(k-j)==abs(x[j]-x[k])||x[j]==x[k])
            return false;
    return true;
}
void Queen::Backtrack(int t){//同上
    if(t>=n)
        sum++;
    else
        for(int i=0;in;i++){
            x[t]=i;
            if(Place(t))Backtrack(t+1);
        }
}
int nQueen(int n){
    Queen X;
    X.n = n;//棋盘行数
    X.sum = 0;//成功次数
    int *p=new int[n];
    for(int i=0; in;i++)
        p=0;
    X.x=p;
    X.Backtrack(0);//回溯
    delete [] p;
    return X.sum;
}
int main(){
    coutnQueen(8);
    return 0;
}

迭代回溯：
c语言风格
#include iostream>
using namespace std;
long sum=0;
bool Place(int k,int *p){//同上
    for(int j=0;jk;j++)
        if(abs(k-j)==abs(p[j]-p[k])||p[j]==p[k])
            return false;
    return true;
}
void Backtrack(int *p,int n){
    p[0] = -1;
    int i = 0;
    while(i>=0){
        p++;
        while(pn&&!(Place(i, p))) p++;
        if(pn){
            if(i == n-1) sum++;
            else{
                i++;
                p = -1;
            }
        }else
            i--;
    }
}
int nQueen(int n){
    int *p=new int[n];
    for(int i=0; in;i++)
        p=0;
    Backtrack(p, n);
    delete [] p;
    return sum;
}
int main(){
    coutnQueen(8);
    return 0;
}
迭代回溯
c++风格
#include iostream>
using namespace std;
class Queen{
    friend int nQueen(int);//执行函数
private:
    bool Place(int k);//测试第k行摆放后，是否有冲突发生
    void Backtrack(int t);//回溯
    int n,*x;//n为棋盘行数，x为记录每行的摆放位置的数组
    long sum;//记录成功次数
};
bool Queen::Place(int k){//同上
    for(int j=0;jk;j++)
        if(abs(k-j)==abs(x[j]-x[k])||x[j]==x[k])
            return false;
    return true;
}
void Queen::Backtrack(int t){//同上
    int i=0;//从第0行开始摆放
    x=-1;//初始化，x取值范围是0~n-1
    while(i>=0){//回溯初始行为0;
        x++;//从第0个位置摆放第i行
        while(xn&&!Place(i)) x++;//找到下一个没冲突的位置
        if(xn){//找到了没有冲突的位置
            if(i == n-1) sum++;//摆放结束
            else{//摆放下一行
                i++;
                x=-1;
            }
        }else//找完了整行，没有找到合适的位置，则回到上一行
            i--;//找上一行合适的位置，
    }
}
int nQueen(int n){
    Queen X;
    X.n = n;//棋盘行数
    X.sum = 0;//成功次数
    int *p=new int[n];
    for(int i=0; in;i++)
        p=0;
    X.x=p;
    X.Backtrack(0);//回溯
    delete [] p;
    return X.sum;
}
int main(){
    coutnQueen(8);
    return 0;
}


本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u2/70469/showart_1270307.html