(アルゴリズム)N皇后問題

タイトル:
八皇后問題:8 X 8のチェスに8人の皇后を置いて、互いに攻撃できないようにします.つまり、任意の2人の皇后が同じ行にいてはいけません.同じ列や対角線に同意して、条件に合ったすべての振り方を求めます.
考え方:
1、遡及法
データ構造:
8個の皇后が同じ行にあることができないため、各皇后が1行を占めることは間違いなく、1つの配列A[8]を定義することができ、配列中のi番目の数字、すなわちA[i]はi番目の行にある皇后の列番号を表す.
条件を満たす:任意の2つの皇后の異なる列、すなわちA[i]!=A[j],任意の2つの皇后は同じ対角線上にいない,すなわちabs(i-j)!=abs(A[i]-A[j]).
アルゴリズム:
遡及法は,配列Aのすべての配列の組合せを深さ遍歴の形で列挙し,枝切りの形(上記の条件を満たすか否かを判断する)で不要な計算量を減らすものであり,詳細はコードを参照する.
2、全配列法
構想は文字列の配列と同じであるhttp://www.cnblogs.com/AndyJee/p/4655485.htmlただ、それぞれの配列を判断する必要があります.
データ構造:
8個の皇后が同じ行にあることができない場合、各皇后が1行を占めることを肯定し、1つの配列A[8]を定義することができ、配列中のi番目の数字、すなわちA[i]はi番目の行にある皇后の列番号を表し、まず配列A[8]をそれぞれ0-7で初期化する.
条件を満たす:0-7という7つの異なる数字で配列を初期化するため、任意の2つの皇后も異なる列になるに違いない.では、各配列に対応する8つの皇后のうち、同じ対角線上に任意の2つがあるかどうかを判断するだけでよい.すなわち、配列の2つの下付きiとjについて、i-j=A[i]-A[j]またはi-j=A[j]-A[i]であれば、2つの要素が同じ対角線上に位置していると考えられ、その配列は条件に合致しない.
考え方:
参照文字列の配置:
全体の文字列の配列を求めて、2つのステップに分けることができます:まずすべての最初の位置に現れる可能性がある文字を求めて、つまり最初の文字と後ろのすべての文字を交換します;次に、最初の文字を固定し、後のすべての文字のソートを求めます.このときも後ろの文字を2つの部分と見なし、最初の文字と後ろの文字を繰り返します.(再帰)
そして、それぞれの配列が上記の追加を満たしているか否かを判断すればよい.
コード:
1、遡及法

#include <iostream>
#include <vector>
#include <stdlib.h>

using namespace std;
int count=0;

bool canPlace(int index,const vector<int> &result){
    for(int i=0;i<index;i++){
        if(result[index]==result[i] || abs(index-i)==abs(result[index]-result[i]))
            return false;
    }
    return true;
}

void queen(int index,vector<int> &result,int N){
    if(index==N){
        for(int i=0;i<N;i++)
            cout<<result[i]<<" ";
        cout<<endl;
        count++;
        return;
    }
    for(int i=0;i<N;i++){
        result[index]=i;
        if(canPlace(index,result))
            queen(index+1,result,N);
    }
}


int main()
{
    int n=8;
    vector<int> result;

    for(int i=0;i<n;i++)
        result.push_back(i);
    queen(0,result,n);
    cout<<count<<endl;
    return 0;
}

2、全配列法

#include <iostream>
#include <vector>
#include <stdlib.h>

using namespace std;
int count=0;

void swap(int *a,int *b){
    int tmp=*a;
    *a=*b;
    *b=tmp;
}

void queen_permutation(vector<int> &result,int index,int len){
    bool can=true;
    if(index==len-1){
        for(int i=0;i<len;i++){
            for(int j=i+1;j<len;j++){
                if(i-j==result[i]-result[j] || i-j==result[j]-result[i]){
                    can=false;
                    break;
                }
            }
            if(can==false)
                break;
        }
        if(can){
            for(int i=0;i<len;i++)
                cout<<result[i];
            cout<<endl;
            count++;
        }
    }
    else{
        for(int i=index;i<len;i++){
            swap(result[index],result[i]);
            queen_permutation(result,index+1,len);
            swap(result[index],result[i]);
        }
    }
}


int main()
{
    int n=8;
    vector<int> result;

    for(int i=0;i<n;i++)
        result.push_back(i);
    queen_permutation(result,0,n);
    cout<<count<<endl;
    return 0;
}